题解 CF576E 【Painting Edges】

· · 题解

Painting Edges

题目传送门

思路

真的神仙。。。

因为这道题多种颜色可以拆成一个一个颜色的考虑，所以我们就直接一种颜色的情况。

这道题跟其他的线段树分治最大的不同就在于每条边没有给出出现的时间。那怎么办呢？

其实我们还是有解决办法的，对于一条边而言，如果有(u,v)两次染色操作，那么[u+1,v-1]这段时间内只有两种情况

  1. 要么没成功还是原先的颜色

  2. 成功了就是u染的颜色。

所以我们就直接假定染成功了，然后直接递归每个叶子判断是否成功了，如果没有，就直接撤销。那为什么是对的呢？因为时间是两两不同的，如果我们这个失败了撤销之后是不会产生影响的。

那怎么判断成功不成功呢？我们可以直接用按秩合并并查集就好了。

口胡了这么多还是上代码好理解一点。

（从xnt奆佬那学到了避免数组和变量重名的方法tql%%%）

\text {Code}

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define MAXN 500005
#define MAXX 55

int n,m,k,q;
int a[MAXN],c[MAXN],u[MAXN],v[MAXN],p[MAXN],fa[MAXX][MAXN << 1],size[MAXX][MAXN << 1];

struct Node{int c,x;};

stack <Node> S;

int findSet (int c,int x)
{
    while (x ^ fa[c][x]) x = fa[c][x];
    return x;   
}

void unionSet (int c,int x,int y)
{
    if (x == y) return ;
    if (size[c][x] > size[c][y]) swap (x,y);    
    S.push (Node {c,x}),size[c][y] += size[c][x],fa[c][x] = y;
}

vector <int> tree[MAXN << 2];

void update (int k,int l,int r,int tl,int tr,int res)
{
    if (l > tr || tl > r) return ;
    if (l >= tl && r <= tr) return tree[k].push_back (res);
    int mid = (l + r) >> 1;
    update (k << 1,l,mid,tl,tr,res);
    update (k << 1 | 1,mid + 1,r,tl,tr,res);
}

void Divide (int k,int l,int r)
{
    int tag = S.size ();
    for (Int i = 0;i < tree[k].size();++ i)
    {
        int x = tree[k][i],a = ::a[x],c = ::c[x],u = ::u[a],v = ::v[a];
        if (c) unionSet (c,findSet (c,u),findSet (c,v + n)),unionSet (c,findSet (c,v),findSet (c,u + n));
    } 
    if (l == r)
    {
        int a = ::a[l],c = ::c[l],u = ::u[a],v = ::v[a];
        if (findSet (c,u) == findSet (c,v)) puts ("NO"),::c[l] = ::p[a];
        else puts ("YES"),::p[a] = ::c[l];
        return ;
    }
    int mid = (l + r) >> 1;
    Divide (k << 1,l,mid),Divide (k << 1 | 1,mid + 1,r);
    while (S.size() > tag)
    {
        int c = S.top().c,x = S.top().x;
        size[c][fa[c][x]] -= size[c][x],fa[c][x] = x;
        S.pop();
    }
}

int read ()
{
    int x = 0;char c = getchar();int f = 1;
    while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}
    while (c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + c - '0';c = getchar();}
    return x * f;
}

void write (int x)
{
    if (x < 0){x = -x;putchar ('-');}
    if (x > 9) write (x / 10);
    putchar (x % 10 + '0');
}

signed main()
{
    n = read (),m = read (),k = read (),q = read ();
    for (Int i = 1;i <= n;++ i)
        for (Int j = 1;j <= k;++ j)
            fa[j][i] = i,fa[j][n + i] = n + i,
            size[j][i] = 1,size[j][n + i] = 1;
    for (Int i = 1;i <= m;++ i) u[i] = read (),v[i] = read (),p[i] = q + 1;
    for (Int i = 1;i <= q;++ i) a[i] = read (),c[i] = read ();
    for (Int i = q;i >= 1;-- i)
    {
        int a = ::a[i];
        if (i < p[a] - 1) update (1,1,q,i + 1,p[a] - 1,i);
        p[a] = i;
    }
    memset (p,0,sizeof (p));
    Divide (1,1,q);
    return 0;
}