Codeforces896 C. Willem, Chtholly and Seniorious（ODT）

题意：

给定n，m，seed，vmax
表示有一个长度为n的序列，m次操作，操作有4种：
(1,l,r,x)将[l,r]内的所有数加上x
(2,l,r,x)将[l,r]内的所有数赋值为x
(3,l,r,x)查询[l,r]内的第x大数
(4,l,r,x,y)计算sum(a(i)^x)%y，其中i属于[l,r]

数据生成方式：

def rnd():
    ret = seed
    seed = (seed * 7 + 13) mod 1000000007
    return ret

for i = 1 to n:
    a[i] = (rnd() mod vmax) + 1

for i = 1 to m:
    op = (rnd() mod 4) + 1
    l = (rnd() mod n) + 1
    r = (rnd() mod n) + 1
    if (l > r): 
         swap(l, r)
    if (op == 3):
        x = (rnd() mod (r - l + 1)) + 1
    else:
        x = (rnd() mod vmax) + 1
    if (op == 4):
        y = (rnd() mod vmax) + 1

解法：

ODT，所有操作都暴力处理就行了

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e5+5;
#define type int
#define It set<Node>::iterator
struct Node{
    int l,r;
    mutable type x;
    Node(int a,int b=0,type c=0){
        l=a,r=b,x=c;
    }
    bool operator<(const Node& a)const{
        return l<a.l;
    }
};
set<Node>s;
int n,m,seed,v_max;
//
int ppow(int a,int b,int mod){
    int ans=1%mod;a%=mod;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int rhd(){
    const static int mod=1e9+7;
    int ans=seed;
    seed=(seed*7+13)%mod;
    return ans;
}
//
It split(int pos){
    auto it=s.lower_bound(Node(pos));//不能用upper_bound,因为要找最左边的一个
    if(it!=s.end()&&it->l==pos){
        return it;
    }
    it--;
    int l=it->l,r=it->r;
    type x=it->x;
    s.erase(it);
    s.insert(Node(l,pos-1,x));
    return s.insert(Node(pos,r,x)).first;
}
void assign(int l,int r,type val){//区间赋值
    auto it2=split(r+1),it1=split(l);//要先找r,再找l
    s.erase(it1,it2);
    s.insert(Node(l,r,val));
}
void add(int l,int r, type val){//区间加法
    auto it2=split(r+1),it1=split(l);//要先找r,再找l
    for(;it1!=it2;it1++){
        it1->x+=val;
    }
}
int kth(int l,int r,int k){
    vector<pair<int,int> >temp;
    auto it2=split(r+1),it1=split(l);//要先找r,再找l
    for(;it1!=it2;it1++){
        temp.push_back({it1->x,it1->r-it1->l+1});
    }
    sort(temp.begin(),temp.end());
    for(auto i:temp){
        k-=i.second;
        if(k<=0)return i.first;
    }
    return -1;
}
int sum(int l,int r,int x,int y){
    int ans=0;
    auto it2=split(r+1),it1=split(l);//要先找r,再找l
    for(;it1!=it2;it1++){
        ans=(ans+ppow(it1->x,x,y)*(it1->r-it1->l+1)%y)%y;
    }
    return ans;
}
//
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>seed>>v_max;
    for(int i=1;i<=n;i++){
        int x=(rhd()%v_max)+1;
        s.insert(Node(i,i,x));
    }
    s.insert(Node(n+1,n+1,0));
    int op,l,r,x,y;
    for(int i=1;i<=m;i++){
        op=(rhd()%4)+1;
        l=(rhd()%n)+1;
        r=(rhd()%n)+1;
        if(l>r)swap(l,r);
        if(op==3)x=(rhd()%(r-l+1))+1;
        else x=(rhd()%v_max)+1;
        if(op==4)y=(rhd()%v_max)+1;
        //
        if(op==1){
            add(l,r,x);
        }else if(op==2){
            assign(l,r,x);
        }else if(op==3){
            int ans=kth(l,r,x);
            cout<<ans<<endl;
        }else if(op==4){
            int ans=sum(l,r,x,y);
            cout<<ans<<endl;
        }
    }
    return 0;
}

---