珂朵莉树不就是用set维护线段吗。所以我们怎么写都可以
咱也不知道这玩意有啥问题。要是真有问题请务必告诉我
我们用set维护线段，里面所有的线段互不相交。我们用一个结构体维护线段。具体写法如下：
struct node
{
int l,r;
bool operator <(const node &a)const{
return r<a.l;
}
};
读者可能会问：这么重载小于号不是会有问题吗？
但是我们保证了set里面所有线段互不相交，所以线段 \(a\) 如果在线段 \(b\) 的左边，那么这个小于号一定成立。
现在我们扔掉珂朵莉树里split操作。就考虑给出一条线段，如何在set里求所有与其相交的线段。
我们现在有一条线段 \(x\)，在set里面所有大于它的线段 \(y\) 均满足 \(x.l\leq y.r\)，也就是说所有与 \(x\) 相交的线段都不小于 \(x\)。那么我们可以配合lower_bound快速找到从哪里开始相交。不难想到，从一刻开始不相交了之后，就再也不会相交了。
下面实现的操作就是从set里面取出相交的线段再插进去一条新的线段的操作。
还有一个问题就是如果只查询不修改，那我们需要先把所有线段取出，计算，然后再放回去。
void opt2(int l,int r,ll x)
{
node cur=(node){l,r,x}; auto it=S.begin();
while((it=S.lower_bound(cur))!=S.end())
{
if((*it).l>r) break;
node tmp=(*it); S.erase(it);
if(tmp.l<l) S.insert((node){tmp.l,l-1,tmp.v});
if(tmp.r>r) S.insert((node){r+1,tmp.r,tmp.v});
}
S.insert(cur);
需要注意的是set里面所有线段均不相交，但是可能会有收尾相接。如果需要避免这种情况特判一下就行。
下面是 CF896C 的代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int Q,n;ll seed,vmax;
ll rnd(){ll ret=seed; seed=(seed*7+13)%1000000007; return ret;}
struct node
{
int l,r;ll v;
bool operator <(const node &a) const{
return r<a.l;
}
};
ll ksm(ll x,ll y,ll mod)
{
ll ret=1; x%=mod;
while(y)
{
if(y&1) ret=ret*x%mod;
x=x*x%mod; y>>=1;
}
return ret;
}
set<node> S;
void opt1(int l,int r,ll x)
{
node cur=(node){l,r,x}; auto it=S.begin();
set<node> ss;
while((it=S.lower_bound(cur))!=S.end())
{
if((*it).l>r) break;
node tmp=(*it); S.erase(it);
if(tmp.l<l) S.insert((node){tmp.l,l-1,tmp.v});
if(tmp.r>r) S.insert((node){r+1,tmp.r,tmp.v});
ss.insert((node){max(tmp.l,l),min(tmp.r,r),tmp.v+x});
}
for(auto x:ss) S.insert(x);
}
void opt2(int l,int r,ll x)
{
node cur=(node){l,r,x}; auto it=S.begin();
while((it=S.lower_bound(cur))!=S.end())
{
if((*it).l>r) break;
node tmp=(*it); S.erase(it);
if(tmp.l<l) S.insert((node){tmp.l,l-1,tmp.v});
if(tmp.r>r) S.insert((node){r+1,tmp.r,tmp.v});
}
S.insert(cur);
}
void opt3(int l,int r,ll x)
{
node cur=(node){l,r,x}; auto it=S.begin();
vector<pair<ll,ll> > V;
set<node> ss;
while((it=S.lower_bound(cur))!=S.end())
{
if((*it).l>r) break;
node tmp=(*it); S.erase(it);
if(tmp.l<l) S.insert((node){tmp.l,l-1,tmp.v});
if(tmp.r>r) S.insert((node){r+1,tmp.r,tmp.v});
V.push_back(make_pair(tmp.v,-max(tmp.l,l)+min(tmp.r,r)+1));
ss.insert((node){max(tmp.l,l),min(tmp.r,r),tmp.v});
}
for(auto x:ss) S.insert(x);
sort(V.begin(),V.end());
for(int i=1;i<(int)V.size();i++) V[i].second+=V[i-1].second;
ll lx=0,rx=V.size()-1,ans=0;
while(lx<=rx)
{
int mid=(lx+rx)>>1;
if(V[mid].second>=x) ans=V[mid].first,rx=mid-1;
else lx=mid+1;
}
printf("%lld\n",ans);
}
void opt4(int l,int r,ll x,ll y)
{
node cur=(node){l,r,x}; auto it=S.begin(); set<node> ss; ll ans=0;
while((it=S.lower_bound(cur))!=S.end())
{
if((*it).l>r) break;
node tmp=(*it); S.erase(it);
if(tmp.l<l) S.insert((node){tmp.l,l-1,tmp.v});
if(tmp.r>r) S.insert((node){r+1,tmp.r,tmp.v});
ll len=-max(tmp.l,l)+min(tmp.r,r)+1;
ans=(ans+len*ksm(tmp.v,x,y)%y)%y;
ss.insert((node){max(tmp.l,l),min(tmp.r,r),tmp.v});
}
for(auto x:ss) S.insert(x);
printf("%lld\n",ans);
}
int main()
{
scanf("%d%d%lld%lld",&n,&Q,&seed,&vmax);ll a;
for(int i=1;i<=n;i++) a=rnd()%vmax+1,S.insert((node){i,i,a});
for(int i=1;i<=Q;i++)
{
int opt=(rnd()%4+1);
int l=rnd()%n+1;
int r=rnd()%n+1;
if(l>r) swap(l,r);
ll x,y;
if(opt==3) x=rnd()%(r-l+1)+1;
else x=rnd()%vmax+1;
if(opt==4) y=rnd()%vmax+1;
if(opt==1) opt1(l,r,x);
if(opt==2) opt2(l,r,x);
if(opt==3) opt3(l,r,x);
if(opt==4) opt4(l,r,x,y);
}
}