样例都过不了，第二次询问还是返回的2

Chorse @ 2018-04-06 17:38:39

#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(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]<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(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

已找到问题，是二分时忘了加标记 但是还是2wa2tle

#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;
}