CF 896 C. Willem, Chtholly and Seniorious(珂朵莉树模板)

Problem - C - Codeforces

大意：给出一个区间 ， 要求进行四种操作 ， 区间加 ， 区间第k大 ， 区间推平 ， 区间求和。

珂朵莉树模板题 ， 练手即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;struct node{int l , r;mutable int v;node(int l , int r = 0 , int v = 0) : l(l), r(r), v(v){}bool operator < (const node &a) const {return l < a.l;}
};set<node>s;set<node>::iterator split(int pos){set<node>::iterator it = s.lower_bound(node(pos));if(it != s.end() && it->l == pos) {return it;}it--;if (it->r < pos) return s.end();int l = it->l;int r = it->r;int v = it->v;s.erase(it);s.insert(node(l , pos - 1 , v));return s.insert(node(pos , r , v)).first;
}inline int qp(int x , int y , int p){int res = 1 % p;x = x % p; while(y){if(y & 1) res = res * x % p;x = x * x % p;y >>= 1;}return res;
}void assign(int l , int r , int x) {set<node>::iterator itr = split(r + 1) , itl = split(l);s.erase(itl , itr);s.insert(node(l , r , x));
}void add(int l , int r , int x){set<node>::iterator itr = split(r + 1) , itl = split(l);for(auto i = itl ; i != itr ; i ++)  i->v += x;
}inline int kth(int l , int r , int x){vector<PII>v;set<node>::iterator itr = split(r + 1) , itl = split(l);for(auto i = itl ; i != itr ; i ++) v.emplace_back(i->v , i->r - i->l + 1);sort(v.begin() , v.end());for(auto [val , num] : v){if(x > num) x -= num;else return val;}
}inline int sum(int l , int r , int x , int p){int res = 0;set<node>::iterator itr = split(r + 1) , itl = split(l);for(auto i = itl ; i != itr ; i ++){res = (res + qp(i->v , x , p) * (i->r - i->l + 1) % p) % p;}return res;
}int n , m , seed , vmax , op , a[N] , x , y , l , r;inline int rnd(){int res = seed;seed = (seed * 7 + 13) % mod;return res;
}signed main(){IOScin >> n >> m >> seed >> vmax;for(int i = 1 ; i <= n ; i ++){a[i] = (rnd() % vmax) + 1;s.insert(node{i , i , a[i]});}for(int i = 1 ; i <= m ; i ++){op = rnd() % 4 + 1;l = rnd() % n + 1;r = rnd() % n + 1;if(l > r) 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) assign(l , r , x);if(op == 3) cout << kth(l , r , x) << "\n";if(op == 4) cout << sum(l , r , x , y) << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);