由於這題的測資是隨機生成
所以可以用一個叫珂朵莉樹的資料結構來維護
珂朵莉樹是一個用set來存相同值的區間
#define IT set<Node>::iterator
IT split(int pos){
IT iter=tr.lower_bound(Node(pos));
if(iter!=tr.end()&&iter->l==pos)return iter;
--iter;
int nl=iter->l,nr=iter->r,nval=iter->val;
tr.erase(iter);
tr.insert(Node{nl,pos-1,nval});
return tr.insert(Node{pos,nr,nval}).first;
}
void assign(int l,int r,int val){
IT iterr=split(r+1),iterl=split(l);
tr.erase(iterl,iterr);
tr.insert(Node(l,r,val));
}
以上是珂朵莉樹的核心
split(int pos)是把原來含有pos位置的節點分成兩部分
例如：(1,8)-->(1,3)、(4,8)
assign(int l,int r,int val)的作用是區間付值(如果沒有這個操作基本上就不能用珂朵莉樹)
接下來區間加值、區間第K小、區間X次方和模mod就暴力硬做就好了
區間加值：
void add(int l,int r,int val){
IT iterr=split(r+1),iterl=split(l);
for(IT i=iterl;i!=iterr;++i)i->val+=val;
}
區間第K小：
int cmp(IT x,IT y){return x->val<y->val;}
int rk(int l,int r,int k){
vector<IT>g;
IT iterr=split(r+1),iterl=split(l);
for (IT i=iterl;i!=iterr;++i)g.push_back(i);
sort(g.begin(),g.end(),cmp);
int o=0;
for(auto i:g){
o+=i->r-i->l+1;
if(o>=k)return i->val;
}
}
區間X次方和模mod：
int pow_mod(int a,int n,int loli){
a%=loli;
int ans=1;
while(n){
if(n&1)ans*=a,ans%=loli;
a*=a,a%=loli,n/=2;
}
return ans;
}
int sum(int l,int r,int x,int loli){
int ans=0;
IT iterr=split(r+1),iterl=split(l);
for(IT i=iterl;i!=iterr;++i)ans=(ans+pow_mod(i->val,x,loli)*(i->r-i->l+1))%loli;
return ans;
}
阿如果你只是要抄答案的話：
#define IT set<Node>::iterator
#define int long long
using namespace std;
int seed,vmax,x,y,n,m,l,r,op;
struct Node{
int l,r;
mutable int val;
Node(int _l=0,int _r=0,int _val=0):l(_l),r(_r),val(_val){}
bool operator < (const Node &nt) const{return l<nt.l;}
};
set<Node>tr;
IT split(int pos){
IT iter=tr.lower_bound(Node(pos));
if(iter!=tr.end()&&iter->l==pos)return iter;
--iter;
int nl=iter->l,nr=iter->r,nval=iter->val;
tr.erase(iter);
tr.insert(Node{nl,pos-1,nval});
return tr.insert(Node{pos,nr,nval}).first;
}
void assign(int l,int r,int val){
IT iterr=split(r+1),iterl=split(l);
tr.erase(iterl,iterr);
tr.insert(Node(l,r,val));
}
void add(int l,int r,int val){
IT iterr=split(r+1),iterl=split(l);
for(IT i=iterl;i!=iterr;++i)i->val+=val;
}
int cmp(IT x,IT y){return x->val<y->val;}
int rk(int l,int r,int k){
vector<IT>g;
IT iterr=split(r+1),iterl=split(l);
for (IT i=iterl;i!=iterr;++i)g.push_back(i);
sort(g.begin(),g.end(),cmp);
int o=0;
for(auto i:g){
o+=i->r-i->l+1;
if(o>=k)return i->val;
}
}
int pow_mod(int a,int n,int loli){
a%=loli;
int ans=1;
while(n){
if(n&1)ans*=a,ans%=loli;
a*=a,a%=loli,n/=2;
}
return ans;
}
int sum(int l,int r,int x,int loli){
int ans=0;
IT iterr=split(r+1),iterl=split(l);
for(IT i=iterl;i!=iterr;++i)ans=(ans+pow_mod(i->val,x,loli)*(i->r-i->l+1))%loli;
return ans;
}
main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>op,tr.insert(Node(i,i,op));
tr.insert(Node(n+1,n+1,0));
for(int i=1;i<=m;++i){
cin>>op>>l>>r>>x;
if(op==1)add(l,r,x);
else if(op==2)assign(l,r,x);
else if(op==3)cout<<rk(l,r,x)<<"\n";
else cin>>y,cout<<sum(l,r,x,y)<<"\n";
}
}