xtq的口令-赛后题解

mydiplomacy · 2018-12-20 18:19:58 · 题解

如果A同学观察B同学，那么我们连一条从点A到点B的有向边。

在下面的陈述中，我们将“A同学收到指令”称为“点A被染色”。

那么我们就可以把题意转化为：

给定一个有向图，已知当一个点连向的点被染色时，那么这个点也被染色。支持两种操作：

查询操作：给定区间[L,R]内的所有点被染色，那么求还需要给多少点染色，才能使最终所有点被染色。

修改操作：给定区间[L,R]和x，将编号在区间[L,R]内的所有点连向x。

下面考虑做法。

• 20分：

  完全暴力即可。对于每个查询操作，首先忽略所有[L,R]内的点和[L,R]被染色后被染色的点。接下来枚举每个点是否被选中，对于每种方案进行判定是否合法，最后输出最小答案。

• 50分：

  需要进一步研究性质。

  首先，由于边只会从编号大的点连到编号小的点，那么这个图一定是一个有向无环图。

  观察所有出度为零（指图中不存在这个点连出的边）的点。我们可以证明：

  • 如果这些点当中的每个点，如果这个点没被[L,R]包含，那么这个点必须被染色。

    证明：由于这个点没有连出的边，那么如果任何其他点被染色了，这个点都不会被染色。

  • 当所有这些点被染色了，那么所有点都会被染色。

    证明：假设存在一个点，当所有这些点被染色时，还没有被染色。于是我们可以推出，这个点所连向的所有点都没有被染色。所以，这个点所连向的点所连向的点也没有被染色，以此类推。由于点的数量是有限的，所以必定会出现下列情况之一：

    • 这个点所连向的点所连向的点...所连向的点，与这个点重合，或者与另外一个这个点所连向的点...所连向的点重合。这与无环矛盾。
    • 这个点所连向的点...所连向的点，没有连出的边。由于我们前面的推导，这个点一定没有染色。而这又与我们假设的前提矛盾。

    所以，假设不成立！

  于是，所有点被染色的充分必要条件是所有出度为零的点被染色。所以这道题的询问操作就转化为了：查询有多少出度为零的点，不在区间[L,R]内。只需首先预处理 出入度为零的点，修改操作时移除所有区间内的点，均可以O(n)处理。

  50分代码见下面参考代码1。

• 70分（所有具备特殊性质的数据点）：

  我们可以首先O(m)预处理每个点是否为出度为零的点并记录，接下来O(n)预处理出sum[i]，代表1~i中有多少个出度为零的点。

  对于每个修改操作，只需要将[L,R]内的每个点标记为出度非零，再根据之前处理出的每个点的是否入度为零标记重新计算sum数组。效率O(n)

  对于每个查询操作，利用前缀和O(1)查询[1,L-1]与[R+1,N]内共有多少个出度非零的点，然后输出。效率O(1)

  但由于修改不超过100组，可以得到部分分。

  70分代码见下面参考代码2。

• 100分：

  利用线段树等数据结构维护数组a，a[i]代表是否出度为零，如果是则为1，否则为0。

  查询操作相当于查询[1,L-1]的和加上[R+1,N]的和。

  修改操作相当于将[L,R]区间区间覆盖为0。

  问题得解。

  std见下面参考代码3。

参考代码1：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=300005;

int d[maxn]; //d代表：当前节点出度是否为零。1：出度为零，0：出度非零

int main()
{
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++) d[i]=1;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d",&x);
        for(int j=1;j<=x;j++)
        {
            scanf("%d",&y);
            d[y]=0; //出度非零
        }
    }
    for(int i=1;i<=q;i++)
    {
        int opt,x,y,z;
        scanf("%d",&opt);
        if(opt==1)
        {
            int sum=0;
            scanf("%d %d",&x,&y);
            for(int j=1;j<x;j++) 
                sum+=d[j];
            for(int j=y+1;j<=n;j++)
                sum+=d[j];
            printf("%d\n",sum);
        }
        if(opt==2)
        {
            scanf("%d %d %d",&x,&y,&z);
            for(int i=x;i<=y;i++) d[i]=0;
        }
    }
    return 0;
}

参考代码2：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=300005;

int d[maxn],s[maxn]; //s:前缀和

int main()
{
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++) d[i]=1;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d",&x);
        for(int j=1;j<=x;j++)
        {
            scanf("%d",&y);
            d[y]=0;
        }
    }
    for(int i=1;i<=n;i++) s[i]=s[i-1]+d[i];
    for(int i=1;i<=q;i++)
    {
        int opt,x,y,z;
        scanf("%d",&opt);
        if(opt==1)
        {
            int sum=0;
            scanf("%d %d",&x,&y);
            sum=s[x-1]+s[n]-s[y];
            printf("%d\n",sum);
        }
        if(opt==2)
        {
            scanf("%d %d %d",&x,&y,&z);
            for(int i=x;i<=y;i++) d[i]=0; 
            for(int i=1;i<=n;i++) s[i]=s[i-1]+d[i]; //修改操作后，重新计算前缀和
        }
    }
    return 0;
}

参考代码3：

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn=900005;

struct Node //线段树节点
{
    int left, right;
    int sum, lazy;
}a[maxn];

int ab[maxn],x,y,z,opt,d[maxn];
int n,q;

void buildtree(int id, int l, int r)
{
    a[id].left=l; a[id].right=r; a[id].lazy=0;
    if(l==r)
    {
        if(d[l]==1)
            a[id].sum=0;
        else
            a[id].sum=1;
        return;
    }
    int mid=(l+r)/2;
    buildtree(id<<1,l,mid);
    buildtree(id<<1|1,mid+1,r);
    a[id].sum=a[id<<1].sum+a[id<<1|1].sum;
}

void pushdown(int id)
{
    if(a[id].lazy==1)
    {
        a[id].sum=0;
        a[id<<1].lazy=1;
        a[id<<1|1].lazy=1;
        a[id].lazy=0;
    }
}

int query(int id, int l, int r)
{
    if(a[id].left==l && a[id].right==r)
    {
        if(a[id].lazy==0)
            return a[id].sum;
        else
            return 0;
    }
    pushdown(id);
    if(r<=a[id<<1].right) return query(id<<1,l,r);
    else if(l>=a[id<<1|1].left) return query(id<<1|1,l,r);
    else
    {
        return query(id<<1,l,a[id<<1].right)+query(id<<1|1,a[id<<1|1].left,r);
    }
}

void change(int id, int l, int r)
{
    if(a[id].left==l && a[id].right==r)
    {
        a[id].lazy=1;
        return;
    }
    pushdown(id);
    if(r<=a[id<<1].right) change(id<<1,l,r);
    else if(l>=a[id<<1|1].left) change(id<<1|1,l,r);
    else
    {
        change(id<<1,l,a[id<<1].right);
        change(id<<1|1,a[id<<1|1].left,r);
    }
    a[id].sum=(a[id<<1].lazy==0?a[id<<1].sum:0)+(a[id<<1|1].lazy==0?a[id<<1|1].sum:0);
}

int main()
{
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&ab[i]);
        for(int j=1;j<=ab[i];j++)
        {
            scanf("%d",&x);
            d[x]=1;
        }
    }
    buildtree(1,1,n);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d %d",&x,&y);
            printf("%d\n",query(1,1,n)-query(1,x,y));
        }
        else
        {
            scanf("%d %d %d",&x,&y,&z);
            change(1,x,y);
        }
    }
    return 0;
}