Parabola @ 2018-07-12 21:29:18
RT
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1000000+5;
int block[MAXN/1000+5][MAXN/1000+5];
int a[MAXN],wb[MAXN],wj[MAXN];
ll add[MAXN/1000+5];
int SIZE;
int n,m;
inline int read()
{
char ch;int x=0;
while(ch < '0' || ch >'9') ch=getchar();
while(ch >= '0' && ch <= '9') x=x*10+ch-'0',ch=read();
return x;
}
inline void init()
{
n=read();m=read();
SIZE=sqrt(n);
int j=0,b=0;
for(int i=0;i<n;i++)
{
a[i]=read();
block[b][j]=a[i];
wb[i]=b;
wj[i]=j;
if(++j == SIZE)
++b,j=0;
}
for(int i=0;i<b;i++)
sort(block[i],block[i]+SIZE);
if(j != 0)
sort(block[b],block[b]+j);
}
inline void change(int l,int r,int k)
{
int lb=wb[l],rb=wb[r];
if(lb == rb)
{
for(int i=l;i<=r;i++)
{
a[i]+=k;
block[wb[i]][wj[i]]+=k;
}
sort(block[lb],block[rb]+SIZE);
}
else
{
for(int i=l;i < (lb+1) * SIZE;i++)
{
a[i]+=k;
block[wb[i]][wj[i]]+=k;
}
for(int j=rb * SIZE;j <= r;j++)
{
a[j]+=k;
block[wb[j]][wj[j]]+=k;
}
for(int i=lb+1;i<rb;i++)
add[i]+=k;
}
}
inline char mygetchar()
{
char ch=getchar();
while(ch != 'A' && ch != 'M') ch=getchar();
return ch;
}
inline int query(int l,int r,int v)
{
int tot=0;
int lb=wb[l],rb=wb[r];
if(lb == rb)
{
for(int i=l;i<=r;i++)
if(a[i] >= v)
tot++;
return tot;
}
else
{
for(int i=l;i < (lb+1) * SIZE;i++)
if(a[i]+add[wb[i]] >= v)
tot++;
for(int j=rb * SIZE;j <= r;j++)
if(a[j]+add[wb[j]] >= v)
tot++;
for(int i=lb+1;i<rb;i++)
tot+=(SIZE-(lower_bound(block[i],block[i]+SIZE,v-add[i])-block[i]+1));
}
return tot;
}
int main()
{
ios::sync_with_stdio(false);
init();
while(m--)
{
char opt=mygetchar();
cout<<opt<<' ';
if(opt == 'M')
cout<<query(read(),read(),read())<<endl;
else
change(read(),read(),read());
}
return 0;
}
by Eqvpkbz @ 2018-07-12 21:59:26
感觉此题有树状数组即视感
by scallop @ 2018-07-12 22:06:14
你的代码是有很大错误的。 具体来说,一个函数实参的求值顺序是不确定 的。
by 向noip冲刺 @ 2018-07-12 22:18:33
应该这样
inline int read()
{
char ch = getchar();int x=0;
while(ch < '0' || ch >'9') ch=getchar();
while(ch >= '0' && ch <= '9') x=x*10+ch-'0',ch=read();
return x;
}
@白井黑子
by Dispwnl @ 2018-07-13 09:02:26
@白井黑子 您
ch=read();
是什么操作啊,不应该是getchar()
吗。。。难道是一种递归型的读入优化(逃
by Parabola @ 2018-07-13 11:18:15
打错了。。。
自己竟然没看到
我好蠢qwq