题解：P2801 教主的魔法

Binah_cyc · 2025-10-10 17:32:12 · 题解

看题解区没有讲单根号的做法的，我来发一个。直接冲到了最优解第二，仅次于神秘 O(q^2) 做法。

首先确保你能理解二分做法，随后考虑怎么消掉这只 \log。

我们枚举每一个块，算这个块对查询操作的贡献。正常二分做法是二分出一个最大的 p 满足 a_p < C-tag，但是我们当我们将两个散块修改之间的整块查询拿出来，将 C-tag 从小到大排序后可以发现，在 a 数组是有序的情况下，p 是单调不降的！所以我们就不需要二分了，可以直接用一个指针扫过去。排序可以用基数排序，复杂度就能做到线性了。

分析复杂度，共有 O(q) 个散块修改操作，每两个散块修改操作之间的查询操作处理复杂度 O(w_i+\sqrt n) 的，其中 w 是修改次数。又有 \displaystyle \sum _{i=1}^{\sqrt n} w_i=q，所以总复杂度是 O(q \sqrt n) 的。剩下的就是正常分块复杂度分析了。

不知道为什么，我的最优块长达到了惊人的 32768，可能是我处理整块的复杂度有点高。

代码略丑，谨慎观看。

// Problem: P2801 教主的魔法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2801
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
bool startmb;
constexpr int N=1<<20;
int n,q,ans[N];
struct node{int id,x;node(int _id,int _x){id=_id,x=_x;}node(){}}a[N];
struct Node{int id;char op;int l,r,x;}x[N];
int cyc[N];
vector<Node> vec[N];

//封装的基数排序
int cnt[257];
node bt[1<<20];
template<typename T>
void mysort(T startpoint,T endpoint)
{
    for(int i=0;i<=255;i++) cnt[i]=0;
    for(auto i=startpoint;i!=endpoint;i++) cnt[(*i).x&255]++;
    for(int i=0;i<=255;i++) cnt[i+1]+=cnt[i];
    for(int i=255;i>=1;i--) cnt[i]=cnt[i-1];
    cnt[0]=0;
    for(auto i=startpoint;i!=endpoint;i++) bt[cnt[(*i).x&255]++]=*i;
    for(auto i=startpoint;i!=endpoint;i++) *i=bt[i-startpoint];

    for(int i=0;i<=255;i++) cnt[i]=0;
    for(auto i=startpoint;i!=endpoint;i++) cnt[(*i).x>>8&255]++;
    for(int i=0;i<=255;i++) cnt[i+1]+=cnt[i];
    for(int i=255;i>=1;i--) cnt[i]=cnt[i-1];
    cnt[0]=0;
    for(auto i=startpoint;i!=endpoint;i++) bt[cnt[(*i).x>>8&255]++]=*i;
    for(auto i=startpoint;i!=endpoint;i++) *i=bt[i-startpoint];

    for(int i=0;i<=255;i++) cnt[i]=0;
    for(auto i=startpoint;i!=endpoint;i++) cnt[(*i).x>>16&255]++;
    for(int i=0;i<=255;i++) cnt[i+1]+=cnt[i];
    for(int i=255;i>=1;i--) cnt[i]=cnt[i-1];
    cnt[0]=0;
    for(auto i=startpoint;i!=endpoint;i++) bt[cnt[(*i).x>>16&255]++]=*i;
    for(auto i=startpoint;i!=endpoint;i++) *i=bt[i-startpoint];

    for(int i=0;i<=255;i++) cnt[i]=0;
    for(auto i=startpoint;i!=endpoint;i++) cnt[(*i).x>>24&255]++;
    for(int i=0;i<=255;i++) cnt[i+1]+=cnt[i];
    for(int i=255;i>=1;i--) cnt[i]=cnt[i-1];
    cnt[0]=0;
    for(auto i=startpoint;i!=endpoint;i++) bt[cnt[(*i).x>>24&255]++]=*i;
    for(auto i=startpoint;i!=endpoint;i++) *i=bt[i-startpoint];
}

constexpr int B=32768;
int ll[N/B],rl[N/B];//块的左右端点

