題目描述：
給一個長度為N(N<10,000)的數列，要求支持6種操作： 1. 將區間[l,r]同時加一個數 2. 將區間[l,r]翻轉 3.將區間[l,r]旋轉若干次 4. 插入一個數 5. 刪除一個數 6.求[l,r]的最小值
吐槽：
1. 今天調了一下午+一晚上... 最后終于給拍出來了... debug的函數我在程序中保留了
2. 可真是累..... 4KB...
算法分析：
對于操作1,懶惰標記。
操作2,懶惰標記。如果不懂如何維護就看我上一篇題解...
操作3，交換兩區間。因為兩區間是相臨的[a,b] [b+1,c]，那么先把a-1旋到樹根，再旋b，再旋c，然后大家知道怎么做了吧....
什么？ 還不知道，在紙上畫畫吧...
操作4 & 5, 基本操作。
操作6， 維護一個min值，維護方法和size相同。
trick:
1. 旋轉若干次可能是很多次
2. 旋轉0次
3. 如果上面兩點注意到了，那么其他的錯誤都可以對拍出來......
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<cassert>
5 using namespace std;
6 const int N = 200005;
7 int nowsize ,splsize;
8 const int inf = ~0u>>2;
9 struct node {
10 int p,ch[2],mn,sz,rt,ad,val;
11 }tree[N];
12 template <typename T> inline void chkmin(T &a, T b){if(a>b) a=b;}
13 // debug
14 void OP(){
15 for(int i=1;i<splsize;i++)
16 cout<<i<<" chd: "<<tree[i].ch[0]<<" "<<tree[i].ch[1]<<" p: "<<tree[i].p<<" mn: "<<tree[i].val<<" "<<tree[i].mn<<" sz: "<<tree[i].sz<<" rt "<<tree[i].rt <<endl;
17 puts("");
18 }
19 //splay
20 inline void setchd(int y,int x,int p){
21 tree[y].ch[p] = x;
22 tree[x].p = y;
23 }
24 inline void pushdown(int x){
25 if(!x) return;
26 if(tree[x].rt){
27 tree[x].rt ^= 1;
28 swap(tree[x].ch[0],tree[x].ch[1]);
29 tree[tree[x].ch[0]].rt ^=1;
30 tree[tree[x].ch[1]].rt ^=1;
31 }
32 if(tree[x].ad){
33 tree[x].mn += tree[x].ad;
34 tree[x].val += tree[x].ad;
35 tree[tree[x].ch[0]].ad += tree[x].ad;
36 tree[tree[x].ch[1]].ad += tree[x].ad;
37 tree[x].ad = 0;
38 }
39 }
40 inline void upt(int x){
41 if(!x) return ;
42 pushdown(tree[x].ch[0]);
43 pushdown(tree[x].ch[1]);
44 tree[x].mn = tree[x].val;
45 chkmin(tree[x].mn , min(tree[tree[x].ch[0]].mn , tree[tree[x].ch[1]].mn));
46 tree[x].sz = tree[tree[x].ch[0]].sz + tree[tree[x].ch[1]].sz + 1;
47 }
48 void rot(int x){
49 int y = tree[x].p;
50 int p = tree[y].ch[1] == x;
51 setchd(tree[y].p, x, tree[tree[y].p].ch[1]==y);
52 setchd(y, tree[x].ch[p^1], p);
53 setchd(x, y ,p^1);
54 upt(y); upt(x);
55 }
56 void dfs(int x){
57 if(!x) return;
58 dfs(tree[x].p);
59 pushdown(x);
60 }
61 void splay(int x,int rt=0){
62 if(x == rt || x ==0) return;
63 dfs(x);
64 while(tree[x].p != rt){
65 int y = tree[x].p;
66 int p = tree[y].ch[1]==x;
67 if(tree[y].p != rt && p == (tree[tree[y].p].ch[1] == y)) rot(y);
68 rot(x);
69 }
70 }
71 // operator
72 int find(int val){
73 if(val ==0 || val >= nowsize) return 0;
74 int x = tree[0].ch[1];
75 while(1){
76 pushdown(x);
77 int l = tree[x].ch[0];
78 int r = tree[x].ch[1];
79 if(tree[l].sz + 1 == val) return x;
80 else if (tree[l].sz + 1 > val) x = l;
81 else {
82 x = r;
83 val -= tree[l].sz + 1;
84 }
85 }
86 }
87 int query(int l,int r,char cmd[],int val = 0){
88 int u = find(l), v = find(r);
89 if(u) splay(u,0);
90 if(v) splay(v,u);
91 if(!strcmp(cmd , "DELETE")){
92 if(v == 0) { tree[u].ch[1] = 0; upt(u); }
93 else { tree[v] .ch[0] = 0; splay(v); }
94 nowsize --;
95 }
96 else if(!strcmp(cmd , "INSERT")){
97 node &now = tree[splsize];
98 now.ad = now.rt = 0;
99 now.mn = now.val = val;
100 now.ch[0] = now.ch[1] = 0;
101 if(v == 0 && u ==0){
102 assert(tree[0].ch[1]==0);
103 setchd(0,splsize,1);
104 }
105 else if(v == 0 ) setchd(u,splsize,1);
106 else setchd(v,splsize,0);
107 splsize ++; nowsize++;
108 splay(splsize-1);
109 }
110 else if(!strcmp(cmd , "REVOLVE")){
111 int p = find(val);
112 if(p) splay(p,v);
113 setchd(u,p,1);
114 setchd(v,tree[p].ch[1],1);
115 setchd(p,v,1);
116 upt(v); upt(p);
117 }
118 else {
119 int x = 0;
120 if(v == 0) x = tree[u].ch[1] ;
121 else { x = tree[v].ch[0] ; splay(v);}
122 assert(x);
123 int ans = tree[x].mn;
124 if(!strcmp(cmd,"ADD")) tree[x].ad += val;
125 if(!strcmp(cmd,"REVERSE")) tree[x].rt ^=1;
126 splay(x,0);
127 if(!strcmp(cmd,"MIN")) return ans;
128 }
129 }
130 //main
131 int main(){
132 int n,m,x,y,z,ans;
133 tree[0].ch[0] = tree[0].ch[1] = tree[0].sz = 0;
134 tree[0].mn = inf;
135 scanf("%d",&n);
136 for(int i=1; i<=n; i++){
137 scanf("%d",&tree[i].val);
138 tree[i].ch[0] = tree[i].ch[1] = 0;
139 tree[i].mn = tree[i].val;
140 setchd(i-1,i,1);
141 splay(i);
142 }
143 splsize = nowsize = n+1;
144 char cmd[10];
145 scanf("%d",&m);
146 while(m--){
147 scanf("%s",cmd);
148 if(!strcmp(cmd,"ADD")){
149 scanf("%d%d%d",&x,&y,&z);
150 query(x-1,y+1,cmd,z);
151 }
152 else if(!strcmp(cmd,"REVERSE")){
153 scanf("%d%d",&x,&y);
154 query(x-1,y+1,cmd);
155 }
156 else if(!strcmp(cmd,"REVOLVE")){
157 scanf("%d%d%d",&x,&y,&z);
158 z %= (y-x+1); if(!z) continue;
159 query(x-1,y-z,cmd,y);
160 }
161 else if(!strcmp(cmd,"INSERT")){
162 scanf("%d%d",&x,&y);
163 query(x,x+1,cmd,y);
164 }
165 else if(!strcmp(cmd,"MIN")){
166 scanf("%d%d",&x,&y);
167 ans = query(x-1,y+1,cmd);
168 printf("%d\n",ans);
169 }
170 else {
171 scanf("%d",&x);
172 query(x-1,x+1,cmd);
173 }
174 }
175 }
176
posted on 2012-05-12 23:48
西月弦 閱讀(620)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告 、
經典題目