| 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，然后就没有然后了呢，注意二分。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxb=,inf=-1u>>;
int B[maxn],add[maxb],st[maxb],en[maxb],A[maxn],S[maxn],n,size,Q;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
int ans,cv;
void query(int L,int R){for(int i=L;i<=R;i++)if(S[i]+add[B[i]]<=cv)ans++;return;}
void queryb(int ql,int qr){
//printf("%d %d\n",ql,qr);
int M,s,L,R;
for(int b=ql;b<=qr;b++){
if(A[st[b]]+add[b]>cv) continue;
s=st[b];L=st[b];R=en[b]+;
while(L+<R){
//printf("%d %d\n",L,R);
M=L+R>>;
if(A[M]+add[b]<=cv) L=M;
else R=M;
}
ans+=L-s+;
} return;
}
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]]+);return;}
void addb(int L,int R){for(int b=L;b<=R;b++)add[b]+=cv;return;}
void init(){
n=read();int cnt=;size=(int)sqrt(1.1*n);
B[]=;
for(int i=;i<=n;i++){
S[i]=A[i]=read();
if(++cnt==size) B[i]=B[i-]+,cnt=;
else B[i]=B[i-];
if(!st[B[i]]) st[B[i]]=i;
en[B[i]]=i;
//printf("%d ",B[i]);
}//puts("");
Q=read();
for(int b=;b<=B[n];b++)sort(A+st[b],A+en[b]+);
return;
}
void work(){
int tp,ql,qr;
while(Q--){
tp=read();ql=read();qr=read();cv=read();
//printf("%d %d %d %d\n",tp,ql,qr,cv);
if(!tp){
ans=;
if(B[ql]==B[qr]) query(ql,qr);
else queryb(B[ql]+,B[qr]-),query(ql,en[B[ql]]),query(st[B[qr]],qr);
write(ans);ENT;
}
else{
if(B[ql]==B[qr]) addt(ql,qr);
else addb(B[ql]+,B[qr]-),addt(ql,en[B[ql]]),addt(st[B[qr]],qr);
}
}
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}