珂朵莉树
前言
ODT一定要数据随机的情况下使用，不然会被卡的很惨
简述
珂朵莉树由一位长发飘逸的帅哥---lxl发明
由于发明者原因，所以也叫ODT：Old Driver Tree
复杂度
但是常数较大，set有时会捅你一刀，但是现在比赛好像开O2（bushi
可以做区间推平和区间多少个~~我才不会说我只会这个呢~~
正题
题目
给定你一个长度为
n,m<=
样例输入
10 6
0 0 0 0 0 0 0 0 0 0
1 3 1
2 5 2
3 10 3
5 9 3
4 9 4
7 10 3
#### 样例输出
0
0
0
5
0
1做法
很显然，如果直接每次去暴力修改直接给你T飞
用分块每次修改最后也是期望 n
线段树码量大，难查询
所以有请今天的主角------ODT
思路
将一段连续的数字合并成一个点，每次进行区间推平时，先把包含两段区间的节点分裂开，将分裂得到的包含l的点和包含r的点合并
具体做法
详情见注释
开一个set，存储一段连续的区间
初始时把每个位置都存进去，因为自身就是一个连续的相同的数
每次在推平时先将包含r+1的节点和包含l的节点分裂（代码中会提到
将中间全部擦除，插入新节点{l,r,c}
如果需要查询，在擦除之前在 r+1的节点和l的节点中间扫一遍查询即可
Code（带注释
#include<iostream>
#include<set>
using namespace std;
struct node{
int l,r;//范围
int v;//相同的值
bool operator < (const node &a) const{
return l<a.l;//便于查询进行分裂
}
};
set<node>aa;
int n;
int a[1000000];
set<node>::iterator split(int x)
{
set<node>::iterator find=aa.lower_bound(node{x,x,0});//找到包含这个节点的点
if(find!=aa.end()&&find->l==x)//如果找到了并且这个节点左端点就是要找的位置 即 不必要分裂
{
return find;//直接返回即可
}
find--;//找到的是第一个大于等于，由于等于的情况判完，一定是大于的
int l=find->l;// ->是指针用法
int r=find->r;
int v=find->v;
aa.erase(find); //将原节点擦除
aa.insert(node{l,x-1,v}); // 分裂出左区间
return aa.insert(node{x,r,v}).first; //返回最后一个区间
}
int assign(int l,int r,int x)
{
set<node>::iterator itr=split(r+1),itl=split(l);//先对r+1和l进行分裂
/*感性理解
这里为什么要对r+1和l进行操作呢，我个人也思考了很久
因为你返回的是那个节点插入的右边，也就是说另一半才包含你查找的东西
你对r+1进行分裂，返回的是r+1到那个节点右端点，所以擦除的时候会擦出掉r
那么你 分裂l是一定包含l的
*/
int res=0;
for(set<node>::iterator i=itl;i!=itr;i++)
{
if(i->v==x) res+=i->r-i->l+1; //对于 l-r中间查询
}
aa.erase(itl,itr);//推平
aa.insert(node{l,r,x});//插入新区间
return res;//回答查询
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];//输入
}
int j=1;
for(int i=1;i<=n;i++)
{
aa.insert(node{i,i,a[i]}); //每个位置都初始化成一个点，便于以后合并
}
for(int i=1;i<=n;i++)
{
int l,r,c;
cin>>l>>r>>c;
cout<<assign(l,r,c)<<endl;//调用函数
}
}