三、P3285 [SCOI2014]方伯伯的OJ
无力吐槽，此题动态开点。。。debug了一整天，代码漏洞颇多。。。。QAQ
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAX=3e5+100,INF=0x7fffffff; 4 struct ppp{ 5 int ch[2],rnd,size,l,r,fa; 6 }treap[MAX]; 7 map<int,int> f; 8 int n,m,a,tot,root,lnow=INF,cnt=0; 9 void update(int p) 10 { 11 treap[p].size=treap[treap[p].ch[0]].size+treap[treap[p].ch[1]].size+treap[p].r-treap[p].l+1; 12 treap[treap[p].ch[0]].fa=treap[treap[p].ch[1]].fa=p; 13 treap[0]=(ppp){0,0,0,0,0,0,0}; 14 } 15 int divide(int now,int k)//now保留前k个 16 { 17 if(k==treap[now].r-treap[now].l+1) return 0; 18 if(k==0) return now; 19 tot++; 20 treap[tot]=(ppp){0,0,rand(),0,treap[now].l+k,treap[now].r,0}; 21 22 f[treap[now].r]=tot; 23 f[treap[now].l+k-1]=now; 24 25 treap[now].r=treap[now].l+k-1; 26 treap[tot].ch[1]=treap[now].ch[1]; 27 if(treap[now].rnd<treap[tot].rnd)//tot防在右下角 28 { 29 treap[now].ch[1]=tot; 30 update(tot); 31 update(now); 32 } 33 else 34 { 35 treap[now].ch[1]=0; 36 treap[tot].ch[0]=now; 37 treap[tot].fa=treap[now].fa; 38 treap[treap[now].fa].ch[treap[treap[now].fa].ch[1]==now?1:0]=tot; 39 update(now); 40 update(tot); 41 update(treap[tot].fa); 42 } 43 if(treap[tot].fa==0) root=tot; 44 return tot; 45 } 46 int merge(int x,int y) 47 { 48 if(x==0 or y==0) 49 return x+y; 50 if(treap[x].rnd>treap[y].rnd) 51 { 52 treap[y].ch[0]=merge(x,treap[y].ch[0]); 53 update(y); 54 return y; 55 } 56 else 57 { 58 treap[x].ch[1]=merge(treap[x].ch[1],y); 59 update(x); 60 return x; 61 } 62 } 63 void split(int now,int &x,int &y,int rank) 64 { 65 if(rank==0) 66 { 67 treap[now].fa=treap[y].fa; 68 x=0,y=now; 69 return ; 70 } 71 if(rank>=treap[now].size) 72 { 73 treap[now].fa=treap[x].fa; 74 x=now,y=0; 75 return ; 76 } 77 if(treap[treap[now].ch[0]].size>=rank) 78 { 79 treap[now].fa=treap[y].fa; 80 y=now; 81 split(treap[now].ch[0],x,treap[now].ch[0],rank); 82 update(now); 83 } 84 else if(treap[treap[now].ch[0]].size+treap[now].r-treap[now].l+1<=rank) 85 { 86 treap[now].fa=treap[x].fa; 87 x=now; 88 split(treap[now].ch[1],treap[now].ch[1],y,rank-(treap[treap[now].ch[0]].size+treap[now].r-treap[now].l+1)); 89 update(now); 90 } 91 else 92 { 93 int ori_fa=treap[now].fa; 94 int k=divide(now,rank-treap[treap[now].ch[0]].size-1); 95 int q=divide(k,1); 96 while(treap[now].fa!=ori_fa) 97 now=treap[now].fa; 98 split(now,x,y,rank); 99 } 100 } 101 void init() 102 { 103 root=++tot; 104 treap[root]=(ppp){0,0,rand(),n,1,n,0}; 105 f[n]=root; 106 } 107 int find(int p) 108 { 109 int fa=treap[p].fa; 110 if(fa==0 or p==0 or p==fa) return 0; 111 int son=treap[fa].ch[1]==p; 112 if(son) return treap[treap[fa].ch[0]].size+treap[fa].r-treap[fa].l+1+find(fa); 113 else return find(fa); 114 } 115 int getrank(int x) 116 { 117 map<int,int>::iterator it=f.lower_bound(x); 118 int p=it->second; 119 return find(p)+treap[treap[p].ch[0]].size+x-treap[p].l+1; 120 } 121 int main() 122 { 123 scanf("%d%d",&n,&m); 124 init(); 125 for(int i=1;i<=m;i++) 126 { 127 int opt,x1,y1; 128 scanf("%d%d",&opt,&x1); 129 x1-=a; 130 if(opt==1) 131 { 132 scanf("%d",&y1); 133 y1-=a; 134 int rank=getrank(x1); 135 printf("%d\n",rank); 136 a=rank; 137 int x=0,y=0,z=0; 138 split(root,x,y,rank-1); 139 split(y,z,y,1); 140 treap[z].l=treap[z].r=y1; 141 f[y1]=z; 142 f.erase(x1); 143 root=merge(merge(x,z),y); 144 } 145 else if(opt==2) 146 { 147 int rank=getrank(x1); 148 printf("%d\n",rank); 149 a=rank; 150 int x=0,y=0,z=0; 151 split(root,x,y,rank-1); 152 split(y,z,y,1); 153 root=merge(merge(z,x),y); 154 } 155 else if(opt==3) 156 { 157 int rank=getrank(x1); 158 printf("%d\n",rank); 159 a=rank; 160 int x=0,y=0,z=0; 161 split(root,x,y,rank-1); 162 split(y,z,y,1); 163 root=merge(merge(x,y),z); 164 } 165 else if(opt==4) 166 { 167 int x=0,y=0,z=0; 168 split(root,x,y,x1-1); 169 split(y,z,y,1); 170 a=treap[z].l; 171 printf("%d\n",a); 172 root=merge(merge(x,z),y); 173 } 174 } 175 return 0; 176 }