欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019.01.19 codeforces 896C.Willem, Chtholly and Seniorious(ODT)

程序员文章站 2024-02-24 11:19:46
...

传送门
ODTODT出处(万恶之源)
题目简述:

  1. 区间赋值
  2. 区间加
  3. 区间所有数k次方和
  4. 区间第k小

思路:直接上ODTODT
不会的点这里
代码:

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
const int N=1e5+5;
typedef long long ll;
typedef pair<ll,int> pli;
vector<pli>q;
struct Node{
    int l,r;
    mutable ll v;
    Node(int l_,int r_=-1,ll v_=0):l(l_),r(r_),v(v_){}
    friend inline bool operator<(const Node&a,const Node&b){return a.l<b.l;}
};
set<Node>S;
typedef set<Node>::iterator It;
inline It split(int pos){
    It it=S.lower_bound(Node(pos));
    if(it!=S.end()&&it->l==pos)return it;
    --it;
    int l=it->l,r=it->r;
    ll v=it->v;
    return S.erase(it),S.insert(Node(l,pos-1,v)),S.insert(Node(pos,r,v)).first;
}
inline int ksm(ll a,int p,ll mod){int ret=1;a%=mod;for(;p;p>>=1,a=a*a%mod)if(p&1)ret=a*ret%mod;return ret;}
inline void assign(int l,int r,ll v){
    It R=split(r+1),L=split(l);
    return S.erase(L,R),(void)S.insert(Node(l,r,v));
}
inline void add(int l,int r,ll v){
    It L=split(l),R=split(r+1);
    for(It it=L;it!=R;++it)(it->v)+=v;
}
inline ll Rank(int l,int r,int kth){
    It R=split(r+1),L=split(l);
    q.clear();
    for(It it=L;it!=R;++it)q.push_back(pli(it->v,it->r-it->l+1));
    sort(q.begin(),q.end());
    for(ri i=0;i<q.size();++i){
        kth-=q[i].second;
        if(kth<=0)return q[i].first;
    }
    return -1;
}
inline ll query(int l,int r,int k,ll mod){
    ll ret=0;
    It L=split(l),R=split(r+1);
    for(It it=L;it!=R;++it)ret=(ret+(ll)(it->r-it->l+1)*ksm(it->v,k,mod)%mod)%mod;
    return ret;
}
int n,m,vmax,seed;
inline int rd(){
  int ret=seed;
  seed=(7ll*seed+13)%1000000007;
  return ret;
}
int main(){
    n=read(),m=read(),seed=read(),vmax=read();
    for(ri i=1;i<=n;++i)S.insert(Node(i,i,rd()%vmax+1));
    for(ri i=1,op,L,R,x,y;i<=m;++i){
        op=rd()%4+1,L=rd()%n+1,R=rd()%n+1;
        if(L>R)swap(L,R);
        if(op==3)x=rd()%(R-L+1)+1;
        else x=rd()%vmax+1;
        if(op==4)y=rd()%vmax+1;
        switch(op){
            case 1:add(L,R,x);break;
            case 2:assign(L,R,x);break;
            case 3:cout<<Rank(L,R,x)<<'\n';break;
            default:cout<<query(L,R,x,y)<<'\n';
        }
    }
    return 0;
}
相关标签: 数据结构