洛谷-CF896C【模板】 Willem, Chtholly and Seniorious

题意翻译 【题面】 请你写一种奇怪的数据结构，支持： 1 l rxx ：将[l,r] 区间所有数加上x 2 l r x ：将[l,r] 区间所有数改成x 3 l r x ：输出将[l,r] 区间从小到大排序后的第x 个数是的多少(即区间第x 小，数字大小相同算多次，保证 1≤ x ≤ r−l+1 ) 4 l r x y ：输出[l,r] 区间每个数字的x 次方的和模yy 的值(即$({\sum }_{i=l}^r{a}_i^x)\mathrm{m}\mathrm{o}\mathrm{d}y$ 【输入格式】 这道题目的输入格式比较特殊，需要选手通过seed 自己生成输入数据。 输入一行四个整数$n,m,seed,v_{max}$ （$1\le n,m\le 10^5$,$0\le seed\le 10^9+7$ ,$1\le vmax\le 10^9,1\le vmax\le 10^9$） 其中n 表示数列长度，m 表示操作次数，后面两个用于生成输入数据。 数据生成的伪代码如下 其中上面的op指题面中提到的四个操作。 【输出格式】 对于每个操作3和4，输出一行仅一个数。

输入输出样例 输入 #1 10 10 7 9

输出 #1 2 1 0 3

输入 #2 10 10 9 9

输出 #2 1 1 3 3

解释：珂朵莉树模板，使一整段区间内的东西变得一样，数据随机的时候用

#include<bits/stdc++.h> #define IT set<node>::iterator using namespace std; typedef long long LL; const int MOD7 = 1e9 + 7; const int MOD9 = 1e9 + 9; const int imax_n = 1e5 + 7; struct node{ int l,r; mutable LL v; node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {} bool operator<(const node& o) const { return l < o.l; } }; LL pown(LL a, LL b, LL mod){ LL res = 1; LL ans = a % mod; while (b){ if (b&1) res = res * ans % mod; ans = ans * ans % mod; b>>=1; } return res; } set<node> s; 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; s.erase(it); s.insert(node(L, pos-1, V)); return s.insert(node(pos, R, V)).first; } void add(int l, int r, LL val){ IT itr = split(r+1),itl = split(l); for (; itl != itr; ++itl) itl->v += val; } void assign_val(int l, int r, LL val){ IT itr = split(r+1),itl = split(l); s.erase(itl, itr); s.insert(node(l, r, val)); } LL ranks(int l, int r, int k){ vector<pair<LL, int> > vp; IT itr = split(r+1),itl = split(l); vp.clear(); for (; itl != itr; ++itl) vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1)); sort(vp.begin(), vp.end()); for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it){ k -= it->second; if (k <= 0) return it->first; } return 0; } LL sum(int l, int r, int ex, int mod){ IT itr = split(r+1),itl = split(l); LL res = 0; for (; itl != itr; ++itl) res = (res + (LL)(itl->r - itl->l + 1) * pown(itl->v, LL(ex), LL(mod))) % mod; return res; } int n, m; LL seed, vmax; LL rd(){ LL ret = seed; seed = (seed * 7 + 13) % MOD7; return ret; } LL a[imax_n]; int main(){ cin>>n>>m>>seed>>vmax; for (int i=1; i<=n; ++i){ a[i] = (rd() % vmax) + 1; s.insert(node(i,i,a[i])); } s.insert(node(n+1, n+1, 0)); for (int i =1; i <= m; ++i){ int op = int(rd() % 4) + 1; int l = int(rd() % n) + 1; int r = int(rd() % n) + 1; if (l > r) swap(l,r); int x, y; if (op == 3) x = int(rd() % (r-l+1)) + 1; else x = int(rd() % vmax) +1; if (op == 4) y = int(rd() % vmax) + 1; if (op == 1) add(l, r, LL(x)); else if (op == 2) assign_val(l, r, LL(x)); else if (op == 3) cout<<ranks(l,r,x)<<endl; else cout<<sum(l,r,x,y)<<endl; } return 0; }