Tip

凡是O(log)转O(1),本质都是ST表与单调性

笛卡尔树

#define EL 
#include<bits/stdc++.h> 
#define int unsigned long long
EL using namespace std; EL
#define  FIO 0 
#define  ten(x) (((x)<<1)+((x)<<3)) 
#define  opposite(x) ((~(x))+1) 
#define  Fsize 100000 
#define  Run const auto __Only_Big_Pool_Use_It_Function_To_Run_Code__ = []{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
#define  Runs(Val) const auto Val = []{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
#define  JustIt };auto __Only_Big_Pool_Use_It_Value_To_Run_Code__=__Only_Big_Pool_Use_It_Function_To_Run_Code__();signed main(){} 
#define  ONLINE_JUDGE EL 
#ifdef ONLINE_JUDGE
#if FIO  
#define  getchar() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++) 
#define  putchar(Ch) (FoutSize<Fsize?Fout[FoutSize++]=Ch:(fwrite(Fout,1,Fsize,stdout),Fout[(FoutSize=0)++]=Ch)) 
#define  Cb fwrite(Fout, 1, FoutSize, stdout); return FoutSize = 0; EL  EL 
#else
    Runs(ds) return 0; }(); EL static std::streambuf* inbuf = cin.rdbuf(); EL static std::streambuf* outbuf = cout.rdbuf();
