CF896C Willem, Chtholly and Seniorious

╰半橙微兮° 2023-10-11 11:19 35阅读 0赞

[题目][Link 1]

珂朵莉树板子，我觉得[洛谷题解][Link 2]讲的就很不错

粘一下自己的板子

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define ST std::set<node>::iterator
    inline int ksm(int a,int b,int mod) {
        int S=1;
        for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;
        return S;
    }
    const int MOD7=1000000007;
    struct node {
        int l,r;
        mutable LL v;
        bool operator<(const node &A) const{if(l==A.l) return r<A.r;return l<A.l;}
    };
    struct Seg{LL v;int t;}a[100005];
    inline int cmp(const Seg &A,const Seg &B) {return A.v<B.v;}
    std::set<node> s;
    int n,m,seed,vmax;
    inline int rnd() {
        int ret=seed;
        seed=(seed*7ll+13)%MOD7;
        return ret;
    }
    inline ST split(int pos) {
        ST it=s.lower_bound((node){pos,-1,0});
        if(it!=s.end()&&it->l==pos) return it;
        --it;
        int L=it->l,R=it->r;LL t=it->v;
        s.erase(it);
        s.insert((node){L,pos-1,t});
        return s.insert((node){pos,R,t}).first;
    }
    inline void pia(int l,int r,int v) {
        ST itl=split(l),itr=split(r+1);
        s.erase(itl,itr);
        s.insert((node){l,r,(LL)v});
    }
    inline void add(int l,int r,int t) {
        ST itl=split(l),itr=split(r+1);
        for(;itl!=itr;++itl) itl->v+=t;
    }
    inline int calc(int l,int r,int x,int mod) {
        ST itl=split(l),itr=split(r+1);
        int ans=0;
        for(;itl!=itr;++itl) 
            ans=(ans+1ll*ksm(itl->v%mod,x,mod)*(itl->r-itl->l+1)%mod)%mod;
        return ans; 
    }
    inline LL rk(int l,int r,int k) {
        ST itl=split(l),itr=split(r+1);
        int cnt=0;
        for(;itl!=itr;++itl) a[++cnt].v=itl->v,a[cnt].t=itl->r-itl->l+1;
        std::sort(a+1,a+cnt+1,cmp);
        for(re int i=1;i<=cnt;i++) {
            if(k-a[i].t>0) {k-=a[i].t;continue;}
            return a[i].v;
        }
    }
    int main() {
        //scanf("%d%d%lld%lld",&n,&m,&seed,&vmax);
        std::cin>>n>>m>>seed>>vmax;
        for(re int i=1;i<=n;i++) s.insert((node){i,i,rnd()%vmax+1});
        int op,l,r,x,y;
        for(re int i=1;i<=m;i++) {
            op=rnd()%4+1;
            l=rnd()%n+1;r=rnd()%n+1;
            if(l>r) std::swap(l,r);
            if(op==3) x=rnd()%(r-l+1)+1;
                else x=rnd()%vmax+1;
            if(op==4) y=rnd()%vmax+1;
            if(op==1) add(l,r,x);
            if(op==2) pia(l,r,x);
            if(op==4) printf("%d\n",calc(l,r,x,y));
            if(op==3) std::cout<<rk(l,r,x),putchar(10);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11366316.html

[Link 1]: https://www.luogu.org/problem/CF896C
[Link 2]: https://www.luogu.org/problemnew/solution/CF896C