题解：P7334 [JRKSJ R1] 吊打

Quintus09 · 2025-11-25 15:05:55 · 题解

一道序列题，我用了延迟修改操作。

首先思考一下查询之间的关系。

注意到在平方后又出现了开方的话这两可以抵消。这样子之后的修改序列变成一堆根号后和一堆平方。

注意到 5 个开方就能让任何数变成 1，多个平方用神秘数学推导就能用快速幂解决。

#include<bits/stdc++.h>
#define int long long
#define ls o<<1
#define rs o<<1|1
using namespace std;
const int N=2e5+5,P=998244353;
int nxt[N],a[N],ans;
struct st{
    int opt,k;
};
vector < st > vec[N<<2];
char c[N];
inline int min(int x,int y){
    return x>y?y:x;
}
inline void pushin(int o,int opt,int k){
    if (opt==1){//刚开始想复杂了用了vector ...
        if (vec[o].empty()){
            vec[o].push_back({1,k});
        }else if(vec[o].back().opt==2){
            if (vec[o].back().k>=k){
                vec[o].back().k-=k;
                if (vec[o].back().k==0) vec[o].pop_back();
            }else{
                k-=vec[o].back().k;
                vec[o].pop_back();
                pushin(o,1,k);
            }
        }else if (vec[o].back().opt==1) vec[o].back().k+=k;
    }else if(opt==2){
        if (vec[o].empty()||vec[o].back().opt==1) vec[o].push_back({2,k});
        else if(vec[o].back().opt==2) vec[o].back().k+=k;
    }
}
inline void pushdown(int o){
    for (auto x:vec[o]){
        pushin(ls,x.opt,x.k);
        pushin(rs,x.opt,x.k);
    }
    vec[o].clear();
    return ;
}
inline void change(int l,int r,int x,int y,int opt,int o){
    if (x<=l&&r<=y){
        pushin(o,opt,1);
        return ;
    }
    pushdown(o);
    int mid=(l+r)>>1;
    if (x<=mid) change(l,mid,x,y,opt,ls);
    if (y>mid) change(mid+1,r,x,y,opt,rs);
    return ;
}
inline int qpow(int x,int k,int p){
    int ret=1;
    while (k){
        if (k&1) ret=ret*x%p;
        x=x*x%p,k>>=1;
    }
    return ret;
}
inline int get(int x,int opt,int k){
    if (opt==1){
        while (k--){
            x=sqrt(x);
            if (x==1) return 1;
        }
        return x;
    }
    if (opt==2) return qpow(x,qpow(2,k,P-1),P);//x^(2^k)%P=x^((2^k)%(P-1))%P
    return 0;
}
inline void getans(int l,int r,int o){
    if (l==r){
        int x=a[l];
        for (auto qwq:vec[o]) x=get(x,qwq.opt,qwq.k);
        ans+=x,ans%=P;
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(o);
    getans(l,mid,ls);
    getans(mid+1,r,rs);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,q;cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    while (q--){
        int opt,x,y;cin>>opt>>x>>y;
        change(1,n,x,y,opt,1);
    }
    getans(1,n,1);
    cout<<ans;
    return 0;
}