本文主要是介绍【线段树】[LUOGU 会场预约] 线段树染色，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
题目链接：[LUOGU 会场预约]
题解：
（这个可以用BIT写，这个是比较短的，可是蒟蒻这个数据结构还需要加强，，，，）
线段树染色，就是对于每次的区间覆盖的时候进行染色处理，再记录一下是否被删除过的数 ，这样不用再进行真实的删除操作了，懒标记为颜色的标号。
安利大佬博客：传送门
（好不容易写完的题，反复TLE，，，索性一个O2，，，结果就过了，，，，不知道我的常数为何如此之大，，，，）
代码：
#include<bits/stdc++.h>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int sea=400002;
struct data{char opt[2]; int l,r;}a[200002];
struct hit{int l,r,lazy;}tr[sea*4];
bool del[sea],same[sea];
int st=1e9,ed,n,v,ans,era;
void pushdown(int o)
{int l=tr[o].l,r=tr[o].r; same[o]=0;//一定不是一种颜色if(!tr[o].lazy) return ;tr[lc].lazy=tr[rc].lazy=tr[o].lazy;tr[o].lazy=0;
}
void build(int o,int l,int r)
{tr[o].l=l,tr[o].r=r; same[o]=1;tr[o].lazy=0;//初始的时候是同一种颜色 if(l==r) return ; int mid=(l+r)/2;build(lc,l,mid); build(rc,mid+1,r);
}
void find(int o)
{int l=tr[o].l,r=tr[o].r;if(same[o]==1)//是否是同一种颜色{if(!del[tr[o].lazy]&&tr[o].lazy) --ans,++era; //没有被删除过，而且还有区间标记del[tr[o].lazy]=1; tr[o].lazy=v;return ;}int mid=(l+r)/2; find(lc); find(rc);tr[o].lazy=v; same[o]=1;//这里面都是同色的
}
void alter(int o,int x,int y)
{int l=tr[o].l,r=tr[o].r;if(x<=l&&r<=y) {find(o); return ;}pushdown(o); int mid=(l+r)/2;if(x<=mid) alter(lc,x,y); if(y>mid) alter(rc,x,y);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%s",a[i].opt);if(a[i].opt[0]=='B') continue;scanf("%d%d",&a[i].l,&a[i].r);st=min(st,a[i].l); ed=max(ed,a[i].r);}build(1,st,ed); int cnt=0; //颜色标号for(int i=1;i<=n;++i){if(a[i].opt[0]=='A'){++ans; v=++cnt; era=0;alter(1,a[i].l,a[i].r); printf("%d\n",era);}else printf("%d\n",ans);}return 0;
}
Continue……
这篇关于【线段树】[LUOGU 会场预约] 线段树染色的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
