欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

P5787 线段树分治+可撤销并查集

程序员文章站 2022-06-22 20:16:33
题目链接:https://www.luogu.com.cn/problem/P5787解题技巧:1.对于此类在某一段时间**[L,R]**内产生贡献的非强制在线问题,我们都可以试着采用线段树分治解决//#define LOCAL#include using namespace std;#define ll long long#define mem(a, b) memset(a,b,sizeof(a))#define sz(a) (int)a.s....
  • 题目链接:https://www.luogu.com.cn/problem/P5787
  • 解题技巧:
    1.对于此类在某一段时间**[L,R]**内产生贡献的非强制在线问题,我们都可以试着采用线段树分治解决
//#define LOCAL
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mem(a, b) memset(a,b,sizeof(a))
#define sz(a) (int)a.size()
#define INF 0x3f3f3f3f
#define DNF 0x7f
#define DBG printf("this is a input\n")
#define fi first
#define se second
#define mk(a, b) make_pair(a,b)
#define pb push_back
#define LF putchar('\n')
#define SP putchar(' ')
#define p_queue priority_queue
#define CLOSE ios::sync_with_stdio(0); cin.tie(0)
#define sz(a) (int)a.size()
#define pii pair <int,int>
template<typename T>
void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args>
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}
using namespace std;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

const int N = 2e5 + 5;
int n , m , k;
vector <int> v[N << 2];
struct node
    {
    int u , v;
}edge[N];
struct Undo_Dsu
{
    stack <pii> st ;
    int fa[N] , siz[N] ;
    int d[N];
    void init()
    {
        while(!st.empty())  st.pop() ;
        for (int i = 1 ; i <= n  ; i ++)  fa[i] = i , siz[i] = 1 , d[i] = 0;
    }
    int dis (int x)
    {
        int temp = 0;
        while (fa[x] != x) {
            temp ^= d[x];
            x = fa[x];
        }
        return temp;
    }
    int findroot(int x)
    {
        return x == fa[x] ? x : findroot(fa[x]) ;
    }
    bool merge(int u , int v)
    {
        int fax = findroot(u) , fay = findroot(v);
        if(fax == fay)  return 0 ;
        if (siz[fax] > siz[fay])  swap(fax, fay) , swap(u , v) ;
        int d1 = dis (u), d2 = dis (v);
        fa[fax] = fay , siz[fay] += siz[fax] ;
        d[fax] = (d1 + d2 + 1) % 2;
        st.push({fax , fay}) ;
        return 1 ;
    }
    void undo() //撤销一次最新的合并
    {
        pii no = st.top();
        fa[no.fi] = no.fi ;
        siz[no.se] -= siz[no.fi] ;
        d[no.fi] = 0;
        st.pop() ;
    }
} dsu ;


void insert (int i , int L , int R, int l , int r , int val)
{
    if (L > r || R < l) return ;
    if (l <= L && R <= r) {
        v[i].pb(val);
        return ;
    }
    int mid = (L + R) >> 1;
    insert (i << 1 , L , mid , l , r , val);
    insert (i << 1 | 1 , mid + 1 , R , l , r, val);
}
void dfs (int i , int L, int R)
{
    int ok = 1;
    int t = sz(dsu.st);
    for (auto it : v[i])
    {
        int u = edge[it].u , v = edge[it].v;
        int fau = dsu.findroot (u) , fav = dsu.findroot (v);
        if (fau == fav)
        {
            int d1 = dsu.dis(u), d2 = dsu.dis(v);
            if ((d1 + d2) % 2 == 0) {
                ok = 0;
                break;
            }
        }
        else
            dsu.merge(u, v);
    }
    if (ok == 0)
    {
        for (int t = L ; t <= R ; t ++)
            cout << "No" << endl;
    }
    else
    {
        if (L == R)
        {
            cout << "Yes" << endl;
            return ;
        }
        int mid = (L + R) >> 1;
        dfs (i << 1 , L , mid);
        dfs (i << 1 | 1, mid + 1 , R);
    }
    while (sz(dsu.st) > t) dsu.undo();
    return ;
}
int main ()
{
    read (n , m, k);
    for (int i = 1 ; i <= m ; i ++)
    {
        int u , v, l , r;
        read (u , v ,l , r);
        edge[i].u = u, edge[i].v = v;
        insert (1 , 1 , k , l + 1 , r , i);
    }
    dsu.init();
    dfs (1, 1 , k);
}

本文地址:https://blog.csdn.net/Zenith_Habitant/article/details/109249873