简介与实现方法
该结构是通过 STL set 来维护存储相同颜色（相同值）连续段的暴力数据结构，需要在 set 中存储若干个三元组 \((l,r,k)\) 表示 \([l,r]\) 的所有颜色（值）都是 \(k\)。
它的使用条件是数据随机。我们把区间覆盖或群体赋值称为区间推平操作，如果该操作较多单一操作是 \(O(\log n)\) 的，特殊构造下可以退化到单一操作 \(O(n\log^2 n)\)，所以泛用性并不强。
Split
该操作 \(Split(pos)\) 通过找到一个区间使得 \(pos\in[l,r]\)，然后根据 \(pos\) 将其分成 \([l,pos-1],[pos,r]\) 两个区间，并且返回指向 \([pos,r]\) 的迭代器。
struct Node{int l,r;mutable int v;Node(int ll, int rr=0, int vv=0) : l(ll), r(rr), v(vv) {}bool operator<(const Node &a)const{return l<a.l;}
};
typedef set<Node>::iterator IT;
set<Node>s;
IT split(int pos){IT 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,r=it->r,v=it->v;s.erase(it);s.insert(Node(l,pos-1,v));return s.insert(Node(pos,r,v)).first;
}
其中 mutable 的作用是使直接用迭代器访问元素时能够修改该值。需要注意一些特判，如能找到 \([pos,r]\) 就直接返回该区间。如果 \(pos>\max r\)，那么该区间不存在，返回 s.end() 即可。
Assign
区间推平操作。具体来说，先找到右侧迭代器 itr=split(r+1)，然后找到左侧迭代器 itl=split(l)，顺序不能反。原因也很简单，因为 split(r+1) 可能会影响 \(l\) 之后的区间形态，先找左再找右可能导致原来找的那个东西已经被删去了。但 split(l) 因为已经有了 split(r+1)，所以并不会对 \(r\) 后面区间形态造成影响（\(l\) 所在区间右端点最大都只能是 \(r\)）。暴力删掉两个迭代器间所有值然后加一个新的区间进去即可。
void assign(int l,int r,int x){IT itr=split(r+1),itl=split(l);for(IT it=itl;it!=itr;it++)ans-=(it->v)*((it->r)-(it->l)+1);s.erase(itl,itr);s.insert(Node(l,r,x));ans+=(r-l+1)*x;
}
例题
好啦然后我们就写完了。由于其结构的特殊性，它能做很多一般数据结构不能做的事情，因为一个连续区间内值相等，所以计算什么 \([l,r]\) 内元素排序后第 \(x\) 个或者 \(\sum_{i=l}^r {a_i}^k\) 都是不在话下，直接上 set 迭代器暴力扫即可。
CF915E Physical Education Lessons
区间推平，值域 \([0,1]\)，数 \(1\) 的个数，直接上 ODT，维护一个全局变量记录和，在每次区间推平时访问要删掉的区间然后相应修改即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PII;
const LL MOD=1e9+7;
struct Node{int l,r;mutable int v;Node(int ll, int rr=0, int vv=0) : l(ll), r(rr), v(vv) {}bool operator<(const Node &a)const{return l<a.l;}
};
typedef set<Node>::iterator IT;
set<Node>s;
int n,q;
IT split(int pos){IT 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,r=it->r,v=it->v;s.erase(it);s.insert(Node(l,pos-1,v));return s.insert(Node(pos,r,v)).first;
}
int ans;
void assign(int l,int r,int x){IT itr=split(r+1),itl=split(l);for(IT it=itl;it!=itr;it++)ans-=(it->v)*((it->r)-(it->l)+1);s.erase(itl,itr);s.insert(Node(l,r,x));ans+=(r-l+1)*x;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q;s.insert(Node(1,n,1));ans=n;while(q--){int l,r,k;cin>>l>>r>>k;assign(l,r,k-1);cout<<ans<<'\n';}return 0;
}
CF896C Willem, Chtholly and Seniorious
区间加，区间推平，类似在线可持久化线段树的功能还有求区间 \(y\) 次方和。对于所有操作都可以转化为 \(Split\) 后遍历所有 \([l,r]\) 拆成的区间并统计答案。对于区间第 \(k\) 大的功能，把所有区间存下来按照颜色排个序即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PII;
const LL MOD=1e9+7;
const int N=1e5+5;
struct Node{int l,r;mutable LL v;Node(int ll, int rr=0, LL vv=0) : l(ll), r(rr), v(vv) {}bool operator<(const Node &a)const{return l<a.l;}
};
typedef set<Node>::iterator IT;
set<Node>s;
int n,m;
LL seed,ret,vmax,a[N];
int rnd(){ret=seed;seed=(seed*7+13)%MOD;return ret;
}
IT split(int pos){IT 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,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 assign(int l,int r,LL x){IT itr=split(r+1),itl=split(l);s.erase(itl,itr);s.insert(Node(l,r,x));
}
void add(int l,int r,LL x){IT itr=split(r+1),itl=split(l);for(IT it=itl;it!=itr;it++)it->v+=x;
}
LL qkpow(LL x,LL y,LL mod){LL res=1;x%=mod;while(y){if(y&1)res=res*x%mod;x=x*x%mod;y>>=1;}return res;
}
LL query1(int l,int r,int x){IT itr=split(r+1),itl=split(l);vector<PII>rk;for(IT it=itl;it!=itr;it++)rk.emplace_back(make_pair(it->v,(it->r)-(it->l)+1));sort(rk.begin(),rk.end());int now=0;for(PII v:rk){now+=v.second;if(now>=x)return v.first;}return 114514;
}
LL query2(int l,int r,LL x,LL y){LL res=0;IT itr=split(r+1),itl=split(l);for(IT it=itl;it!=itr;it++)(res+=qkpow(it->v,x,y)*((it->r)-(it->l)+1)%y)%=y;return res;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>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++){int op=rnd()%4+1;LL x;int l=rnd()%n+1,r=rnd()%n+1;if(l>r)swap(l,r);if(op==1){x=rnd()%vmax+1;add(l,r,x);}else if(op==2){x=rnd()%vmax+1;assign(l,r,x);}else if(op==3){x=rnd()%(r-l+1)+1;cout<<query1(l,r,x)<<'\n';}else {x=rnd()%vmax+1;LL y=rnd()%vmax+1;cout<<query2(l,r,x,y)<<'\n';}}return 0;
}