odt

Inker · 2019-03-26 21:26:26 · 个人记录

#include<cstdio>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long dnt;
struct node{
    int l,r;
    mutable dnt v;
    bool operator < (const node &b)const
    {
        return l<b.l;
    }
};

typedef set<node>::iterator iter;

set<node>se;
int n,m,vmax,seed;
iter split(int pos)
{
    iter it=se.lower_bound((node){pos,-1,0});
    if(it!=se.end()&&it->l==pos)return it;
    --it;
    int l=it->l,r=it->r;
    dnt v=it->v;
    se.erase(it);
    se.insert((node){l,pos-1,v});
    return se.insert((node){pos,r,v}).first;
}

void assign(int l,int r,dnt v)
{
    iter rr=split(r+1),ll=split(l);
    se.erase(ll,rr);
    se.insert((node){l,r,v});
}

void plu(int l,int r,dnt vv)
{
    iter rr=split(r+1),ll=split(l);
    for(;ll!=rr;ll++){
        ll->v=ll->v + vv;
    }
}
struct pr{
    dnt v;
    int l;
    bool operator < (const pr &b){
        return v<b.v;
    }
};
vector <pr> vc;
dnt quk(int l,int r,int k)
{
    iter rr=split(r+1),ll=split(l);
    vc.clear();
    for(;ll!=rr;ll++){
        vc.push_back((pr){ll->v,(ll->r - ll->l + 1)});
    }
    sort(vc.begin(),vc.end());
    for(int i=0;i<vc.size();i++){
        k-=vc[i].l;
        if(k<=0)return vc[i].v;
    }
    return 114514;
}
dnt mpow(dnt a,int b,int mod)
{
    dnt c=1;
    a=a%mod;
    for(;b;b>>=1,a=a*a%mod){
        if(b&1)c=a*c%mod;
    }
    return c;
}
dnt qpw(int l,int r,int x,int y)
{
    iter rr=split(r+1),ll=split(l);
    dnt res=0;
    for(;ll!=rr;ll++){
        res=(res+mpow(ll->v,x,y)*(ll->r - ll->l +1))%y;
    }
    return res;
}

int Rand(){
    int ret=seed;
    seed=(seed*7ll+13)%1000000007;
    return ret;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&seed,&vmax);
    for(int i=1;i<=n;i++){
        int xx=Rand()%vmax+1;
        se.insert((node){i,i,xx});
    }
    int op,l,r,x,y;
    for(int i=1;i<=m;i++){
        op=Rand()%4+1;
        l=Rand()%n+1;
        r=Rand()%n+1;
        if(l>r)swap(l,r);
        if(op==3)x=(Rand()%(r-l+1))+1;
        else x=Rand()%vmax+1;
        if(op==4) y=Rand()%vmax+1;
        if(op==1) plu(l,r,x);
        if(op==2) assign(l,r,x);
        if(op==3) {
            printf("%lld\n",quk(l,r,x));
        }
        if(op==4){
            printf("%lld\n",qpw(l,r,x,y));
        }
    }
    return 0;
}