分块

Q1：

1：给区间[a,b]的所有数都增加X

2：询问第i个数是什么？

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 #define ll long long 
 6 inline void read(ll &k)
 7 {
 8     char c=getchar();int f=1;k=0;
 9     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
10     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
11     k*=f;
12 }
13 const int maxn=100100;
14 ll n,a[maxn],k[400],x,tmp,y,z,block,ex,q,bl[maxn];
15 inline void update(int l,int r,int add)
16 {
17     for (int i=bl[l]+1;i<=bl[r]-1;i++)k[i]+=add;
18     for (int i=l;i<=block*bl[l];i++)a[i]+=add;
19     if (bl[l]!=bl[r])
20     for (int i=block*(bl[r]-1)+1;i<=r;i++)a[i]+=add;
21 }
22 inline ll query(int x)
23 {
24     return k[x/block+1]+a[x];
25 }
26 int main()
27 {
28     read(n);
29     block=(int)sqrt(n);
30     ex=n-block*block;
31     for (int i=1;i<=n;i++)
32     bl[i]=(i-1)/block+1;
33     for (int i=1;i<=n;i++)
34     {
35         read(a[i]);
36     }
37     read(q);
38     for (int i=1;i<=q;i++)
39     {
40         read(tmp);
41         if (tmp==1)
42         {
43             read(x);read(y);read(z);
44             update(x,y,z);
45         }
46         if (tmp==2)
47         {
48             read(x);
49             printf("%lld
",query(x));
50         }
51     }
52 }

View Code

http://codevs.cn/problem/4927/

有n个数和5种操作

add a b c：把区间[a,b]内的所有数都增加c

set a b c：把区间[a,b]内的所有数都设为c

sum a b：查询区间[a,b]的区间和

max a b：查询区间[a,b]的最大值

min a b：查询区间[a,b]的最小值

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #define ll long long 
  5 #define max MAX
  6 #define min MIN
  7 inline ll minn(ll a,ll b)
  8 {
  9     return a<b?a:b;
 10 }
 11 inline ll maxx(ll a,ll b)
 12 {
 13     return a>b?a:b;
 14 }
 15 inline void read(ll &k)
 16 {
 17     char c=getchar();ll f=1;k=0;
 18     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
 19     while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
 20     k*=f;
 21 }
 22 const ll inf=1ll << 62;
 23 const ll maxn=100100;
 24 ll m,xx,yy,mi,ma,n,c,tmp,block,q,a[maxn],delta[4000],bl[maxn],set[maxn],sum[maxn],min[maxn],max[maxn];
 25 bool is_set[4000]={0};
 26 char s[200];
 27 inline void update1(ll l,ll r,ll add)
 28 {
 29     for (ll i=bl[l]+1;i<=bl[r]-1;i++)
 30     delta[i]+=add;
 31     //
 32     if (bl[l]==bl[r])
 33     {
 34         if (is_set[bl[l]])
 35         {
 36             is_set[bl[l]]=0;
 37             for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)
 38             a[i]=delta[bl[l]]+set[bl[l]];
 39             for (ll i=l;i<=r;i++)
 40             a[i]+=add;
 41             delta[bl[l]]=0;
 42             sum[bl[l]]=0;
 43             for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)
 44             sum[bl[l]]+=a[i];
 45             //
 46             mi=inf,ma=-inf;
 47             for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
 48             min[bl[l]]=mi;
 49             max[bl[l]]=ma;
 50             //
 51         }
 52         else
 53         {
 54             for (ll i=l;i<=r;i++)a[i]+=add;
 55             for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)
 56             a[i]+=delta[bl[l]];
 57             delta[bl[l]]=0;
 58             sum[bl[l]]=0;
 59             for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)
 60             sum[bl[l]]+=a[i];
 61             //
 62             mi=inf,ma=-inf;
 63             for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
 64             min[bl[l]]=mi;
 65             max[bl[l]]=ma;
 66             //
 67         }
 68         return;
 69     }
 70     //l
 71     if (is_set[bl[l]])
 72     {
 73         is_set[bl[l]]=0;
 74         for (ll i=l;i<=block*bl[l];i++)
 75         a[i]=set[bl[l]]+add+delta[bl[l]];
 76         for (ll i=(bl[l]-1)*block+1;i<l;i++)
 77         a[i]=set[bl[l]]+delta[bl[l]];
 78         sum[bl[l]]=0;
 79         for (ll i=(bl[l]-1)*block+1;i<=bl[l]*block;i++)
 80         sum[bl[l]]+=a[i];
 81         delta[bl[l]]=0;
 82         //
 83         mi=inf,ma=-inf;
 84         for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
 85         min[bl[l]]=mi;
 86         max[bl[l]]=ma;
 87         //
 88     }
 89     else 
 90     {
 91         for (ll i=l;i<=block*bl[l];i++)
 92         a[i]+=add+delta[bl[l]];
 93         for (ll i=block*(bl[l]-1)+1;i<l;i++)///////////////
 94         a[i]+=delta[bl[l]];
 95         sum[bl[l]]=0;
 96         for (ll i=(bl[l]-1)*block+1;i<=bl[l]*block;i++)
 97         sum[bl[l]]+=a[i];
 98 //        sum[bl[l]]+=delta[bl[l]]*block;
 99         delta[bl[l]]=0;
100         //
101         mi=inf,ma=-inf;
102         for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
103         min[bl[l]]=mi;
104         max[bl[l]]=ma;
105         //
106     }
107     //r
108     if (is_set[bl[r]])
109     {
110         is_set[bl[r]]=0;
111         for (ll i=block*(bl[r]-1)+1;i<=r;i++)
112         a[i]=set[bl[r]]+add+delta[bl[r]];
113         for (ll i=r+1;i<=bl[r]*block;i++)
114         a[i]=set[bl[r]]+delta[bl[r]];
115         sum[bl[r]]=0;
116         for (ll i=(bl[r]-1)*block+1;i<=bl[r]*block;i++)
117         sum[bl[r]]+=a[i];
118         delta[bl[r]]=0;
119         //
120         mi=inf,ma=-inf;
121         for (ll i=(bl[r]-1)*block+1;i<=block*bl[r];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
122         min[bl[r]]=mi;
123         max[bl[r]]=ma;
124         //
125     }
126     else 
127     {
128         for (ll i=block*(bl[r]-1)+1;i<=r;i++)
129         a[i]+=add+delta[bl[r]];
130         for (ll i=r+1;i<=bl[r]*block;i++)
131         a[i]+=delta[bl[r]];
132         sum[bl[r]]=0;
133         for (ll i=(bl[r]-1)*block+1;i<=bl[r]*block;i++)
134         sum[bl[r]]+=a[i];
135         delta[bl[r]]=0;
136         //
137         mi=inf,ma=-inf;
138         for (ll i=(bl[r]-1)*block+1;i<=block*bl[r];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
139         min[bl[r]]=mi;
140         max[bl[r]]=ma;
141         //
142     }
143 }
144 inline void update2(ll l,ll r,ll sett)
145 {
146     for (ll i=bl[l]+1;i<=bl[r]-1;i++)
147     is_set[i]=1,set[i]=sett,delta[i]=0;
148     //
149     if (bl[l]==bl[r])
150     {
151         if (is_set[bl[l]])
152         {
153             is_set[bl[l]]=0;
154             for (ll i=block*(bl[l]-1)+1;i<=block*bl[l];i++)
155             a[i]=set[bl[l]]+delta[bl[l]];
156         }
157         else
158         {
159             for (ll i=block*(bl[l]-1)+1;i<=block*bl[l];i++)
160             a[i]+=delta[bl[l]];
161         }
162         delta[bl[l]]=0;
163         for (ll i=l;i<=r;i++)a[i]=sett;
164         sum[bl[l]]=0;
165         for (ll i=block*(bl[l]-1)+1;i<=block*bl[l];i++)
166         sum[bl[l]]+=a[i];
167         //
168         mi=inf,ma=-inf;
169         for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
170         min[bl[l]]=mi;
171         max[bl[l]]=ma;
172         //
173         return;
174     }
175     //l
176     if (is_set[bl[l]])
177     {
178         is_set[bl[l]]=0;
179         for (ll i=block*(bl[l]-1)+1;i<=block*bl[l];i++)
180         a[i]=set[bl[l]]+delta[bl[l]];
181     }
182     else 
183     {
184         for (ll i=block*(bl[l]-1)+1;i<=block*bl[l];i++)
185         a[i]+=delta[bl[l]];
186     }
187     delta[bl[l]]=0;
188     for (ll i=l;i<=block*bl[l];i++)a[i]=sett;
189     sum[bl[l]]=0;
190     for (ll i=block*(bl[l]-1)+1;i<=block*bl[l];i++)
191     sum[bl[l]]+=a[i];
192     //
193     mi=inf,ma=-inf;
194     for (ll i=(bl[l]-1)*block+1;i<=block*bl[l];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
195     min[bl[l]]=mi;
196     max[bl[l]]=ma;
197     //
198     //r
199     if (is_set[bl[r]])
200     {
201         is_set[bl[r]]=0;
202         for (ll i=block*(bl[r]-1)+1;i<=block*bl[r];i++)
203         a[i]=set[bl[r]]+delta[bl[r]];
204     }
205     else 
206     {
207         for (ll i=block*(bl[r]-1)+1;i<=block*bl[r];i++)
208         a[i]+=delta[bl[r]];
209     }
210     delta[bl[r]]=0;
211     for (ll i=block*(bl[r]-1)+1;i<=r;i++)a[i]=sett;
212     sum[bl[r]]=0;
213     for (ll i=block*(bl[r]-1)+1;i<=block*bl[r];i++)
214     sum[bl[r]]+=a[i];
215     //
216     mi=inf,ma=-inf;
217     for (ll i=(bl[r]-1)*block+1;i<=block*bl[r];i++)mi=minn(mi,a[i]),ma=maxx(ma,a[i]);
218     min[bl[r]]=mi;
219     max[bl[r]]=ma;
220     //
221 }
222 inline ll querysum(ll l,ll r)
223 {
224     ll ans=0;
225     if (l==r)
226     {
227         if (is_set[bl[l]])return set[bl[l]]+delta[bl[l]];
228         return a[l]+delta[bl[l]];
229     }
230     if (bl[l]==bl[r])
231     {
232         if (is_set[bl[l]])return (set[bl[l]]+delta[bl[l]])*(r-l+1);
233         for (ll i=l;i<=r;i++)
234         ans+=a[i]+delta[bl[l]];
235         return ans;
236     }
237     for (ll i=bl[l]+1;i<=bl[r]-1;i++)
238     if (is_set[i])ans+=(set[i]+delta[i])*block;
239     else ans+=sum[i]+delta[i]*block;
240     //l
241     if (is_set[bl[l]])ans+=(set[bl[l]]+delta[bl[l]])*(bl[l]*block-l+1);
242     else for (ll i=l;i<=bl[l]*block;i++)ans+=a[i]+delta[bl[l]];
243     //r
244     if (is_set[bl[r]])ans+=(set[bl[r]]+delta[bl[r]])*(r-((bl[r]-1)*block+1)+1);
245     else for (ll i=(bl[r]-1)*block+1;i<=r;i++)ans+=a[i]+delta[bl[r]];
246     return ans;
247 }
248 inline ll querymax(ll l,ll r)
249 {
250     if (l==r)return querysum(l,r);
251     if (bl[l]==bl[r])
252     {
253         if (is_set[bl[l]])return set[bl[l]]+delta[bl[l]];
254         ma=-inf;
255         for (ll i=l;i<=r;i++)ma=maxx(ma,a[i]);
256         return ma+delta[bl[l]];
257     }
258     ll ans=-inf;
259     for (ll i=bl[l]+1;i<=bl[r]-1;i++)
260     if (is_set[i])ans=maxx(ans,set[i]+delta[i]);
261     else ans=maxx(ans,delta[i]+max[i]);
262     //l
263     if (is_set[bl[l]])ans=maxx(ans,set[bl[l]]+delta[bl[l]]);
264     else for (ll i=l;i<=bl[l]*block;i++)ans=maxx(ans,delta[bl[l]]+a[i]);
265     //r
266     if (is_set[bl[r]])ans=maxx(ans,set[bl[r]]+delta[bl[r]]);
267     else for (ll i=block*(bl[r]-1)+1;i<=r;i++)ans=maxx(ans,delta[bl[r]]+a[i]);
268     return ans;
269 }
270 inline ll querymin(ll l,ll r)
271 {
272     if (l==r)return querysum(l,r);
273     if (bl[l]==bl[r])
274     {
275         if (is_set[bl[l]])return set[bl[l]]+delta[bl[l]];
276         mi=inf;
277         for (ll i=l;i<=r;i++)mi=minn(mi,a[i]);
278         return mi+delta[bl[l]];
279     }
280     ll ans=inf;
281     for (ll i=bl[l]+1;i<=bl[r]-1;i++)
282     if (is_set[i])ans=minn(ans,set[i]+delta[i]);
283     else ans=minn(ans,delta[i]+min[i]);
284     //l
285     if (is_set[bl[l]])ans=minn(ans,set[bl[l]]+delta[bl[l]]);
286     else for (ll i=l;i<=bl[l]*block;i++)ans=minn(ans,delta[bl[l]]+a[i]);
287     //r
288     if (is_set[bl[r]])ans=minn(ans,set[bl[r]]+delta[bl[r]]);
289     else for (ll i=block*(bl[r]-1)+1;i<=r;i++)ans=minn(ans,delta[bl[r]]+a[i]);
290     return ans;
291 }
292 int main()
293 {
294     memset(is_set,0,sizeof(is_set));
295     read(n);read(m);
296     block=(ll)sqrt(n);
297     for (int i=1;i<=n;i++)
298     bl[i]=(i-1)/block+1;
299     for (int i=1;i<=n;i++)read(a[i]);
300     for (int i=1;i<=n;i++)sum[bl[i]]+=a[i];
301     for (int i=1;i<=n;i++)
302     {
303         if (bl[i]!=bl[i-1])mi=inf,ma=-inf;
304         mi=minn(mi,a[i]);
305         ma=maxx(ma,a[i]);
306         max[bl[i]]=ma;
307         min[bl[i]]=mi;
308     }
309     for (int i=1;i<=m;i++)
310     {
311         scanf("%s%lld%lld",s,&xx,&yy);
312         if (s[0]=='a')
313         {
314             read(c);
315             update1(xx,yy,c);
316         }
317         if (s[0]=='s'&&s[1]=='e')
318         {
319             read(c);
320             update2(xx,yy,c);
321         }
322         if (s[0]=='s'&&s[1]=='u')printf("%lld
",querysum(xx,yy));
323         if (s[0]=='m'&&s[1]=='a')printf("%lld
",querymax(xx,yy));
324         if (s[0]=='m'&&s[1]=='i')printf("%lld
",querymin(xx,yy));
325     }
326 }

View Code