洛谷 P2184 贪婪大陆 题解【线段树】【容斥原理】

点击量：37

   大家写的题解跟我都不一样啊hhh

目录

题目背景

面对蚂蚁们的疯狂进攻，小FF的Tower defence宣告失败……人类被蚂蚁们逼到了Greed Island上的一个海湾。现在，小FF的后方是一望无际的大海， 前方是变异了的超级蚂蚁。 小FF还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造SCV布置地雷以阻挡蚂蚁们的进攻。

 

题目描述

小FF最后一道防线是一条长度为N的战壕， 小FF拥有无数多种地雷，而SCV每次可以在[ L , R ]区间埋放同一种不同于之前已经埋放的地雷。 由于情况已经十万火急，小FF在某些时候可能会询问你在[ L’ , R’] 区间内有多少种不同的地雷， 他希望你能尽快的给予答复。

 

对于30%的数据： 0<=n,m<=1000;

 

对于100%的数据： 0<=n,m<=10^5.

 

输入输出格式

输入格式：

第一行为两个整数n和m； n表示防线长度， m表示SCV布雷次数及小FF询问的次数总和。

 

接下来有m行， 每行三个整数Q，L , R； 若Q=1 则表示SCV在[ L , R ]这段区间布上一种地雷， 若Q=2则表示小FF询问当前[ L , R ]区间总共有多少种地雷。

输出格式：

对于小FF的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。

 

输入输出样例

输入样例#1：

5 4

1 1 3

2 2 5

1 2 4

2 3 5

输出样例#1：

1

2

题解：

   一开始看上去，不是一个线段树区间染色的题吗。。。手玩了一下样例发现原来地雷是可以覆盖的啊，开始重新审视这个题。

   和区间染色类似，而因为区间染色（如果可覆盖）在查询时合并区间要看左孩子的最右点和右孩子的最左点是否一致，一致则把种类-1【容斥原理】。这样只用多维护两个变量+lazytag就可以了。不过这个题不能覆盖，就要想办法换个思路维护。

   因为这个题的地雷种类只会增加不会减少，也就是一旦左孩子的最右点和右孩子的最左点颜色（编号）相同，它们就永远相同，对这个容斥产生1个贡献，因此我们可以维护一个区间最左点与左相邻区间最右点相同颜色的个数（最左或最右任选其一维护，我写的是最左）作为重复标记。在线段树区间change时，一旦出现跨越了两个儿子的修改，那就要把右儿子的左端点重复标记++了。同样，lazytag在标记与下放时，如果lazy不等于0，依然要把右儿子的左端点++，维护的lazyl（上面传下来的左端点tag）也要加上去，并延续到左儿子上。

Code：

#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;
}