BZOJ2212 [POI2011] Tree Rotations 【treap】

题目分析：
写的无旋treap应该跑不过，但bzoj判断的总时限。把相关实现改成线段树合并就可以了。
代码：
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int maxn = 1000020;
  5 
  6 int n;
  7 int ch[maxn][2],num,val[maxn];
  8 
  9 int son[maxn>>2][2],sz[maxn],rot[maxn],data[maxn],key[maxn];
 10 
 11 long long ans = 0;
 12 
 13 int merge(int r1,int r2){
 14     if(r1 == 0) return r2; if(r2 == 0) return r1;
 15     if(key[r1] < key[r2]){
 16     son[r1][1] = merge(son[r1][1],r2);
 17     sz[r1] = sz[son[r1][0]]+sz[son[r1][1]]+1;
 18     return r1;
 19     }else{
 20     son[r2][0] = merge(r1,son[r2][0]);
 21     sz[r2] = sz[son[r2][0]]+sz[son[r2][1]]+1;
 22     return r2;
 23     }
 24 }
 25 pair<int,int> split(int rt,int k){
 26     if(k == 0) return make_pair(0,rt);
 27     if(k >= sz[rt]) return make_pair(rt,0); 
 28     if(sz[son[rt][0]] >= k){
 29     pair<int,int> res = split(son[rt][0],k);
 30     son[rt][0] = res.second; res.second = rt;
 31     sz[rt] = sz[son[rt][0]] + sz[son[rt][1]] + 1;
 32     return res;
 33     }else{
 34     pair<int,int> res = split(son[rt][1],k-sz[son[rt][0]]-1);
 35     son[rt][1] = res.first; res.first = rt;
 36     sz[rt] = sz[son[rt][0]] + sz[son[rt][1]] + 1;
 37     return res;
 38     }
 39 }
 40 int found(int now,int x){
 41     if(now == 0) return 0;
 42     if(data[now] == x) return sz[son[now][0]];
 43     if(data[now] < x) return sz[son[now][0]]+1+found(son[now][1],x);
 44     else return found(son[now][0],x);
 45 }
 46 
 47 void dfs(int now){
 48     int d; scanf("%d",&d);
 49     if(d){val[now] = d; return;}
 50     ch[now][0] = ++num; dfs(num); ch[now][1] = ++num; dfs(num);
 51 }
 52 
 53 long long alpha,beta;
 54 void walk(int A,int B){
 55     int z = found(B,data[A]); alpha += z; beta += (sz[B]-z);
 56     if(son[A][0]) walk(son[A][0],B);
 57     if(son[A][1]) walk(son[A][1],B);
 58 }
 59 
 60 void dfs2(int A,int &B){
 61     if(son[A][0]) dfs2(son[A][0],B),son[A][0] = 0;
 62     if(son[A][1]) dfs2(son[A][1],B),son[A][1] = 0;
 63     sz[A] = 1; int z = found(B,data[A]);
 64     pair<int,int> pr = split(B,z);
 65     B = merge(merge(pr.first,A),pr.second);
 66 }
 67 
 68 void dfs1(int now){
 69     if(val[now]){
 70     num++;
 71     key[num]=rand();
 72     sz[num]=1;
 73     data[num]=val[now];
 74     rot[now]=num;
 75     return;
 76     }
 77     dfs1(ch[now][0]); dfs1(ch[now][1]);
 78     alpha = 0,beta = 0;
 79     if(sz[rot[ch[now][0]]] < sz[rot[ch[now][1]]]){
 80     walk(rot[ch[now][0]],rot[ch[now][1]]);
 81     dfs2(rot[ch[now][0]],rot[ch[now][1]]);
 82     rot[now] = rot[ch[now][1]];
 83     }else {
 84     walk(rot[ch[now][1]],rot[ch[now][0]]);
 85     dfs2(rot[ch[now][1]],rot[ch[now][0]]);
 86     rot[now] = rot[ch[now][0]];
 87     }
 88     ans += min(alpha,beta);
 89 }
 90 
 91 void read(){
 92     scanf("%d",&n);
 93     num = 1;
 94     dfs(1);
 95 }
 96 
 97 void work(){
 98     num = 0;
 99     dfs1(1);
100     printf("%lld",ans);
101 }
102 
103 int main(){
104     read();
105     work();
106     return 0;
107 }