Willem, Chtholly and Seniorious题解
题目传送：题目
题面翻译
【题面】
请你写一种奇怪的数据结构，支持：
- 1 l r x ：将 [l,r] 区间所有数加上 x
- 2 l r x ：将 [l,r] 区间所有数改成 x
- 3 l r x ：输出将 [l,r] 区间从小到大排序后的第 x 个数是的多少(即区间第$x$ 小，数字大小相同算多次，保证 1\leq x \leq r-l+1 )
- 4 l r x y ：输出 [l,r] 区间每个数字的 x 次方的和模 y 的值(即(\sum^r_{i=l}a_i^x ) \mod y )
【输入格式】
这道题目的输入格式比较特殊，需要选手通过$seed$ 自己生成输入数据。
输入一行四个整数 n,m,seed,v_{max} （ 1\leq n,m\leq 10^{5} ,0\leq seed \leq 10^{9}+7 ,1\leq vmax \leq 10^{9} ）
其中 n 表示数列长度， m 表示操作次数，后面两个用于生成输入数据。
思路分析
这题是珂朵莉树的起源，珂朵莉树详见
1.区间加
将每个节点都加一遍就行了。
void add(int l,int r,ll v){
IT itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++){
itl->v+=v;
}
}
2.区间第k小
也是非常暴力的思想，将每个节点存在 vector 里再 sort 一下。
ll Rank(int l,int r,int k){
IT itr=split(r+1),itl=split(l);
vector<PL> vt;
for(;itl!=itr;itl++){
int L=itl->l,R=itl->r;
ll V=itl->v;
vt.push_back(PL(V,R-L+1));
}
sort(vt.begin(),vt.end());
for(VIT it=vt.begin();it!=vt.end();++it){
k-=it->second;
if(k<=0){
return it->first;
}
}
}
3.区间x次方和
每个节点x次方加起来就行了，不要忘记乘以区间长度，还有就是对每个节点的值先模一个，不然会爆 $ long long $（还是非常暴力）
ll sum(int l,int r,int x,int mod)
{
IT itr = split(r+1),itl=split(l);
ll res=0;
for (;itl!=itr;itl++){
int L=itl->l,R=itl->r;
ll V=itl->v;
V=V%mod;
res =(res+(ll)(R-L+1)*bp(V,ll(x),ll(mod)))%mod;
}
return res;
}
至此这道题就完成了，当然还有线段树的做法，实现比珂朵莉树难很多。
代码实现
#include<bits/stdc++.h>
#define IT set<node>::iterator
#define PL pair<long long,int>//first记录区间值,second记录区间长度
#define VIT vector<PL>::iterator
using namespace std;
typedef long long ll;
const int N=1145141;
const int sM=1e9+7;
struct node{
int l,r;
mutable ll v;
node(int L,int R=0,ll V=0):l(L),r(R),v(V){}
bool operator <(const node& a)const{return l<a.l;}
};
inline ll bp(ll a,ll b,ll M) {
if (b==0) return 1;
ll res = bp(a,b/2,M);
if (b % 2)
return(res*res)%M*a%M;
else
return (res*res)%M;
}
set<node> chtolly;
IT split(int pos){ //分裂
IT it=chtolly.lower_bound(node(pos));
if(it !=chtolly.end()&&it->l==pos){return it;}
it--;
int l=it->l,r=it->r;
ll v=it->v;
chtolly.erase(it);
chtolly.insert(node(l,pos-1,v));
return chtolly.insert(node(pos,r,v)).first;
}
void assign(int l,int r,int v){//推平
IT itr=split(r+1),itl=split(l);
chtolly.erase(itl,itr);
chtolly.insert(node(l,r,v));
}
void add(int l,int r,ll v){//区间加
IT itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++){
itl->v+=v;
}
}
ll Rank(int l,int r,int k){//第k小
IT itr=split(r+1),itl=split(l);
vector<PL> vt;
for(;itl!=itr;itl++){
int L=itl->l,R=itl->r;
ll V=itl->v;
vt.push_back(PL(V,R-L+1));
}
sort(vt.begin(),vt.end());
for(VIT it=vt.begin();it!=vt.end();++it){
k-=it->second;
if(k<=0){
return it->first;
}
}
}
ll sum(int l,int r,int x,int mod)//求和
{
IT itr = split(r+1),itl=split(l);
ll res=0;
for (;itl!=itr;itl++){
int L=itl->l,R=itl->r;
ll V=itl->v;
V=V%mod;
res =(res+(ll)(R-L+1)*bp(V,ll(x),ll(mod)))%mod;
}
return res;
}
int n,m;
ll seed,vmax,a[N];
ll rnd(){
ll ret=seed;
seed=(seed*7+13)%sM;
return ret;
}
int main(){
cin>>n>>m>>seed>>vmax;
for(int i=1;i<=n;i++){
a[i]=(rnd()%vmax)+1;
chtolly.insert(node(i,i,a[i]));
}
chtolly.insert(node(n+1,n+1,0));
while(m--){
int l,r,x,y,op;
op=int(rnd()%4)+1;
l=int(rnd()%n)+1;
r=int(rnd()%n)+1;
if(l>r) {
swap(l,r);
}
if(op==3){
x=int(rnd()%(r-l+1))+1;
}
else{
x=int(rnd()%vmax)+1;
}
if(op==4){
y=int(rnd()%vmax)+1;
}
if(op==1){
add(l,r,ll(x));
}
else if(op==2){
assign(l,r,ll(x));
}
else if(op==3){
cout<<Rank(l,r,x)<<endl;
}
else {
cout<<sum(l,r,x,y)<<endl;
}
}
return 0;
}
喜欢的记得点个赞。