uva 12299 RMQ with Shifts

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=100000+5;
 6 int num[maxn<<4];
 7 int tmp[maxn];
 8 int indice[50];
 9 int tot;
10 void push_up(int rt)
11 {
12     num[rt]=min(num[rt<<1],num[rt<<1|1]);
13 }
14 void build(int l,int r,int rt)
15 {
16     if(l==r)
17     {
18         scanf("%d",&num[rt]);
19         tmp[tot++]=num[rt];
20         return ;
21     }
22     int m=(l+r)>>1;
23     build(l,m,rt<<1);
24     build(m+1,r,rt<<1|1);
25     push_up(rt);
26 }
27 void update(int x,int y,int l,int r,int rt)
28 {
29     if(l==r)
30     {
31         num[rt]=y;
32         return ;
33     }
34     int m=(l+r)>>1;
35     if(x<=m) update(x,y,l,m,rt<<1);
36     else update(x,y,m+1,r,rt<<1|1);
37     push_up(rt);
38 }
39 int query(int L,int R,int l,int r,int rt)
40 {
41     if(L<=l&&r<=R)
42     {
43         return num[rt];
44     }
45     int m=(l+r)>>1;
46     if(R<=m) return query(L,R,l,m,rt<<1);
47     if(L>m) return query(L,R,m+1,r,rt<<1|1);
48     int a=query(L,R,l,m,rt<<1);
49     int b=query(L,R,m+1,r,rt<<1|1);
50     return min(a,b);
51 }
52 int main()
53 {
54     int n,q;
55     scanf("%d%d",&n,&q);
56     tot=1;
57     build(1,n,1);
58     while(q--)
59     {
60         getchar();
61         int cnt=0;
62         char cmd;
63         cmd=getchar();
64         if(cmd=='q')
65         {
66             while(cmd!='(')
67                     cmd=getchar();
68             while(cmd!=')')
69                 scanf("%d%c",&indice[cnt++],&cmd);
70             printf("%d
",query(indice[0],indice[1],1,n,1));
71         }
72         else
73         {
74             while(cmd!='(')
75                     cmd=getchar();
76             while(cmd!=')')
77                 scanf("%d%c",&indice[cnt++],&cmd);
78             int temp=tmp[indice[0]];
79             for(int i=0;i<cnt-1;i++)
80                 tmp[indice[i]]=tmp[indice[i+1]];
81             tmp[indice[cnt-1]]=temp;
82             for(int i=0;i<cnt;i++)
83                 update(indice[i],tmp[indice[i]],1,n,1);
84         }
85     }
86     return 0;
87 }