Libreoj 6278. 数列分块入门 2

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=5e4+5;
 5 vectorv[50005];
 6 ll a[N],tag[N],blg[N],L[N],R[N],block,tot;
 7 void resort(int n)
 8 {
 9     v[n].clear();
10     for(int i=L[n];i<=R[n];i++)v[n].push_back(a[i]);
11     sort(v[n].begin(),v[n].end());
12 }
13 void build(int n)
14 {
15     block=sqrt(n);
16     tot=n/block;
17     if(n%block)tot++;
18     
19     for(int i=1;i<=n;i++)
20     {
21         blg[i]=(i-1)/block+1;
22         v[blg[i]].push_back(a[i]);
23     }
24     for(int i=1;i<=tot;i++)
25     {
26         L[i]=(i-1)*block+1;
27         R[i]=i*block;
28         sort(v[i].begin(),v[i].end());
29     }
30     R[tot]=n;
31 }
32 void update(int l,int r,ll k)
33 {
34     if(blg[l]==blg[r])
35     {
36         for(int i=l;i<=r;i++)a[i]+=k;
37         resort(blg[l]);
38         return;
39     }
40     for(int i=l;i<=R[blg[l]];i++)a[i]+=k;
41     for(int i=L[blg[r]];i<=r;i++)a[i]+=k;
42     for(int i=blg[l]+1;i<=blg[r]-1;i++)tag[i]+=k;
43     resort(blg[l]);
44     resort(blg[r]);
45 }
46 int query(int l,int r,ll c)
47 {
48     int ans=0;
49     if(blg[l]==blg[r])
50     {
51         for(int i=l;i<=r;i++)
52         if(a[i]+tag[blg[l]];
53         return ans;
54     }
55     for(int i=l;i<=R[blg[l]];i++)
56     if(a[i]+tag[blg[l]];
57     
58     for(int i=L[blg[r]];i<=r;i++)        
59     if(a[i]+tag[blg[r]];
60     
61     for(int i=blg[l]+1;i<=blg[r]-1;i++)
62     ans+=lower_bound(v[i].begin(),v[i].end(),c-tag[i])-v[i].begin();    
63     
64     return ans;
65 }
66 int main()
67 {
68     int n,opt,l,r;ll k;
69     scanf("%d",&n);
70     for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
71     build(n);
72     for(int i=1;i<=n;i++)
73     {
74         scanf("%d%d%d%lld",&opt,&l,&r,&k);
75         if(opt)printf("%d\n",query(l,r,1ll*k*k));
76         else update(l,r,k);
77     }
78     return 0;
79 }