简介
珂朵莉树一般多见于区间推平操作，即把[l,r]区间的值都赋值成k值的区间推平操作，在数据随机中可以出现奇效。
模板
点击查看代码
struct node
{
int l,r;
mutable int v;//mutable相反于const 用于操作存于set（存于set的均为const，但是加了mutable即可修改其值）中的值.
node(int i,int j,int k):l(i),r(j),v(k)
{
};
operator <(const node &o)const
{
return l<o.l; //重定义小于运算符，用于给set进行排序
}
};
set<node>s;
set<node>::iterator split(int pos)
{
set<node>::iterator it=s.lower_bound(node(pos,0,0));//set库当中的lower_bound()和upper_bound()
//是返回>=参数val或>参数val的迭代器；
if(it!=s.end()&&it->l==pos)
{
return it;
}
it--;
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;
}
void assign(int l,int r,int k)
{
auto itr=split(r+1),itl=split(l);//split函数是返回split(pos)中以pos为左边界的迭代器
int len=0,tol=0; //set的erase操作中左闭右开，即删除包含左迭代器到不包含右迭代器的中间部分
for(auto i=itl;i!=itr;i++)
{
len+=i->r-i->l+1;
tol+=i->v*(i->r-i->l+1);
}
s.erase(itl,itr);
s.insert(node(l,r,k));
if(k==0)
{
sum-=tol;
}
else
{
sum+=len-tol;
}
}
1.CF915E
思路：
用珂朵莉树给左右端点赋值，进行区间推平操作。
点击查看代码
#include<iostream>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define ll long long
int sum;
struct node
{
int l,r;
mutable int v;
node(int i,int j,int k):l(i),r(j),v(k)
{
};
operator <(const node &o)const
{
return l<o.l;
}
};
set<node>s;
set<node>::iterator split(int pos)
{
set<node>::iterator it=s.lower_bound(node(pos,0,0));
if(it!=s.end()&&it->l==pos)
{
return it;
}
it--;
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;
}
void assign(int l,int r,int k)
{
auto itr=split(r+1),itl=split(l);//split函数是返回split(pos)中以pos为左边界的迭代器
int len=0,tol=0; //set的erase操作中左闭右开，即删除包含左迭代器到不包含右迭代器的中间部分
for(auto i=itl;i!=itr;i++)
{
len+=i->r-i->l+1;
tol+=i->v*(i->r-i->l+1);
}
s.erase(itl,itr);
s.insert(node(l,r,k));
if(k==0)
{
sum-=tol;
}
else
{
sum+=len-tol;
}
}
signed main()
{
cin.tie(NULL);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int n;
int q;
cin>>n>>q;
s.insert(node(1,n,1));
sum=n;
for(int i=1;i<=q;i++)
{
int a,b,c;
cin>>a>>b>>c;
assign(a,b,c==1?0:1);
cout<<sum<<'\n';
}
return 0;
}