[模板]ETT

约定不等于承诺〃 2021-12-22 16:47 166阅读 0赞

![1332167-20190327135822890-165402248.png][]

解：splay维护括号序列，就是进子树一次出子树一次。树上每个点直接记录这两个点的编号。

建树的时候按照分配的编号建树。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 typedef long long LL;
      3 #define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
      4 static char buf[100000],*pa(buf),*pb(buf);
      5 template <class T> inline void read(T &x) {
      6     x = 0;
      7     register char c(gc);
      8     while((c<'0'||c>'9')&&c!='-')
      9         c=gc;
     10     register int f(c=='-'?c=gc,-1:1);
     11     while(c>='0'&&c<='9')
     12         x=x*10+c-48,c=gc;
     13     x*=f;
     14     return;
     15 }
     16 
     17 const int N = 400010;
     18 const LL INF = 0x3f3f3f3f3f3f3f3fll;
     19 
     20 struct Edge {
     21     int nex, v;
     22 }edge[N]; int tp;
     23 
     24 int fa[N], op[N], ed[N], s[N][2], root, stk[N], top;
     25 LL large[N], val[N], Val[N], tag[N];
     26 int e[N], num = 1, n, id[N];
     27 
     28 inline void add(int x, int y) {
     29     tp++;
     30     edge[tp].v = y;
     31     edge[tp].nex = e[x];
     32     e[x] = tp;
     33     return;
     34 }
     35 
     36 void DFS(int x, int f) {
     37     id[++num] = x;
     38     op[x] = num;
     39     for(int i = e[x]; i; i = edge[i].nex) {
     40         int y = edge[i].v;
     41         if(y == f) continue;
     42         DFS(y, x);
     43     }
     44     id[++num] = x;
     45     ed[x] = num;
     46     return;
     47 }
     48 
     49 inline void pushup(int x) {
     50     large[x] = std::max(large[s[x][0]], large[s[x][1]]);
     51     large[x] = std::max(large[x], val[x]);
     52     if(!fa[x]) root = x;
     53     return;
     54 }
     55 
     56 inline void pushdown(int x) {
     57     if(tag[x]) {
     58         if(s[x][0]) {
     59             tag[s[x][0]] += tag[x];
     60             val[s[x][0]] += tag[x];
     61             large[s[x][0]] += tag[x];
     62         }
     63         if(s[x][1]) {
     64             tag[s[x][1]] += tag[x];
     65             val[s[x][1]] += tag[x];
     66             large[s[x][1]] += tag[x];
     67         }
     68         tag[x] = 0;
     69     }
     70     return;
     71 }
     72 
     73 void out(int x = root) {
     74     pushdown(x);
     75     if(s[x][0]) {
     76         out(s[x][0]);
     77     }
     78     printf("%d ", id[x]);
     79     if(s[x][1]) {
     80         out(s[x][1]);
     81     }
     82     return;
     83 }
     84 
     85 inline void rotate(int x) {
     86     int y = fa[x];
     87     int z = fa[y];
     88     bool f = (s[y][1] == x);
     89     
     90     fa[x] = z;
     91     if(z) {
     92         s[z][s[z][1] == y] = x;
     93     }
     94     s[y][f] = s[x][!f];
     95     if(s[x][!f]) {
     96         fa[s[x][!f]] = y;
     97     }
     98     s[x][!f] = y;
     99     fa[y] = x;
    100     
    101     pushup(y);
    102     return;
    103 }
    104 
    105 inline void splay(int x, int g = 0) {
    106     int y = x;
    107     stk[top = 1] = y;
    108     while(fa[y]) {
    109         y = fa[y];
    110         stk[++top] = y;
    111     }
    112     while(top) {
    113         pushdown(stk[top]);
    114         top--;
    115     }
    116     
    117     y = fa[x];
    118     int z = fa[y];
    119     while(y != g) {
    120         if(z != g) {
    121             (s[z][1] == y) ^ (s[y][1] == x) ? 
    122             rotate(x) : rotate(y);
    123         }
    124         rotate(x);
    125         y = fa[x];
    126         z = fa[y];
    127     }
    128     pushup(x);
    129     return;
    130 }
    131 
    132 inline int getLP() {
    133     pushdown(root);
    134     int p = s[root][0];
    135     while(s[p][1]) {
    136         p = s[p][1];
    137         pushdown(p);
    138     }
    139     return p;
    140 }
    141 
    142 inline int getRP() {
    143     pushdown(root);
    144     int p = s[root][1];
    145     while(s[p][0]) {
    146         p = s[p][0];
    147         pushdown(p);
    148     }
    149     return p;
    150 }
    151 
    152 int build(int l, int r, int f) {
    153     int mid = (l + r) >> 1;
    154     //int x = np(f, Val[id[mid]]);
    155     fa[mid] = f;
    156     val[mid] = large[mid] = Val[id[mid]];
    157     if(l < mid) s[mid][0] = build(l, mid - 1, mid);
    158     if(mid < r) s[mid][1] = build(mid + 1, r, mid);
    159     pushup(mid);
    160     return mid;
    161 }
    162 
    163 inline void Add(int x, LL v) {
    164     splay(op[x]);
    165     int a = getLP();
    166     splay(ed[x]);
    167     int b = getRP();
    168     splay(b);
    169     splay(a, b);
    170     int z = s[a][1];
    171     tag[z] += v;
    172     large[z] += v;
    173     val[z] += v;
    174     pushup(a);
    175     pushup(b);
    176     return;
    177 }
    178 
    179 int main() {
    180 
    181     int q, rt, x; LL y;
    182     read(n); read(q); read(rt);
    183     for(register int i = 1; i <= n; i++) {
    184         read(Val[i]);
    185     }
    186     for(register int i = 1; i < n; i++) {
    187         read(x); read(y);
    188         add(x, y); add(y, x);
    189     }
    190     
    191     DFS(rt, 0);
    192     
    193     /*for(int i = 1; i <= num + 1; i++) {
    194         printf("%d ", id[i]);
    195     }
    196     puts("");*/
    197     
    198     Val[0] = val[0] = -INF;
    199     root = build(1, num + 1, 0);
    200     
    201     //out(), puts("");
    202     
    203     for(int i = 1, f; i <= q; i++) {
    204         read(f); read(x);
    205         if(f == 3) { /// out max subtree x
    206             splay(op[x]);
    207             int a = getLP();
    208             splay(ed[x]);
    209             int b = getRP();
    210             splay(b);
    211             splay(a, b);
    212             printf("%lld\n", large[s[a][1]]);
    213         }
    214         else if(f == 2) { /// subtree x += y
    215             read(y);
    216             Add(x, y);
    217         }
    218         else if(f == 1) { /// change fa[x] -> y
    219             read(y);
    220             splay(op[x]);
    221             int a = getLP();
    222             splay(ed[x]);
    223             int b = getRP();
    224             
    225             /*printf("%d op = %d ed = %d \n", x, op[x], ed[x]);
    226             printf("a=%d %d  b=%d %d \n", a, id[a], b, id[b]);*/
    227             
    228             splay(b);
    229             splay(a, b);
    230             int z = s[a][1];
    231             s[a][1] = fa[z] = 0;
    232             pushup(a);
    233             pushup(b);
    234             splay(op[y]);
    235             int t = getRP();
    236             splay(t, op[y]);
    237             s[t][0] = z; fa[z] = t;
    238             pushup(t);
    239             pushup(op[y]);
    240         }
    241         //out(), puts("");
    242     }
    243     
    244     return 0;
    245 }

AC代码

转载于:https://www.cnblogs.com/huyufeifei/p/10607106.html

[1332167-20190327135822890-165402248.png]: /images/20211220/f370ba5304d640f792c147008c703819.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/4fcb4afe68814ec7bb82b2b895f772bc.png