题解：P7334 [JRKSJ R1] 吊打

· · 题解

这题核心就一个点：开方可以抵消掉一次平方操作。这样我们只需要维护一个 pair<int,int>，第一个值代表开方的次数，第二个值代表平方的次数。这样的好处就是保证了计算顺序是先开方后平方。

每次遇到一个开方操作，就看看当前区间是否有平方操作。若有则将其减一，否则给开放操作加一。碰到平方操作则是直接给平方操作加一即可。

最后只需要查询每个叶节点的两种操作次数，然后先开方后平方。开方次数一定不会很多，因为到 1 后就停了，直接暴力。平方操作则是快速幂算 a[i]^{2^k}，其中 k 是平方操作。这一步可以通过费马小定理转化成 a[i]^{(2^k \bmod 998244352)}。

最后实现细节，这里实现甚至比普通线段树方便点。因为只查询叶节点，所以根本不用 pushup，只记录懒标记即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 998244353

int qpow(int a,int b,int p){
    if (a==0) return 0;
    int ret=1;
    while (b){
        if (b&1) ret=(ret*a)%p;
        b>>=1;
        a=(a*a)%p;
    }
    return ret;
}
int a[1000005],b[1000005];
pair<int,int> tag[4000005];
void maketag(int l,int r,int p,pair<int,int> num){
    if (tag[p].second>=num.first) tag[p].second+=num.second-num.first;
    else{
        num.first-=tag[p].second;
        tag[p].second=num.second;
        tag[p].first+=num.first;
    }
}
void pushdown(int l,int r,int p){
    int mid=(l+r)/2;
    maketag(l,mid,p*2,tag[p]);
    maketag(1+mid,r,p*2+1,tag[p]);
    tag[p]={0,0};
}
void update(int L,int R,pair<int,int> qwq,int l,int r,int p=1){
    if (l>R||L>r) return;
    if (L<=l&&r<=R) maketag(l,r,p,qwq);
    else{
        int mid=(l+r)/2;
        pushdown(l,r,p);
        update(L,R,qwq,l,mid,p*2);
        update(L,R,qwq,mid+1,r,p*2+1);
    }
}
pair<int,int> query(int P,int l,int r,int p=1){
    if (l==r) return tag[p];
    else{
        int mid=(l+r)/2;
        pushdown(l,r,p);
        if (P<=mid) return query(P,l,mid,p*2);
        return query(P,mid+1,r,p*2+1);
    }
}
unordered_map<int,int> mp;
signed main(){
    int n,q;
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    while (q--){
        int op,l,r;
        cin>>op>>l>>r;
        if (op==1) update(l,r,{1,0},1,n);
        if (op==2) update(l,r,{0,1},1,n);
    }
    for (int i=1;i<=n;i++){
        auto q=query(i,1,n);
        for (int j=1;j<=q.first&&a[i]!=1;j++) a[i]=sqrt(a[i]);
        a[i]=qpow(a[i],qpow(2,q.second,MOD-1),MOD);
        ans=(ans+a[i])%MOD;
    }
    cout<<ans;
}