#define  getchar() (A == B && (B = (A = Fin) + inbuf -> sgetn(Fin, Fsize), A == B) ? EOF : *A++) 
#define  putchar(Ch) (outbuf -> sputc(Ch)) 
#define  Cb return 0; EL  EL 
#endif 
#ifndef _WIN64
#define  inline __inline__ __attribute__((always_inline))  EL  EL 
#endif
#endif 
#define  register  EL 
EL template<typename T>concept Double = std::is_same<T, float>::value || std::is_same<T, double>::value || std::is_same<T, long double>::value; EL template<typename T>concept Int = std::is_integral<T>::value; template<Int T, Double Y>inline T mul(T x, T y, T mod) { return (x * y - (T)((Y)x / mod * y) * mod + mod) % mod; }EL   EL template<typename T = long long> constexpr T Pow10[10] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000 }; EL static struct ArrayWriter { char Insert = ' ', End = '\n'; }war; EL template<typename T = char> struct VectorIOer { T* x; int Len; template<typename Other>inline VectorIOer<Other>& operator()(Other* x, int Len) { VectorIOer<Other> e; e.Len = Len, e.x = x; return e; } }; VectorIOer vio; EL int Index, Top, FoutSize; char Ch, * A, * B, Fin[Fsize], Fout[Fsize], Stack[Fsize]; EL   EL template<Int T> inline void read(register T& x) { bool sign = 0; x = 0; while (!((Ch = getchar()) == '-' ? Ch = getchar(), sign = 1 : isdigit(Ch))); while (x = ten(x) + (Ch & 15), isdigit(Ch = getchar())); x = sign ? opposite(x) : x; } EL template<Double T> inline void read(register T& x) { bool sign = 0; x = 0, Index = 1; while (!((Ch = getchar()) == '-' ? Ch = getchar(), sign = 1 : isdigit(Ch))); while (x = 10 * x + (Ch & 15), isdigit(Ch = getchar())); if (Ch == '.' && (Ch = getchar())) while (x += T(Ch & 15) / (Index *= 10), isdigit(Ch = getchar())); x = sign ? -x : x; } EL inline void read(register char& x) { x = getchar(); } EL inline void read(register char* x) { while ((*(x++) = getchar()) != '\n'); *(--x) = '\0'; } EL template<size_t Len, typename T> inline void read(T* x) { Index = 0; while (read(*(x + Index++)), Index != Len); } EL template<typename T> inline void read(register VectorIOer<T>&& io) { Index = 0; while (read(*(io.x + Index++)), Index != io.Len); } EL template<typename T> inline void read(register VectorIOer<T>& io) { Index = 0; while (read(*(io.x + Index++)), Index != io.Len); } EL template<typename T, typename... Args>inline void read(register T& x, register Args&... args) { read(x), read(args...); } EL template<Int T> inline void write(register T x) { if (!x)return (void)(putchar('0')); if (x < 0)putchar('-'), x = -x; while (x)Stack[++Top] = (x % 10) ^ 48, x /= 10; while (Top)putchar(Stack[Top--]); } EL inline void write(register char& x) { putchar(x); } EL inline void write(register char* x) { while (putchar(*(x++)), *x ^ '\0'); } EL inline void write(const char x[]) { register int i = 0; while (putchar(x[i++]), x[i] ^ '\0'); } EL template<size_t Len, typename T> inline void write(T* x) { Index = 0; while (write(*(x + Index++)), Index != Len) putchar(war.Insert); putchar(war.End); } EL template<typename T> inline void write(register VectorIOer<T>&& io) { Index = 0; while (write(*(io.x + Index++)), Index != io.Len) putchar(war.Insert); putchar(war.End); } EL template<typename T> inline void write(register VectorIOer<T>& io) { Index = 0; while (write(*(io.x + Index++)), Index != io.Len) putchar(war.Insert); putchar(war.End); } EL template<Double T>inline void write(T X, int k = 6) { long long x = X; if (!x) (putchar('0')); if (x < 0)putchar('-'), x = -x; while (x)Stack[++Top] = (x % 10) ^ 48, x /= 10; while (Top)putchar(Stack[Top--]); if (!k) return; putchar('.'), Index = 1; if (!(X -= (long long)X))while (k--) putchar('0'); write((long long)(X * Pow10<long long>[k])); } EL template<typename T, typename... Args> inline void write(register T x, register Args... args) { write(x), write(args...); } EL inline int clear() { Cb } EL  EL template<Int T> EL T power(T&& a, T&& b, T&& c) { EL     if (b == 0) EL         return 1 % c; EL     long long ans = 1, t = a; EL     while (b > 0) { EL         if (b & 1) ans = ans * t % c; EL         b /= 2; t = t * t % c; EL } EL     return ans; EL } EL template<Int T> EL void exgcd(T a, T b, T& x, T& y) { EL     if (b == 0) { EL         x = 1, y = 0; EL         return; EL } EL     exgcd(b, a % b, y, x); EL     y -= a / b * x; EL } EL template<Int T, Int Y, Int P> EL inline void setinv(T* inv, Y p, P go) { EL     inv[1] = 1; EL     for (Y i = 2; i < go; ++i) EL         inv[i] = (p - p / i) * inv[p % i] % p; EL } EL template<Int Y> EL Y powmod(Y a, Y b, Y p) { EL     Y res = 1; EL     while (b > 0) { EL         if (b & 1) res = res * a % p; EL         a = a * a % p, b >>= 1; EL } EL     return res; EL } EL  EL   EL template<Int R> EL int generator(R p) { EL     vector<R> fact; EL     R phi = p - 1, n = phi; EL     for (R i = 2; i * i <= n; ++i) { EL         if (n % i == 0) { EL             fact.push_back(i); EL             while (n % i == 0) n /= i; EL } EL } EL     if (n > 1) fact.push_back(n); EL     for (R res = 2; res <= p; ++res) { EL         bool ok = true; EL         for (R factor : fact) { EL             if (powmod(res, phi / factor, p) == 1) { EL                 ok = false; EL                 break; EL } EL } EL         if (ok) return res; EL } EL     return -1; EL } EL template<Int T> EL T phi(T n) EL { EL     T res = n; EL     for (T i = 2; i * i <= n; ++i) EL{ EL         if (n % i == 0) EL             res = res / i * (i - 1);   EL         while (n % i == 0)   EL             n /= i; EL } EL     if (n > 1) EL         res = res / n * (n - 1);   EL     return res; EL } EL template<Int ll> EL ll inv(ll a, ll p) { EL     ll d, x, y; EL     exgcd(a, p, d, x, y); EL     return d == 1 ? (x + p) % p : -1; EL } EL  template<typename T = long double, size_t Len = 3> EL struct Vector { EL  EL   using vec = Vector<T, Len>; EL  array<T, Len> data; EL  T& x = data[0], & y = data[1], & z = (Len >= 3) ? data[2] : data[1]; EL     T& operator[](size_t at) { EL       return data[at]; EL } EL    vec operator =(vec Other) { EL      for (size_t i = 0; i < Len; data[i] = Other.data[i], i++); EL       return *this; EL }vec operator+(vec& v) { EL        vec t; EL       for (size_t i = 0; i < Len; ++i) { EL           t[i] = data[i] + v[i]; EL } EL      return t; EL } EL   vec operator-(vec& v) { EL      vec t; EL       for (size_t i = 0; i < Len; ++i) { EL           t[i] = data[i] - v[i]; EL } EL      return t; EL } EL   T operator*(vec& v) { EL        T re = 0; EL        for (size_t i = 0; i < Len; ++i) { EL           re += data[i] * v[i]; EL } EL       this->data[0]; EL       return re; EL } EL  T operator^ (Vector<T, 2>& Other) { EL      if (Len != 2) EL            const int Throw = [] { throw (cerr << "Cannot cross", " Vector<T, 2>"); return 0; }(); EL       return data[0] * Other.data[1] - data[1] * Other.data[0]; EL } EL   vec operator^ (Vector<T, 3>& Other) { EL        if (Len != 3) EL            const int Throw = [] { throw (cerr << "Cannot cross", " Vector<T, 3>"); return 0; }(); EL       return vec{ {data[1] * Other.data[2] - data[2] * Other.data[1] ,data[2] * Other.data[0] - data[0] * Other.data[2],data[0] * Other.data[1] - data[1] * Other.data[0] } }; EL } EL    T times(Vector<T, 2>& Other) { EL       if (Len != 2) EL            const int Throw = [] { throw (cerr << "Cannot cross", " Vector<T, 2>"); return 0; }(); EL       return data[0] * Other.data[1] - data[1] * Other.data[0]; EL } EL   vec times(Vector<T, 3>& Other) { EL         if (Len != 3) EL            const int Throw = [] { throw (cerr << "Cannot cross", " Vector<T, 3>"); return 0; }(); EL       return vec{ {data[1] * Other.data[2] - data[2] * Other.data[1] ,data[2] * Other.data[0] - data[0] * Other.data[2],data[0] * Other.data[1] - data[1] * Other.data[0] } }; EL }vec operator+(vec&& v) { EL        vec t; EL       for (size_t i = 0; i < Len; ++i) { EL           t[i] = data[i] + v[i]; EL } EL      return t; EL } EL   vec operator-(vec&& v) { EL         vec t; EL       for (size_t i = 0; i < Len; ++i) { EL           t[i] = data[i] - v[i]; EL } EL      return t; EL } EL   T operator*(vec&& v) { EL       T re = 0; EL        for (size_t i = 0; i < Len; ++i) { EL           re += data[i] * v[i]; EL } EL       this->data[0]; EL       return re; EL } EL  T operator^ (Vector<T, 2>&& Other) { EL         if (Len != 2) EL            const int Throw = [] { throw (cerr << "Cannot cross", " Vector<T, 2>"); return 0; }(); EL       return data[0] * Other.data[1] - data[1] * Other.data[0]; EL } EL   vec operator^ (Vector<T, 3>&& Other) { EL       if (Len != 3) EL            const int Throw = [] { throw (cerr << "Cannot cross", " Vector<T, 3>"); return 0; }(); EL       return vec{ {data[1] * Other.data[2] - data[2] * Other.data[1] ,data[2] * Other.data[0] - data[0] * Other.data[2],data[0] * Other.data[1] - data[1] * Other.data[0] } }; EL } EL    T times(Vector<T, 2>&& Other) { EL      if (Len != 2) EL            const int Throw = [] { throw (cerr << "Cannot cross", " Vector<T, 2>"); return 0; }(); EL       return data[0] * Other.data[1] - data[1] * Other.data[0]; EL } EL   vec times(Vector<T, 3>&& Other) { EL        if (Len != 3) EL            const int Throw = [] { throw (cerr << "Cannot cross", " Vector<T, 3>"); return 0; }(); EL       return vec{ {data[1] * Other.data[2] - data[2] * Other.data[1] ,data[2] * Other.data[0] - data[0] * Other.data[2],data[0] * Other.data[1] - data[1] * Other.data[0] } }; EL }vec operator*(T v) { EL        vec re; EL      for (size_t i = 0; i < Len; ++i) { EL           re[i] = data[i] * v; EL } EL        this->data[0]; EL       return re; EL } EL  template<typename JD = long double> EL  JD Length() { EL        JD re = 0; EL       for (size_t i = 0; i < Len; ++i) { EL           re += data[i] * data[i]; EL } EL        this->data[0]; EL       return sqrt(re); EL } EL  EL    Vector(array<T, Len> Data) :data(Data) {}; EL   Vector() {} EL }; EL template<typename T = double> EL struct Camera { EL    Camera(T X = 1, T Y = 1, T Z = 1) { EL      x = X, y = Y, z = Z; EL } EL    T x, y, z; EL }; EL  EL namespace exVector { EL     template<typename T, size_t Len> EL     inline T DegOf(Vector<T, Len> a, Vector<T, Len> b) { EL         auto ji = a * b; EL         auto lena = a.Length(); EL      auto lenb = b.Length(); EL      return acosl(ji / lena / lenb); EL } EL     template<typename T> EL     Vector<T, 3> NullVec{ 0,0,0 }; EL  EL }using namespace exVector; template<Int word, Int ull>bool check(const word a, const ull p) { ull d = p - 1, get = pow(a, d, p); if (get != 1) return 1; while ((d & 1) ^ 1)if (d >>= 1, (get = pow(a, d, p)) == p - 1) return 0; else if (get != 1) return 1; return 0; }constexpr unsigned char test[]{ 2,3,5,7,11,13,17,19,23,29,31,37 }; template<Int word>bool IsPrime(const word p) { if (p > 40) { for (word a : test)if (check(a, p)) return 0; return 1; }for (word a : test)if (p == a) return 1; return 0; }

const int maxn = 1e7 + 10;
int top, rs[maxn], ls[maxn], stk[maxn], n, p[maxn], ans1, ans2;
inline void build() {
    for (int i = 1; i <= n; i++) {
        int k = top;
        while (k > 0 && p[stk[k]] > p[i]) k--;
        if (k) rs[stk[k]] = i;
        if (k < top) ls[i] = stk[k + 1];
        stk[++k] = i;
        top = k;
    }
}
signed main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(p[i]);
    build();
    for (int i = 1; i <= n; ++i) {
        ans1 ^= (i * (ls[i] + 1));
        ans2 ^= (i * (rs[i] + 1));
    }
    write(ans1, ' ', ans2);
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