B_1168 @ 2018-04-19 16:05:30
代码如下求助qwq
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010,maxs=1001;
int a[maxn],b[maxn],be[maxn],l[maxs],r[maxs],tag[maxs],n,m,len,num;
inline void reb(int L,int R){
for(int i=L;i<=R;i++)b[i]=a[i];
sort(b+L,b+R+1);
}
inline int find(int x,int w){
int ll=l[x],rr=r[x],mid;
while(ll<=rr){
mid=(ll+rr)/2;
if(b[mid]<w) ll=mid+1;
else rr=mid-1;
}
return r[x]-ll+1;
}
inline void query(int L,int R,int c){
int ans=0;
if(be[L]==be[R]){
for(int i=L;i<=R;i++)if(a[i]+tag[be[i]]>=c)ans++;
printf("%d\n",ans);
}
else{
for(int i=L;i<=r[be[L]];i++)if(a[i]+tag[be[i]]>=c)ans++;
for(int i=l[be[R]];i<=R;i++)if(a[i]+tag[be[i]]>=c)ans++;
for(int i=be[L]+1;i<=be[R]-1;i++){
ans+=find(i,c-tag[i]);
}
printf("%d\n",ans);
}
}
inline void modify(int L,int R,int w){
if(be[L]==be[R]){
for(int i=L;i<=R;i++)a[i]+=w;
reb(l[be[L]],r[be[R]]);
}
else{
for(int i=L;i<=r[be[L]];i++){
a[i]=w;
}
reb(l[be[L]],r[be[L]]);
for(int i=l[be[R]];i<=R;i++){
a[i]=w;
}
reb(l[be[R]],r[be[R]]);
for(int i=be[L]+1;i<=be[R]-1;i++)tag[i]+=w;
}
}
int main(){
scanf("%d%d",&n,&m);
int len=sqrt(n);
int num=n/len;
if (n%len) num++;
for(int i=1;i<=num;i++)l[i]=(i-1)*len+1,r[i]=i*len;
for(int i=1;i<=n;i++)be[i]=(i-1)/len+1;
for(register int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
for(int i=1;i<=num;i++){
reb(l[i],r[i]);
}
while(m--){
int x,y,z;
char tmp;
scanf("%c%d%d%d",&tmp,&x,&y,&z);
if(tmp=='A')query(x,y,z);
if(tmp=='Z')modify(x,y,z);
}
}
by 夏色祭 @ 2018-04-19 17:48:00
@stewart 别读一个字符,读字符数组
by 半仙胡小桃 @ 2018-04-19 17:51:30
读一个字符貌似不行