P2801 教主的魔法 (分块）

长度为\(n(n\le 1000000)\)的数组，\(q(q\le 3000)\) 次操作。修改操作即将某个区间的值增加某个不大于1000的值，查询操作即查询某个区间比C大于等于的数有多少个

我们用一个数组\(add[i]\)来表示第\(i\)段增量，如果查询区间完全包含第\(i\)段，那么就相当于是在原数组中查找大于等于\(C-add[i]\)的数，怎么找？排序后二分找。而对于左右不完整的那部分，直接暴力查询就可以。

对于修改操作。整段的直接增加增量，不完整的直接修改原数组，然后重新排序即可。

假设一段长度为\(t\) 则复杂度\(O(C(t+{nlog(t)\over t}))\)

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int a[N],b[N],be[N],L[N],R[N],add[N];

char op[3];

int l,r,x;

int n,m;

void change(int l,int r,int x){

    int p = be[l],q = be[r];

    if(p == q){

        for(int i=l;i<=r;i++)a[i] += x;

        for(int i=L[p];i<=R[p];i++)b[i] = a[i];

        sort(b+L[p],b+R[p]+1);

    }

    else{

        for(int i=p+1;i<=q-1;i++)add[i] += x;

        for(int i=l;i<=R[p];i++)a[i] += x;

        for(int i=L[p];i<=R[p];i++)b[i] = a[i];

        sort(b+L[p],b+R[p]+1);

        for(int i=L[q];i<=r;i++)a[i] += x;

        for(int i=L[q];i<=R[q];i++)b[i] = a[i];

        sort(b+L[q],b+R[q]+1);

    }

}

void solve(int l,int r,int x){

    int res = 0;

    int p = be[l],q = be[r];

    if(p == q){

        for(int i=l;i<=r;i++){

            if(a[i] + add[p] >= x)res++;

        }

        printf("%d\n",res);return;

    }

    else{

        for(int i=p+1;i<=q-1;i++){

            res += (R[i]-L[i]+1) - (lower_bound(b+L[i],b+R[i]+1,x-add[i]) - (b+L[i]));

        }

        for(int i=l;i<=R[p];i++)if(a[i] + add[p] >= x)res++;

        for(int i=L[q];i<=r;i++)if(a[i] + add[q] >= x)res++;

        printf("%d\n",res);return ;

    }

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i] = a[i];

    int t = sqrt(n);

    for(int i=1;i<=t;i++){

        L[i] = (i - 1) * t + 1;

        R[i] = i * t;

    }

    if(R[t] < n)t++,L[t] = R[t-1] + 1,R[t] = n;

    for(int i=1;i<=t;i++)for(int j=L[i];j<=R[i];j++)be[j] = i;

    for(int i=1;i<=t;i++){

        sort(b+L[i],b+R[i]+1);

    }

    while(m--){

        scanf("%s%d%d%d",op,&l,&r,&x);

        if(op[0] == 'M')change(l,r,x);

        else solve(l,r,x);

    }

    return 0;

}

巴特西

P2801 教主的魔法 (分块）

最新文章

热门文章