//快读
char but[1<<22],*p1=but,*p2=but;
#define getchar() (p1==p2&&(p2=(p1=but)+fread(but,1,1<<22,stdin),p1==p2)?EOF:*p1++)
void read(int&x)
{
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
}
void read(char&x)
{
    x=getchar();
    while(!isupper(x)) x=getchar();
}

bool endmb;
main()
{
    cerr<<((&startmb-&endmb)/1024.0/1024)<<endl;
    cin.tie(0)->sync_with_stdio(false);
    read(n),read(q);
    for(int i=0;i<n;i++) read(a[i].x),a[i].id=i;
    for(int i=0;i<n;i++) rl[i/B]=i;
    for(int i=n-1;i>=0;i--) ll[i/B]=i;
    for(int i=0;i<q;i++) read(x[i].op),read(x[i].l),read(x[i].r),read(x[i].x),x[i].id=i,x[i].l--,x[i].r--;
    for(int i=0;i<q;i++) for(int k=x[i].l/B;k<=x[i].r/B;k++) cyc[k]++;
    for(int i=0;i<=n/B;i++) vec[i].reserve(cyc[i]);
    for(int i=0;i<q;i++)//把操作下放到块上
    {
        if(x[i].l/B==x[i].r/B) vec[x[i].l/B].emplace_back(x[i]);
        else
        {
            vec[x[i].l/B].emplace_back(Node{i,x[i].op,x[i].l,rl[x[i].l/B],x[i].x});
            vec[x[i].r/B].emplace_back(Node{i,x[i].op,ll[x[i].r/B],x[i].r,x[i].x});
            for(int k=x[i].l/B+1;k<x[i].r/B;k++) vec[k].emplace_back(Node{i,x[i].op,ll[k],rl[k],x[i].x});
        }
    }
    for(int k=0;k<=n/B;k++)//枚举每一块
    {
        int tag=0;
        mysort(a+ll[k],a+rl[k]+1);//排序
        vector<node> que;
        for(auto i=vec[k].begin();i!=vec[k].end();i++)
        {
            if((*i).op=='M')
            {
                if((*i).l==ll[k]&&(*i).r==rl[k]) {tag+=(*i).x;continue;}//整块修改直接打tag
                if(que.size())//处理整块查询
                {
                    mysort(que.begin(),que.end());//排序
                    int point=ll[k];
                    for(auto [id,x]:que)
                    {
                        while(point<=rl[k]&&a[point].x<x) point++;//指针
                        ans[id]+=rl[k]-point+1;
                    }
                    que.clear();
                }
                //散块修改用归并,保证有序的同时保证复杂度
                vector<node> xl,xr;
                xl.reserve(B),xr.reserve(B);
                for(int x=ll[k];x<=rl[k];x++) ((*i).l<=a[x].id&&a[x].id<=(*i).r?xr:xl).emplace_back(a[x]);
                for(auto&[id,x]:xr) x+=(*i).x;
                auto idl=xl.begin(),idr=xr.begin();
                auto idp=a+ll[k];
                while(idl!=xl.end()&&idr!=xr.end()) *idp++=*((*idl).x<=(*idr).x?idl:idr)++;
                while(idl!=xl.end()) *idp++=*idl++;
                while(idr!=xr.end()) *idp++=*idr++;
            }
            else
            {
                (*i).x=max(0,(*i).x-tag);//算C-tag
                if((*i).l==ll[k]&&(*i).r==rl[k]) que.emplace_back((*i).id,(*i).x);//整块查询后面再查
                else for(int x=ll[k];x<=rl[k];x++) if((*i).l<=a[x].id&&a[x].id<=(*i).r&&a[x].x>=(*i).x) ans[(*i).id]++;//散块查询直接查
            }
        }
        //最后把没查过的查完
        if(que.size())
        {
            mysort(que.begin(),que.end());
            int point=ll[k];
            for(auto [id,x]:que)
            {
                while(point<=rl[k]&&a[point].x<x) point++;
                ans[id]+=rl[k]-point+1;
            }
            que.clear();
        }
    }
    for(int i=0;i<q;i++) if(x[i].op=='A') cout<<ans[i]<<'\n';
    return 0;
}

最后感谢 zcz0263 大佬给出的这个做法，还帮我调题。orz