【bzoj3343】教主的魔法

题解：
分块
整块打标记，左右两边暴力归并重构即可

//by sdfzchy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=1000010,mod=1e9+7;
int n,m;
inline int in()
{
    char tmp=getchar();
    int res=0,f=1;
    while((tmp<'0'||tmp>'9')&&tmp!='-')tmp=getchar();
    if(tmp=='-') f=-1,tmp=getchar();
    while(tmp>='0'&&tmp<='9')   res=(res<<1)+(res<<3)+(tmp^48),tmp=getchar();
    return res*f;
}
int bel[N],siz,col[N],a[N];
vector<int> v[100000];
char s[10];
void reset(int x,int pos)
{
    v[x].clear();
    int i=(x-1)*siz+1,j=pos;
    while(i<pos&&j<=x*siz)
    {
        if(a[i]<a[j]) v[x].push_back(a[i++]);
        else v[x].push_back(a[j++]);
    }
    while(i<pos) v[x].push_back(a[i++]);
    while(j<=x*siz) v[x].push_back(a[j++]);
}

void add(int l,int r,int w)
{
    for(int i=l;i<=min(r,bel[l]*siz);i++) a[i]+=w;
    reset(bel[l],l);
    if(bel[l]==bel[r]) return;
    for(int i=(bel[r]-1)*siz+1;i<=r;i++)  a[i]+=w;
    reset(bel[r],r);
    for(int i=bel[l]+1;i<=bel[r]-1;i++)   col[i]+=w;
}

int ask(int l,int r,int w)
{
    int ans=0;
    for(int i=l;i<=min(r,bel[l]*siz);i++) if(a[i]+col[bel[l]]>=w) ans++;
    if(bel[l]==bel[r]) return ans;
    for(int i=(bel[r]-1)*siz+1;i<=r;i++)  if(a[i]+col[bel[r]]>=w) ans++;
    for(int i=bel[l]+1;i<=bel[r]-1;i++)   ans+=siz-(lower_bound(v[i].begin(),v[i].end(),w-col[i])-v[i].begin());
    return ans;
}

int main()
{
    n=in(),m=in();
    siz=sqrt(n*log2(n));
    for(int i=1;i<=n;i++)
    {
        bel[i]=(i-1)/siz+1;
        a[i]=in();
        v[bel[i]].push_back(a[i]);
    }
    for(int i=1;i<=bel[n];i++) sort(v[i].begin(),v[i].end()); 
    for(int i=1,l,r,w;i<=m;i++)
    {
        scanf("%s",s);
        l=in(),r=in(),w=in();
        if(s[0]=='M') add(l,r,w);
        else printf("%d\n",ask(l,r,w));
    }
    return 0;
}