| WZJ的数据结构（负五） |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
请你设计一个数据结构，完成以下功能： 给定一个大小为N的整数组A，要求你回答执行M次操作。操作分两种： 操作1：每次操作给你l,r,v三个参数，求Al至Ar中值<=v的个数。 操作2：每次操作给你l,r,v三个参数，将Al至Ar中每个数的值+v。 |
|
输入
|
|
第一行为一个正整数N。
第二行为N个整数Ai。 第三行为一个正整数M。 接下来M行每行4个正整数t,l,r,v。若t=0表示操作1，t=1表示操作2。 |
|
输出
|
|
对每个操作1输出结果。
|
|
输入示例
|
|
10
1 2 1 1 2 1 1 2 2 1 4 0 1 10 2 0 1 10 1 1 3 5 1 0 1 10 1 |
|
输出示例
|
|
10
6 4 |
|
其他说明
|
|
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 }