cogs2320.[hzoi2015]聪聪的世界

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #define ll long long
  5 using namespace std;
  6 const int N=1000006;
  7 inline ll maxn(ll a,ll b){return a>b?a:b;}
  8 inline ll minn(ll a,ll b){return a<b?a:b;}
  9 
 10 int n,m;
 11 ll v[N];
 12 struct son
 13 {
 14     ll max,min;
 15 };
 16 son a[N*5];
 17 ll ji[N*5];
 18 void pushup(int x)
 19 {
 20     a[x].max=maxn(a[x<<1].max,a[x<<1|1].max);
 21     a[x].min=minn(a[x<<1].min,a[x<<1|1].min);
 22 }
 23 void pushdown(int x)
 24 {
 25     if(ji[x])
 26     {
 27         ji[x<<1]+=ji[x];
 28         ji[x<<1|1]+=ji[x];
 29         a[x<<1].max+=ji[x];
 30         a[x<<1].min+=ji[x];
 31         a[x<<1|1].min+=ji[x];
 32         a[x<<1|1].max+=ji[x];
 33         ji[x]=0;
 34     }
 35 }
 36 void build(int l,int r,int x)
 37 {
 38     if(l==r)
 39     {
 40         a[x].min=a[x].max=v[l];
 41         return ;
 42     }
 43     int mid=(l+r)>>1;
 44     build(l,mid,x<<1);
 45     build(mid+1,r,x<<1|1);
 46     pushup(x);
 47 }
 48 void addqu(int L,int R,ll c,int l,int r,int x)
 49 {
 50     if(L<=l&&r<=R)
 51     {
 52         a[x].max+=c;
 53         a[x].min+=c;
 54         ji[x]+=c;
 55         return ;
 56     }
 57     pushdown(x);
 58     int mid=(l+r)>>1;
 59     if(L<=mid)
 60       addqu(L,R,c,l,mid,x<<1);
 61     if(mid<R)
 62       addqu(L,R,c,mid+1,r,x<<1|1);
 63     pushup(x);
 64 }
 65 void adddian(int pos,ll c,int l,int r,int x)
 66 {
 67     if(l==r)
 68     {
 69         a[x].min+=c;
 70         a[x].max+=c;
 71         return ;
 72     }
 73     int mid=(l+r)>>1;
 74     pushdown(x);
 75     if(pos<=mid)
 76       adddian(pos,c,l,mid,x<<1);
 77     else
 78       adddian(pos,c,mid+1,r,x<<1|1);
 79     pushup(x);
 80 }
 81 ll qq(int pos,int l,int r,int x)
 82 {
 83     if(l==r)
 84       return a[x].max;
 85     pushdown(x);
 86     int mid=(l+r)>>1;
 87     if(pos<=mid)
 88       return qq(pos,l,mid,x<<1);
 89     else
 90       return qq(pos,mid+1,r,x<<1|1);
 91 }
 92 void Swap(int posx,int posy)
 93 {
 94     ll valx=qq(posx,1,n,1),valy=qq(posy,1,n,1);
 95     adddian(posx,valy-valx,1,n,1);
 96     adddian(posy,valx-valy,1,n,1);
 97 }
 98 ll zuoxiao(int L,int R,ll c,int l,int r,int x)
 99 {
100     if(L<=l&&r<=R&&a[x].min>c)
101       return -1;
102     if(l==r)
103         return a[x].max<c?a[x].max:-1;
104     int mid=(l+r)>>1;
105     ll temp;
106     pushdown(x);
107     if(R>mid)
108     {
109       temp=zuoxiao(L,R,c,mid+1,r,x<<1|1);
110       return temp==-1?zuoxiao(L,R,c,l,mid,x<<1):temp;
111     }
112     else
113       return zuoxiao(L,R,c,l,mid,x<<1);
114 }
115 ll zuoda(int L,int R,ll c,int l,int r,int x)
116 {
117     if(L<=l&&r<=R&&a[x].max<c)
118       return -1;
119     if(l==r)
120         return a[x].max>c?a[x].max:-1;
121     int mid=(l+r)>>1;
122     ll temp;
123     pushdown(x);
124     if(R>mid)
125     {
126       temp=zuoda(L,R,c,mid+1,r,x<<1|1);
127       return temp==-1?zuoda(L,R,c,l,mid,x<<1):temp;
128     }
129     else
130       return zuoda(L,R,c,l,mid,x<<1);
131 }
132 ll youxiao(int L,int R,ll c,int l,int r,int x)
133 {
134     if(L<=l&&r<=R&&a[x].min>c)
135       return -1;
136     if(l==r)
137         return a[x].max<c?a[x].max:-1;
138     int mid=(l+r)>>1;
139     ll temp;
140     pushdown(x);
141     if(L<=mid)
142     {
143       temp=youxiao(L,R,c,l,mid,x<<1);
144       return temp==-1?youxiao(L,R,c,mid+1,r,x<<1|1):temp;
145     }
146     else
147       return youxiao(L,R,c,mid+1,r,x<<1|1);
148 }
149 ll youda(int L,int R,ll c,int l,int r,int x)
150 {
151     if(L<=l&&r<=R&&a[x].max<c)
152       return -1;
153     if(l==r)
154         return a[x].max>c?a[x].max:-1;
155     int mid=(l+r)>>1;
156     ll temp;
157     pushdown(x);
158     if(L<=mid)
159     {
160       temp=youda(L,R,c,l,mid,x<<1);
161       return temp==-1?youda(L,R,c,mid+1,r,x<<1|1):temp;
162     }
163     else
164       return youda(L,R,c,mid+1,r,x<<1|1);
165 }
166 int main(){
167     //freopen("1.txt","r",stdin);
168     freopen("ccsworld.in","r",stdin);
169     freopen("ccsworld.out","w",stdout);
170     scanf("%d%d",&n,&m);
171     for(int i=1;i<=n;++i)
172       scanf("%lld",&v[i]);
173     
174     build(1,n,1);
175     while(m--)
176     {
177         int kk;
178         int x,y;
179         ll w;
180         scanf("%d%d",&kk,&x);
181         if(kk==1)printf("%lld
",zuoxiao(1,x,qq(x,1,n,1),1,n,1));
182         else if(kk==2)printf("%lld
",zuoda(1,x,qq(x,1,n,1),1,n,1));
183         else if(kk==3)printf("%lld
",youxiao(x,n,qq(x,1,n,1),1,n,1));
184         else if(kk==4)printf("%lld
",youda(x,n,qq(x,1,n,1),1,n,1));
185         else if(kk==5){scanf("%d",&y);Swap(x,y);}
186         else if(kk==6){scanf("%d%lld",&y,&w);addqu(x,y,w,1,n,1);}
187         else if(kk==7){scanf("%d%lld",&y,&w);addqu(x,y,-w,1,n,1);}
188     }
189     //while(1);
190     return 0;
191 }