POJ 3580 SuperMemo

SuperMemo

Time Limit: 5000ms
Memory Limit: 65536KB
This problem will be judged on PKU. Original ID: 3580
64-bit integer IO format: %lld      Java class name: Main

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A1, A2, ... An}. Then the host performs a series of operations and queries on the sequence which consists:

  1. ADD x y D: Add D to each number in sub-sequence {Ax ... Ay}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
  2. REVERSE x y: reverse the sub-sequence {Ax ... Ay}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
  3. REVOLVE x y T: rotate sub-sequence {Ax ... Ay} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
  4. INSERT x P: insert P after Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
  5. DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
  6. MIN x y: query the participant what is the minimum number in sub-sequence {Ax ... Ay}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

 

Input

The first line contains n (n ≤ 100000).

The following n lines describe the sequence.

Then follows M (M ≤ 100000), the numbers of operations and queries.

The following M lines describe the operations and queries.

 

Output

For each "MIN" query, output the correct answer.

 

Sample Input

5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5

Sample Output

5

Source

POJ Founder Monthly Contest – 2008.04.13
 
解题：据说是灰常灰常重口味的splay的题目
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define KT ch[ch[root][1]][0]
  6 using namespace std;
  7 const int maxn = 200010;
  8 const int INF = ~0u>>2;
  9 struct SplayTree{
 10     int val[maxn],fa[maxn],ch[maxn][2],sz[maxn],root,tot;
 11     int flip[maxn],add[maxn],minv[maxn],seq[maxn];
 12     void newnode(int &x,int key,int f){
 13         x = ++tot;
 14         minv[x] = val[x] = key;
 15         ch[x][0] = ch[x][1] = 0;
 16         sz[x] = 1;
 17         fa[x] = f;
 18         add[x] = flip[x] = 0;
 19     }
 20     inline void pushdown(int x){
 21         if(!x) return;
 22         if(flip[x]){
 23             flip[ch[x][0]] ^= 1;
 24             flip[ch[x][1]] ^= 1;
 25             swap(ch[x][0],ch[x][1]);
 26             flip[x] = 0;
 27         }
 28         if(add[x]){
 29             if(ch[x][0]){
 30                 add[ch[x][0]] += add[x];
 31                 minv[ch[x][0]] += add[x];
 32                 val[ch[x][0]] += add[x];
 33             }
 34             if(ch[x][1]){
 35                 add[ch[x][1]] += add[x];
 36                 minv[ch[x][1]] += add[x];
 37                 val[ch[x][1]] += add[x];
 38             }
 39             add[x] = 0;
 40         }
 41     }
 42     inline void pushup(int x){
 43         minv[x] = min(val[x],min(minv[ch[x][0]],minv[ch[x][1]]));
 44         sz[x] = 1 + sz[ch[x][0]] + sz[ch[x][1]];
 45     }
 46     void rotate(int x,int kd){
 47         int y = fa[x];
 48         pushdown(y);
 49         pushdown(x);
 50         ch[y][kd^1] = ch[x][kd];
 51         fa[ch[x][kd]] = y;
 52         fa[x] = fa[y];
 53         ch[x][kd] = y;
 54         fa[y] = x;
 55         if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x;
 56         pushup(y);
 57     }
 58     void splay(int x,int goal){
 59         pushdown(x);
 60         while(fa[x] != goal){
 61             pushdown(fa[fa[x]]);
 62             pushdown(fa[x]);
 63             pushdown(x);
 64             if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]);
 65             else{
 66                 int y = fa[x],z = fa[y],s = (ch[z][0] == y);
 67                 if(x == ch[y][s]){
 68                     rotate(x,s^1);
 69                     rotate(x,s);
 70                 }else{
 71                     rotate(y,s);
 72                     rotate(x,s);
 73                 }
 74             }
 75         }
 76         pushup(x);
 77         if(!goal) root = x;
 78     }
 79     void build(int &x,int L,int R,int f){
 80         if(L > R) return;
 81         int mid = (L + R)>>1;
 82         newnode(x,seq[mid],f);
 83         build(ch[x][0],L,mid-1,x);
 84         build(ch[x][1],mid + 1,R,x);
 85         pushup(x);
 86     }
 87     void init(int n){
 88         val[0] = root = tot = 0;
 89         fa[0] = ch[0][0] = ch[0][1] = 0;
 90         flip[0] = add[0] = sz[0] = 0;
 91         minv[0] = INF;
 92         newnode(root,INF,0);
 93         newnode(ch[root][1],INF,root);
 94         sz[root] = 2;
 95         for(int i = 1; i <= n; ++i)
 96             scanf("%d",seq + i);
 97         build(KT,1,n,ch[root][1]);
 98         pushup(ch[root][1]);
 99         pushup(root);
100     }
101     void select(int k,int goal){
102         int x = root;
103         pushdown(x);
104         while(sz[ch[x][0]] + 1 != k){
105             if(k < sz[ch[x][0]] + 1) x = ch[x][0];
106             else{
107                 k -= sz[ch[x][0]] + 1;
108                 x = ch[x][1];
109             }
110             pushdown(x);
111         }
112         splay(x,goal);
113     }
114     void MIN(){
115         int x,y;
116         scanf("%d%d",&x,&y);
117         if(x > y) swap(x,y);
118         select(x - 1 + 1,0);
119         select(y + 1 + 1,root);
120         printf("%d
",minv[KT]);
121     }
122     void Add(){
123         int x,y,d;
124         scanf("%d%d%d",&x,&y,&d);
125         if(x > y) swap(x,y);
126         select(x - 1 + 1,0);
127         select(y + 1 + 1,root);
128         add[KT] += d;
129         val[KT] += d;
130         minv[KT] += d;
131     }
132     void reverse(){
133         int x,y;
134         scanf("%d%d",&x,&y);
135         if(x > y) swap(x,y);
136         select(x - 1 + 1,0);
137         select(y + 1 + 1,root);
138         flip[KT] ^= 1;
139     }
140     void insert(){
141         int x,p;
142         scanf("%d%d",&x,&p);
143         select(x + 1,0);
144         select(x + 2,root);
145         newnode(KT,p,ch[root][1]);
146         pushup(ch[root][1]);
147         pushup(root);
148     }
149     void remove(){
150         int x;
151         scanf("%d",&x);
152         select(x - 1 + 1,0);
153         select(x + 1 + 1,root);
154         KT = 0;
155         pushup(ch[root][1]);
156         pushup(root);
157     }
158     void revolve(){
159         int x,y,t;
160         scanf("%d%d%d",&x,&y,&t);
161         if(x > y) swap(x,y);
162         t %= (y - x + 1);
163         t = (t + y - x + 1)%(y - x + 1);
164         int l = y - t + 1,r = y;
165         if(!t) return;
166         select(l - 1 + 1,0);
167         select(r + 1 + 1,root);
168         int tmp = KT;
169         KT = 0;
170         pushup(ch[root][1]);
171         pushup(root);
172         select(x - 1 + 1,0);
173         select(x + 1,root);//右子树现在是x开始的区间了
174         KT = tmp;
175         fa[KT] = ch[root][1];
176         pushup(ch[root][1]);
177         pushup(root);
178     }
179 }spt;
180 int main(){
181     int n,m;
182     char op[10];
183     scanf("%d",&n);
184     spt.init(n);
185     scanf("%d",&m);
186     while(m--){
187         scanf("%s",op);
188         if(op[0] == 'A') spt.Add();
189         else if(op[0] == 'M') spt.MIN();
190         else if(op[0] == 'I') spt.insert();
191         else if(op[0] == 'D') spt.remove();
192         else if(op[0] == 'R' && op[3] == 'E') spt.reverse();
193         else if(op[0] == 'R' && op[3] == 'O') spt.revolve();
194     }
195     return 0;
196 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/crackpotisback/p/4877208.html