poj 3580 SuperMemo splay tree(重口味)

http://poj.org/problem?id=3580

给一个长度为N(N<10,000)的数列，要求支持6种操作： 1. 将区间[l,r]同时加一个数 2. 将区间[l,r]翻转 3.将区间[l,r]旋转若干次 4. 插入一个数 5. 删除一个数 6.求[l,r]的最小值

对于操作1,懒惰标记。

操作2,懒惰标记。如果不懂如何维护就看我上一篇题解...

操作3，交换两区间。因为两区间是相临的[a,b] [b+1,c]，那么先把a-1旋到树根，再旋b，再旋c，然后大家知道怎么做了吧....

什么？还不知道，在纸上画画吧...

操作4 & 5, 基本操作。

操作6，维护一个min值，维护方法和size相同。

trick:

1. 旋转若干次可能是很多次

2. 旋转0次

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 using namespace std;
  6 #define inf (1<<29)
  7 const int maxn = 200020;
  8 int nowsz , splaysz;
  9 struct node {
 10     int p,chd[2],mn,sz,rt,ad,val;
 11 }tree[maxn];
 12 inline void sc(int y,int x,int p) { tree[y].chd[p]=x;tree[x].p=y; }
 13 inline void pushdown(int x) {
 14     if(!x) return;
 15     if(tree[x].rt) {
 16         tree[x].rt ^= 1;
 17         swap(tree[x].chd[0] , tree[x].chd[1]);
 18         tree[tree[x].chd[0]].rt ^= 1;
 19         tree[tree[x].chd[1]].rt ^= 1;
 20     }
 21     if(tree[x].ad) {
 22         tree[x].mn += tree[x].ad;
 23         tree[x].val += tree[x].ad;
 24         tree[tree[x].chd[0]].ad += tree[x].ad;
 25         tree[tree[x].chd[1]].ad += tree[x].ad;
 26         tree[x].ad = 0;
 27     }
 28 }
 29 inline void update(int x) {
 30     if(!x) return;
 31     pushdown(tree[x].chd[0]);
 32     pushdown(tree[x].chd[1]);
 33     tree[x].mn = tree[x].val;
 34     tree[x].mn = min( tree[x].mn , min( tree[tree[x].chd[0]].mn , tree[tree[x].chd[1]].mn ) );
 35     tree[x].sz = tree[tree[x].chd[0]].sz + tree[tree[x].chd[1]].sz + 1;
 36 }
 37 inline void rot(int x) {
 38     int y = tree[x].p;
 39     int w = tree[y].chd[1] == x;
 40     sc(tree[y].p,x,tree[tree[y].p].chd[1]==y);
 41     sc(y,tree[x].chd[w^1],w);
 42     sc(x,y,w^1);
 43     update(y);
 44     update(x);
 45 }
 46 void dfs(int x) {
 47     if(!x) return;
 48     dfs(tree[x].p);
 49     pushdown(x);
 50 }
 51 void splay(int x,int rt=0) {
 52     if(x == rt || x == 0) return;
 53     dfs(x);
 54     while(tree[x].p!=rt) {
 55         int y = tree[x].p;
 56         int w = tree[y].chd[1]==x;
 57         if(tree[y].p != rt && tree[tree[y].p].chd[w]==y) rot(y);
 58         rot(x);
 59     }
 60 }
 61 int find(int val) {
 62     if(val == 0 || val >= nowsz) return 0;
 63     int x = tree[0].chd[1];
 64     while(1) {
 65         pushdown(x);
 66         int u = tree[x].chd[0];
 67         int v = tree[x].chd[1];
 68         if(tree[u].sz + 1 == val) return x;
 69         else if(tree[u].sz + 1 > val) x = u;
 70         else {
 71             x = v;
 72             val -= tree[u].sz + 1;
 73         }
 74     }
 75 }
 76 int query(int l,int r,char cmd[],int val=0) {
 77     int u = find(l) , v =find(r);
 78     if(u) splay(u);
 79     if(v) splay(v , u);
 80     if(!strcmp(cmd,"DELETE")) {
 81         if(v == 0) { tree[u].chd[1]=0; update(u); }
 82         else { tree[v].chd[0]=0; splay(v); }
 83         nowsz --;
 84     }
 85     else if(!strcmp(cmd,"INSERT")) {
 86         node &now = tree[splaysz];
 87         now.ad = now.rt = 0;
 88         now.mn = now.val = val;
 89         now.chd[0] = now.chd[1] = 0;
 90         if(v == 0 && u == 0) {
 91             //assert(tree[0].chd[1]==0);
 92             sc(0,splaysz,1);
 93         }
 94         else if(v == 0) sc(u,splaysz,1);
 95         else sc(v,splaysz,0);
 96         splaysz ++; nowsz ++;
 97         splay(splaysz-1);
 98     }
 99     else if(!strcmp(cmd,"REVOLVE")) {
100         int p = find(val);
101         if(p) splay(p,v);
102         sc(u,p,1);
103         sc(v,tree[p].chd[1],1);
104         sc(p,v,1);
105         update(v); update(p);
106     }
107     else {
108         int x = 0;
109         if(v == 0) x = tree[u].chd[1];
110         else {
111             x = tree[v].chd[0]; splay(v);
112         }
113         //assert(x);
114         int ans = tree[x].mn;
115         if(!strcmp(cmd,"ADD")) tree[x].ad += val;
116         if(!strcmp(cmd,"REVERSE")) tree[x].rt ^= 1;
117         splay(x , 0);
118         if(!strcmp(cmd,"MIN")) return ans;
119     }
120 }
121 int main() {
122     int n,m,x,y,z,ans;
123     char cmd[11];
124     tree[0].chd[0] = tree[0].chd[1] = tree[0].sz = 0;
125     tree[0].mn = inf;
126     scanf("%d" , &n);
127     for(int i=1;i<=n;i++) {
128         scanf("%d",&tree[i].val);
129         tree[i].chd[0] = tree[i].chd[1] = 0;
130         tree[i].mn = tree[i].val;
131         sc(i-1 , i , 1);
132         splay(i);
133     }
134     splaysz = nowsz = n + 1;
135     scanf("%d" , &m);
136     while(m--) {
137         scanf("%s" , cmd);
138         if(!strcmp(cmd,"ADD")) {
139             scanf("%d%d%d",&x,&y,&z);
140             query(x-1,y+1,cmd,z);
141         }
142         else if(!strcmp(cmd,"REVERSE")) {
143             scanf("%d%d",&x,&y);
144             query(x-1,y+1,cmd);
145         }
146         else if(!strcmp(cmd,"REVOLVE")) {
147             scanf("%d%d%d",&x,&y,&z);
148             z %= (y-x+1); if(!z) continue;
149             query(x-1,y-z,cmd,y);
150         }
151         else if(!strcmp(cmd,"INSERT")) {
152             scanf("%d%d",&x,&y);
153             query(x,x+1,cmd,y);
154         }
155         else if(!strcmp(cmd,"INSERT")) {
156             scanf("%d%d",&x,&y);
157             query(x,x+1,cmd,y);
158         }
159         else if(!strcmp(cmd,"MIN")) {
160             scanf("%d%d",&x,&y);
161             ans = query(x-1,y+1,cmd);
162             printf("%d
" , ans);
163         }
164         else {
165             scanf("%d",&x);
166             query(x-1,x+1,cmd);
167         }
168     }
169     return 0;
170 }