已找到问题，是二分时忘了加标记
但是还是2wa2tle
```cpp
#include<cmath>
#include<cstdio>
#include<algorithm>
#define N 1000005
#define NB 1005
using namespace std;
int n,q,size,tot,left[NB],right[NB],belong[N],add[NB];
int tall[N],sall[N]; //sall是tall分块排序后的数组
inline void init()
{
scanf("%d%d",&n,&q);
size=sqrt(n);
int cnt=1;
for(int i=1;i<=n;i++)
belong[i]=i/size+1,scanf("%d",&tall[i]),sall[i]=tall[i];
while(cnt<=n)
{
left[++tot]=cnt;
right[tot]=min(cnt+size-1,n);
sort(sall+left[tot],sall+right[tot]+1);
cnt+=size;
}
}
void Modify(int l,int r,int v)
{
int lblock=belong[l],rblock=belong[r];
for(int i=lblock+1;i<rblock;i++) add[i]+=v;
if(lblock==rblock)
{
for(int i=l;i<=r;i++) tall[i]+=v;
for(int i=left[lblock];i<=right[lblock];i++) sall[i]=tall[i];
sort(sall+left[lblock],sall+right[lblock]+1);
}
else
{
if(l==left[lblock]) add[lblock]+=v;
else
{
for(int i=left[lblock];i<l;i++) sall[i]=tall[i];
for(int i=l;i<=right[lblock];i++) tall[i]+=v,sall[i]=tall[i];
sort(sall+left[lblock],sall+right[lblock]+1);
}
if(r==right[rblock]) add[rblock]+=v;
else
{
for(int i=left[rblock];i<=r;i++) tall[i]+=v,sall[i]=tall[i];
for(int i=r+1;i<=right[rblock];i++) sall[i]=tall[i];
sort(sall+left[rblock],sall+right[rblock]+1);
}
}
}
int LowerBound(int block,int bound)
{
int l=left[block],r=right[block],mid;
while(l<=r)
{
mid=(l+r)>>1;
if(sall[mid]+add[block]<bound) l=mid+1;
else r=mid-1;
}
return l;
}
void Query(int l,int r,int bound)
{
int ans=0;
int lblock=belong[l],rblock=belong[r];
for(int i=lblock+1;i<rblock;i++)
ans+=right[i]-(LowerBound(i,bound)-1);
if(lblock==rblock)
{
for(int i=l;i<=r;i++)
if(tall[i]+add[lblock]>=bound) ans++;
}
else
{
if(l==left[lblock])
ans+=right[lblock]-(LowerBound(lblock,bound)-1);
else
for(int i=l;i<=right[lblock];i++)
if(tall[i]+add[lblock]>=bound) ans++;
if(r==right[rblock])
ans+=right[rblock]-(LowerBound(rblock,bound)-1);
else
for(int i=left[rblock];i<=r;i++)
if(tall[i]+add[rblock]>=bound) ans++;
}
printf("%d\n",ans);
}
void work()
{
int L,R,T;char ch[5];
while(q--)
{
scanf("%s",ch);
scanf("%d%d%d",&L,&R,&T);
if(ch[0]=='M') Modify(L,R,T);
else Query(L,R,T);
}
}
int main()
{
init();
work();
return 0;
}
```
by Chorse @ 2018-04-07 19:47:40