题解 P2184 【贪婪大陆】线段树 容斥

[博客传送门！](http://www.wjyyy.top/844.html) 一个类似区间染色求种类数的题。（为什么大家写的和我都不一样。。。）    一开始看上去，不是一个线段树区间染色的题吗。。。手玩了一下样例发现原来地雷是可以覆盖的啊，开始重新审视这个题。    和区间染色类似，而因为区间染色（如果可覆盖）在查询时合并区间要看**左孩子的最右点**和**右孩子的最左点**是否一致，一致则把种类-1**【容斥原理】**。这样只用多维护两个变量+lazytag就可以了。不过这个题不能覆盖，就要想办法换个思路维护。    因为这个题的地雷种类只会增加不会减少，因此一旦左孩子的最右点和右孩子的最左点颜色（编号）相同，它们就永远相同，对这个容斥产生1个贡献，因此我们可以维护一个区间最左点与左相邻区间最右点相同颜色的个数（最左或最右任选其一维护，我写的是最左）作为**重复标**记。在线段树区间change时，一旦出现跨越了两个儿子的修改，那就要把右儿子的左端点重复标记++了。同样，lazytag在标记与下放时，如果**lazy不等于0**，依然要把右儿子的左端点++，同时维护的**lazyl（上面传下来的左端点tag）**也要加上去，并延续到左儿子上。 ## Code： ```cpp #include<cstdio> #include<cstring> #define ls (k<<1) #define rs (k<<1|1) #define mid (l+r>>1) #define Mid (t[k].l+t[k].r>>1) struct node { int l,r,v,lazy; int ll,lazyl; node(int l,int r) { this->l=l;//区间位置 this->r=r; ll=0;//左端点的重复标记 v=0;//区间不互相干扰的颜色种类 lazy=0; lazyl=0; } node() { ll=0; v=0; lazy=0; lazyl=0; } }t[410000]; void build(int k,int l,int r) { t[k]=node(l,r); if(l==r) return; build(ls,l,mid); build(rs,mid+1,r); } void pushdown(int k)//pushdown是关键 { if(t[k].l==t[k].r) { t[k].lazy=0; t[k].lazyl=0; return; } t[ls].v+=t[k].lazy; t[ls].ll+=t[k].lazyl; t[ls].lazyl+=t[k].lazyl; t[ls].lazy+=t[k].lazy; t[rs].v+=t[k].lazy; if(t[k].lazy) { t[rs].ll+=t[k].lazy;//有时多种颜色会一起传下来 t[rs].lazyl+=t[k].lazy; } t[rs].lazyl+=t[k].lazyl; t[rs].lazy+=t[k].lazy; t[k].lazy=0; t[k].lazyl=0; } void change(int k,int l,int r,int x) { if(t[k].l==l&&r==t[k].r) { t[k].lazy++; t[k].v++; return; } t[k].v++; pushdown(k); if(r<=Mid) change(ls,l,r,x); else if(l>Mid) change(rs,l,r,x); else { t[rs].ll++;//修改右孩子的左端点重复标记 t[rs].lazyl++;//并下放到右孩子的左孩子的lazytag change(ls,l,Mid,x); change(rs,Mid+1,r,x); } return; } int ask(int k,int l,int r) { pushdown(k); if(t[k].l==l&&t[k].r==r) return t[k].v; if(r<=Mid) return ask(ls,l,r); else if(l>Mid) return ask(rs,l,r); else return ask(ls,l,Mid)+ask(rs,Mid+1,r)-t[rs].ll;//减去重复标记 } int main() { int n,m,op,l,r; scanf("%d%d",&n,&m); build(1,1,n); for(int i=1;i<=m;i++) { scanf("%d%d%d",&op,&l,&r); if(op==1) change(1,l,r,i); else printf("%d\n",ask(1,l,r)); } return 0; } ```