loj#6278. 数列分块入门 2

#6278. 数列分块入门 2

简要题意：

　　给出一个长为

题解：

　　分块之后直接就分情况暴力了啊：

　　先枚举头，再枚举尾，中间的块之间二分求位置（当然了，预处理就要排序一下）

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<vector>
 7 using namespace std;
 8 int n,a[51000],ba[51000];
 9 int block,pos[51000];
10 vector<int> v[510];
11 void reset(int x)
12 {
13     v[x].clear();
14     for(int i=(x-1)*block+1;i<=x*block;i++)
15         v[x].push_back(a[i]);
16     sort(v[x].begin(),v[x].end());
17 }
18 void update(int l,int r,int c)
19 {
20     for(int i=l;i<=min(pos[l]*block,r);i++)a[i]+=c;
21     reset(pos[l]);
22     if(pos[l]!=pos[r])
23         for(int i=(pos[r]-1)*block+1;i<=r;i++)
24             a[i]+=c;
25     reset(pos[r]);
26     for(int i=pos[l]+1;i<=pos[r]-1;i++)ba[i]+=c;
27 }
28 void sol(int l,int r,int c)
29 {
30     int ans=0;
31     for(int i=l;i<=min(pos[l]*block,r);i++)if(a[i]+ba[pos[i]]<c)ans++;
32     if(pos[l]!=pos[r])
33         for(int i=(pos[r]-1)*block+1;i<=r;i++)
34             if(a[i]+ba[pos[i]]<c)
35                 ans++;
36     for(int i=pos[l]+1;i<=pos[r]-1;i++)
37     {
38         int x=c-ba[i];
39         ans+=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();
40     }
41     printf("%d
",ans);
42 }
43 int main()
44 {
45     memset(pos,0,sizeof(pos));memset(ba,0,sizeof(ba));
46     scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);
47     block=int(sqrt(n));for(int i=1;i<=n;i++){pos[i]=(i-1)/block+1;v[pos[i]].push_back(a[i]);}
48     for(int i=1;i<=pos[n];i++)sort(v[i].begin(),v[i].end());
49     for(int i=1;i<=n;i++)
50     {
51         int opt,l,r,c;
52         scanf("%d%d%d%d",&opt,&l,&r,&c);
53         if(opt==0)update(l,r,c);
54         else sol(l,r,c*c);
55     }
56     return 0;
57 }