COJ 0995 WZJのデータ構造(負五)区間操作

WZJのデータ構造(マイナス5)
難易度レベル:C;運転時間制限:1000 ms;運行スペース制限:262144 KB;コード長制限:200000 B
試験問題の説明
データ構造を設計して、以下の機能を完成してください.
Nサイズの整数群Aが与えられ、M回の操作の実行に答えるように要求される.操作は2種類あります.
操作1:毎回操作してあなたにl,r,vの3つのパラメータをあげて、AlからArの中値<=vの個数を求めます.
操作2:毎回、l,r,vの3つのパラメータを操作し、AlからArの各数の値を＋vにします.
入力
第1の挙動は正の整数Nである.
第2の動作N個の整数Ai.
第3の挙動は正の整数Mである.
次に、M行は、行ごとに4つの正の整数t,l,r,vを有する.t=0が操作1を表し、t=1が操作2を表す.
しゅつりょく
操作1ごとに結果を出力します.
入力例
101 2 1 1 2 1 1 2 2 140 1 10 20 1 10 11 3 5 10 1 10 1
出力例
1064
その他の説明
1<=N<=200000
1<=M<=10000
1<=L<=R<=N
0<=Ai,v<=10^9
标题:ブロックを分けて、それぞれsort、それから次はありませんね、二分に注意してください.

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 #define PAU putchar(' ')
 8 #define ENT putchar('
')
 9 using namespace std;
10 const int maxn=200000+10,maxb=450,inf=-1u>>1;
11 int B[maxn],add[maxb],st[maxb],en[maxb],A[maxn],S[maxn],n,size,Q;
12 inline int read(){
13     int x=0,sig=1;char ch=getchar();
14     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
15     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
16     return x*=sig;
17 }
18 inline void write(int x){
19     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
20     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
21     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
22 }
23 int ans,cv;
24 void query(int L,int R){for(int i=L;i<=R;i++)if(S[i]+add[B[i]]<=cv)ans++;return;}
25 void queryb(int ql,int qr){
26     //printf("%d %d
",ql,qr);
27     int M,s,L,R;
28     for(int b=ql;b<=qr;b++){
29         if(A[st[b]]+add[b]>cv) continue;
30         s=st[b];L=st[b];R=en[b]+1;
31         while(L+1<R){
32             //printf("%d %d
",L,R);
33             M=L+R>>1;
34             if(A[M]+add[b]<=cv) L=M;
35             else R=M;
36         } 
37         ans+=L-s+1;
38     } return;
39 }
40 void addt(int L,int R){for(int i=L;i<=R;i++)S[i]+=cv;for(int i=st[B[L]];i<=en[B[L]];i++)A[i]=S[i];sort(A+st[B[L]],A+en[B[L]]+1);return;}
41 void addb(int L,int R){for(int b=L;b<=R;b++)add[b]+=cv;return;}
42 void init(){
43     n=read();int cnt=0;size=(int)sqrt(1.1*n);
44     B[0]=1;
45     for(int i=1;i<=n;i++){
46         S[i]=A[i]=read();
47         if(++cnt==size) B[i]=B[i-1]+1,cnt=0;
48         else B[i]=B[i-1];
49         if(!st[B[i]]) st[B[i]]=i;
50         en[B[i]]=i;
51         //printf("%d ",B[i]);
52     }//puts("");
53     Q=read();
54     for(int b=1;b<=B[n];b++)sort(A+st[b],A+en[b]+1);
55     return;
56 }
57 void work(){
58     int tp,ql,qr;
59     while(Q--){
60         tp=read();ql=read();qr=read();cv=read();
61         //printf("%d %d %d %d
",tp,ql,qr,cv);
62         if(!tp){
63             ans=0;
64             if(B[ql]==B[qr]) query(ql,qr);
65             else queryb(B[ql]+1,B[qr]-1),query(ql,en[B[ql]]),query(st[B[qr]],qr);
66             write(ans);ENT;
67         }
68         else{
69             if(B[ql]==B[qr]) addt(ql,qr);
70             else addb(B[ql]+1,B[qr]-1),addt(ql,en[B[ql]]),addt(st[B[qr]],qr);
71         }
72     }
73     return;
74 }
75 void print(){
76     return;
77 }
78 int main(){
79     init();work();print();return 0;
80 }