算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    给一个长度为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 西月弦 阅读(594) 评论(0)  编辑 收藏 引用 所属分类: 解题报告经典题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理