珂朵莉树
set版本
cpp
struct ODT{
struct Node{
int l,r;
mutable int v;//永远可变，可以直接修改set的值中的v，而不用重新插入
bool operator<(const Node&t)const{
return l<t.l;
}
};
set<Node> odt;
void init(vector<int> &a,int n){
for(int i=1,j;i<=n;i++){
j=i;
while(j+1<=n&&a[j+1]==a[j])j++;
odt.insert({i,j,a[i]});
i=j;
}
}
auto split(int x){
auto it=odt.lower_bound(Node(x,0,0));
if(it!=odt.end()&&it->l==x)return it;
it--;
auto [l,r,v]=*it;
odt.erase(it);
odt.insert(Node(l,x-1,v));
return odt.insert(Node(x,r,v)).first;
}
void assign(int l,int r,int v){
auto R=split(r+1),L=split(l);// 先R再L防止迭代器擦除
odt.erase(L,R);
odt.insert(Node(l,r,v));
}
void add(int l,int r,int v){
auto R=split(r+1),L=split(l);
for(auto p=L;p!=R;p++){
p->v+=v;
}
}
int kth(int l,int r,int k){
auto R=split(r+1),L=split(l);
vector<array<int,2>> tmp;
for(auto p=L;p!=R;p++){
tmp.push_back({p->v,p->r-p->l+1});
}
sort(tmp.begin(),tmp.end());
for(auto [val,len]:tmp){
if(len>=k)return val;
k-=len;
}
return 0;
}
int cal(int l,int r,int x,int y){
auto R=split(r+1),L=split(l);
int ans=0;
for(auto p=L;p!=R;p++){
int val=qpow(p->v%y,x,y);
(ans+=val*(p->r-p->l+1)%y)%=y;
}
return ans;
}
};map版本
cpp
struct ODT{
map<int,int> odt;
void init(vector<int> &a,int n){
for(int i=1,j;i<=n;i++){
j=i;
while(j+1<=n&&a[j+1]==a[j])j++;
odt[i]=a[i];
i=j;
}
odt[n+1]=-1;
}
auto split(int x){
auto it=prev(odt.upper_bound(x));
if(it->first==x)return it;
return odt.insert(it,make_pair(x,it->second));
}
void assign(int l,int r,int v){
split(l),split(r+1);
auto it=odt.find(l);
while(it->first!=r+1)it=odt.erase(it);
odt[l]=v;
}
void add(int l,int r,int v){
split(l),split(r+1);
auto it=odt.find(l);
while(it->first!=r+1){
it->second+=v;
it++;
}
}
int kth(int l,int r,int k){
split(l),split(r+1);
auto it=odt.find(l);
vector<array<int,2>> tmp;
while(it->first!=r+1){
tmp.push_back({it->second,next(it)->first-it->first});
it++;
}
sort(tmp.begin(),tmp.end());
for(auto [val,len]:tmp){
if(len>=k)return val;
k-=len;
}
return 0;
}
int cal(int l,int r,int x,int y){
split(l),split(r+1);
auto it=odt.find(l);
int ans=0;
while(it->first!=r+1){
int val=qpow(it->second%y,x,y);
(ans+=val*(next(it)->first-it->first)%y)%=y;
it++;
}
return ans;
}
};链表版本
cpp
struct ODT{
struct Block{
Block *next;
int l,r,v;
Block(int l=0,int r=0,int v=0,Block *next=NULL):l(l),r(r),v(v),next(next){}
bool operator<(const Block &t)const{
return v<t.v;
}
} *root,*lb,*rb;
void init(vector<int> &a,int n){
root=new Block();
auto tail=root;
for(int i=1,j;i<=n;i++){
j=i;
while(j+1<=n&&a[j+1]==a[j])j++;
tail->v=a[i];
tail->l=i;
tail->r=j;
if(j!=n)tail->next=new Block(),tail=tail->next;
i=j;
}
}
Block* split(int x){
for(auto b=root;b;b=b->next){
if(b->l==x+1)return b;
if(b->l<=x&&x+1<=b->r){
b->next=new Block(x+1,b->r,b->v,b->next);
b->r=x;
return b->next;
}
}
return NULL;
}
void prepare(int l,int r){// 保证操作都在[l,r]之间
lb=split(l-1);
rb=split(r);
}
void assign(int l,int r,int v){
prepare(l,r);
lb->r=r;
lb->v=v;
if(lb->next!=rb)delete(lb->next);
lb->next=rb;
}
void add(int l,int r,int v){
prepare(l,r);
for(auto b=lb;b!=rb;b=b->next){
b->v+=v;
}
}
int kth(int l,int r,int k){
prepare(l,r);
vector<Block> tmp;
for(auto b=lb;b!=rb;b=b->next){
tmp.push_back(*b);
}
sort(tmp.begin(),tmp.end());
for(auto [ne,L,R,v]:tmp){
int len=R-L+1;
if(k<=len)return v;
k-=len;
}
return -1;
}
int cal(int l,int r,int x,int y){
prepare(l,r);
int ans=0;
for(auto b=lb;b!=rb;b=b->next){
int val=qpow(b->v%y,x,y);
(ans+=(b->r-b->l+1)%y*val%y)%=y;
}
return ans;
}
};