P2801 教主的魔法(分块)

nofind · 2019-09-30 14:34:11 · 个人记录

题意：https://www.luogu.org/problem/P2801

考虑分块,在块内排序,维护块的加法tag,修改时小块暴力改,大块维护tag(不用排序,块内大小关系不变),查询时散块暴力找,大块二分位置

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
const int maxt=1010;
int n,m,t,cnt;
int a[maxn],b[maxn],L[maxn],R[maxn],pos[maxn],tag[maxt];
inline char readc()
{
    char c=0;while(c!='M'&&c!='A')c=getchar();
    return c;
}
inline void change(int ql,int qr,int k)
{
    if(pos[ql]==pos[qr])
    {
        for(int i=ql;i<=qr;i++)a[i]+=k;
        for(int i=L[pos[ql]];i<=R[pos[qr]];i++)b[i]=a[i];
        sort(b+L[pos[ql]],b+R[pos[qr]]+1);
        return;
    }
    for(int i=ql;i<=R[pos[ql]];i++)a[i]+=k;
    for(int i=L[pos[ql]];i<=R[pos[ql]];i++)b[i]=a[i];
    sort(b+L[pos[ql]],b+R[pos[ql]]+1);
    for(int i=L[pos[qr]];i<=qr;i++)a[i]+=k;
    for(int i=L[pos[qr]];i<=R[pos[qr]];i++)b[i]=a[i];
    sort(b+L[pos[qr]],b+R[pos[qr]]+1);
    for(int i=pos[ql]+1;i<=pos[qr]-1;i++)tag[i]+=k;
}
inline int query(int ql,int qr,int k)
{
    int ans=0;
    if(pos[ql]==pos[qr])
    {
        for(int i=ql;i<=qr;i++)if(a[i]+tag[pos[ql]]>=k)ans++;
        return ans;
    }
    for(int i=ql;i<=R[pos[ql]];i++)if(tag[pos[ql]]+a[i]>=k)ans++;
    for(int i=L[pos[qr]];i<=qr;i++)if(tag[pos[qr]]+a[i]>=k)ans++;
    for(int i=pos[ql]+1;i<=pos[qr]-1;i++)
    {
        int l=L[i],r=R[i],res=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(b[mid]+tag[i]>=k)res=R[i]-mid+1,r=mid-1;
            else l=mid+1;
        }
        ans+=res;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);t=sqrt(n);cnt=n/t;
    if(n%t)cnt++;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    for(int i=1;i<=cnt;i++)L[i]=(i-1)*t+1,R[i]=i*t;
    R[cnt]=n;
    for(int i=1;i<=n;i++)pos[i]=(i-1)/t+1;
    for(int i=1;i<=cnt;i++)sort(b+L[i],b+R[i]+1);
    for(int i=1;i<=m;i++)
    {
        char op=readc();
        int l,r,k;scanf("%d%d%d",&l,&r,&k);
        if(op=='M')change(l,r,k);
        else printf("%d\n",query(l,r,k));
    }
    return 0;
}