天天看點
傳回

2020牛客暑期多校訓練營（第八場） A、All-Star Game（線段樹分治、LCT）

題目連結

題面：

2020牛客暑期多校訓練營（第八場） A、All-Star Game（線段樹分治、LCT）

題意：

有 n n n 個球員， m m m 個粉絲。

一個粉絲可能喜歡多個球員。

現在要從 n n n 個球員中選出一些球員來參加比賽，使得所有的粉絲都願意觀看這場比賽。

某個粉絲喜歡觀看這場比賽的條件滿足以下之一即可：

（1）粉絲 i i i 喜歡的球員 j j j 在這場比賽中。

（2）粉絲 x x x 喜歡觀看球員 j j j 的比賽，粉絲 i , x i,x i,x 都喜歡觀看球員 y y y 的比賽，那麼粉絲 i i i 喜歡觀看球員 j j j 的比賽。

給定 q q q 次喜歡關系的改變，每次詢問至少選出多少球員，才能讓所有粉絲都喜歡觀看這場比賽。

如果不能滿足讓所有粉絲都喜歡觀看這場比賽，輸出-1。

題解：

如果把這個關系建成一個圖的話。其實就是需要求n個球員的連通分量個數（因為條件（2），導緻了喜歡關系可以傳遞）。

如果有球迷的度為0，答案就是-1。

否則答案就是（n個球員的連通分量個數）- (孤立球員個數)

是以隻需要在加邊和删邊的時候，維護n個球員的連通分量個數。

x是球員，y是球迷。

x, y加邊時候，如果他們本來不連通，而且y原來有邊，連通分量減一。

x, y删邊時候，如果删完他們變得不連通，而且y還有邊，連通分量加一。

在離線的同時記錄一下每一時刻球迷的度為0的個數和孤立球員的個數。

因為我們在統計到 i i i 的狀态時，若有粉絲的度為0，那麼答案為-1。也就是說若最終狀态合法，那麼粉絲一定在若幹個連通塊中，這些聯通塊中一定都有球員。是以我們隻需要統計最終連通塊的數量，那麼（最終總連通塊的數量-孤立球員個數）就是答案

線段樹上維護按秩合并可撤銷并查集，時間複雜度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

LCT維護删邊時間最大的生成樹，時間複雜度 O ( n l o g n ) O(nlogn) O(nlogn)

代碼（1）：線段樹上維護按秩合并可撤銷并查集

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x)  (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=400100;
const int maxp=800100;
const int maxm=1000100;
const int up=200000;

int n,m,q;
int f[maxn],d[maxn],top=0;
pair<int,int>st[maxn];
int cntp;
int di[maxn],cntq,cntf;

struct tree
{
    int l,r;
    vector<pair<int,int> >vc;
}t[maxn<<2];

int ans[maxn];
map<pair<int,int>,int>mp;

int fi(int x)
{
    if(f[x]==x) return x;
    else return fi(f[x]);
}

void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    t[cnt].vc.clear();
    if(l==r) return ;
    build(l,tmid,lc);
    build(tmid+1,r,rc);
}

void change(int l,int r,int cnt,pair<int,int> val)
{
    if(l>r) return ;
    if(l<=t[cnt].l&&t[cnt].r<=r)
    {
        t[cnt].vc.pb(val);
        return ;
    }
    if(t[lc].r>=l) change(l,r,lc,val);
    if(t[rc].l<=r) change(l,r,rc,val);
}

void _merge(int x,int y)
{
    int xx=fi(x),yy=fi(y);
    if(xx==yy) return ;

    cntp--;
    if(d[xx]>d[yy]) swap(xx,yy);
    st[++top]=pr(xx,d[xx]==d[yy]);
    f[xx]=yy;
    d[yy]+=(d[xx]==d[yy]);
}

void dfs(int l,int r,int cnt)
{
    int now=top;
    for(int i=0;i<t[cnt].vc.size();i++)
        _merge(t[cnt].vc[i].first,t[cnt].vc[i].second);
    if(l==r)
    {
        if(ans[l]>0) ans[l]=-1;
        else ans[l]+=cntp;
    }
    else
    {
        dfs(l,tmid,lc);
        dfs(tmid+1,r,rc);
    }
    while(top>now)
    {
        d[f[st[top].first]]-=st[top].second;
        f[st[top].first]=st[top].first;
        top--,cntp++;
    }
}


int main(void)
{
    scanf("%d%d%d",&n,&m,&q);
    cntp=n+m,cntq=n,cntf=m;
    for(int i=1;i<=n+m;i++)
        f[i]=i,d[i]=1;

    build(1,q,1);

    int k,x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&x);
            mp[pr(x+n,i)]=1;
            if(++di[i]==1) cntq--;
            if(++di[x+n]==1) cntf--;
        }
    }

    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        if(mp.count(pr(x+n,y)))
        {
            int pos=mp[pr(x+n,y)];
            mp.erase(pr(x+n,y));
            change(pos,i-1,1,pr(x+n,y));
            if(--di[y]==0) cntq++;
            if(--di[x+n]==0) cntf++;
        }
        else
        {
            mp[pr(x+n,y)]=i;
            if(++di[y]==1) cntq--;
            if(++di[x+n]==1) cntf--;
        }
        if(cntf) ans[i]=1;
        else ans[i]=-cntq;
    }
    for(auto p : mp)
        change(p.second,q,1,pr(p.first.first,p.first.second));

    dfs(1,q,1);

    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);

    return 0;
}

代碼（2）LCT維護删邊時間最大的生成樹

人醜常數大，比兩個log的線段樹分治跑的還慢。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x)  (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1100100;
const int maxp=800100;
const int maxm=1000100;
const int up=200000;

struct tree
{
    int son[2];
    int fa,minn,rev;
}t[maxn];

int st[maxn];
int deltime[maxn],isdel[maxn];
int n,m,q;
int idin[maxn];
int cnt,cntp,cntq,cntf;

struct node
{
    int x,y;
    int begintime,endtime;
    int id;
    node(){}
    node(int a,int b,int c,int d,int e)
    {
        x=a,y=b,begintime=c,endtime=d,id=e;
    }
}in[maxn],out[maxn];

bool cmpin(const node &a,const node &b)
{
    return a.begintime<b.begintime;
}
bool cmpout(const node &a,const node &b)
{
    return a.endtime<b.endtime;
}

map<pair<int,int>,int>mp;
int ans[maxn],di[maxn];


void pushup(int x)
{
    t[x].minn=x;
    if(t[x].son[0])
        t[x].minn=deltime[t[x].minn]<deltime[t[t[x].son[0]].minn]?t[x].minn:t[t[x].son[0]].minn;
    if(t[x].son[1])
        t[x].minn=deltime[t[x].minn]<deltime[t[t[x].son[1]].minn]?t[x].minn:t[t[x].son[1]].minn;
}

void _reverse(int x)
{
    if(!x) return ;
    swap(t[x].son[0],t[x].son[1]);
    t[x].rev^=1;
}

void pushdown(int x)
{
    if(!x) return ;
    if(t[x].rev)
    {
        _reverse(t[x].son[0]);
        _reverse(t[x].son[1]);
        t[x].rev=0;
    }
}

bool notroot(int x)
{
    return t[t[x].fa].son[0]==x||t[t[x].fa].son[1]==x;
}

int get_son(int x)
{
    return x==t[t[x].fa].son[1];
}

void rot(int x)
{
    int y=t[x].fa,z=t[y].fa;
    int k=get_son(x),w=t[x].son[k^1];
    t[y].son[k]=w,t[w].fa=y;

    if(notroot(y))t[z].son[get_son(y)]=x;
    t[x].fa=z;

    t[x].son[k^1]=y,t[y].fa=x;
    pushup(y),pushup(x);
}

void splay(int x)
{
    int top=0;
    st[++top]=x;
    for(int pos=x;notroot(pos);pos=t[pos].fa) st[++top]=t[pos].fa;
    while(top) pushdown(st[top--]);

    while(notroot(x))
    {
        int y=t[x].fa;
        int z=t[y].fa;
        if(notroot(y))
            if(get_son(x)==get_son(y)) rot(y);
            else rot(x);
        rot(x);
    }
}

void access(int x)
{
    for(int y=0;x;y=x,x=t[x].fa)
    {
        splay(x);
        t[x].son[1]=y;
        pushup(x);
    }
}

void makeroot(int x)
{
    access(x);
    splay(x);
    _reverse(x);
}

int findroot(int x)
{
    access(x);
    splay(x);
    while(t[x].son[0]) pushdown(x),x=t[x].son[0];
    splay(x);
    return x;
}

void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}

bool link(int x,int y)
{
    makeroot(x);
    if(findroot(y)==x) return false;
    t[x].fa=y;
    return true;
}

bool cut(int x,int y)
{
    makeroot(x);
    if(findroot(y)!=x||t[y].fa!=x||t[y].son[0]) return false;
    t[y].fa=t[x].son[1]=0;
    pushup(x);
    return true;
}

bool connected(int x,int y)
{
    x=findroot(x);
    y=findroot(y);
    return x==y;
}

//這好像就是 split 函數
void fuck(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}

void _insert(int p)
{
    deltime[in[p].id]=in[p].endtime;
    t[in[p].id].minn=in[p].id;
    int x=in[p].x,y=in[p].y,id=in[p].id;
    if(connected(x,y))
    {
        fuck(x,y);
        if(deltime[t[y].minn]>deltime[id])
            isdel[id]=1;
        else
        {
            isdel[t[y].minn]=1;

            int de=t[y].minn;
            cut(in[idin[de]].x,de);
            cut(in[idin[de]].y,de);
            link(x,id);
            link(y,id);
        }
    }
    else
    {
        link(in[p].x,in[p].id);
        link(in[p].y,in[p].id);
        cntp--;
    }
}

void del(int p)
{
    if(isdel[out[p].id])
        isdel[out[p].id]=0;
    else
    {
        cut(out[p].x,out[p].id);
        cut(out[p].y,out[p].id);
        cntp++;
    }
}

int main(void)
{
    scanf("%d%d%d",&n,&m,&q);
    cntp=n+m,cntq=n,cntf=m;
    for(int i=1;i<=n+m;i++)
        deltime[i]=inf;

    int k,x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&x);
            mp[pr(x+n,i)]=1;
            if(++di[i]==1) cntq--;
            if(++di[x+n]==1) cntf--;
        }
    }

    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        if(mp.count(pr(x+n,y)))
        {
            int pos=mp[pr(x+n,y)];
            mp.erase(pr(x+n,y));
            if(--di[y]==0) cntq++;
            if(--di[x+n]==0) cntf++;

            ++cnt;
            in[cnt]=node(x+n,y,pos,i,cnt+n+m);
            out[cnt]=in[cnt];
        }
        else
        {
            mp[pr(x+n,y)]=i;
            if(++di[y]==1) cntq--;
            if(++di[x+n]==1) cntf--;
        }
        if(cntf) ans[i]=1;
        else ans[i]=-cntq;
    }
    for(auto p : mp)
    {
        ++cnt;
        in[cnt]=node(p.first.first,p.first.second,p.second,q+1,cnt+n+m);
        out[cnt]=in[cnt];
    }

    sort(in+1,in+cnt+1,cmpin);
    sort(out+1,out+cnt+1,cmpout);
    for(int i=1;i<=cnt;i++)
        idin[in[i].id]=i;

    int cntin=1,cntout=1;
    for(int i=1;i<=q;i++)
    {
        while(cntin<=cnt&&in[cntin].begintime<=i)
            _insert(cntin++);
        while(cntout<=cnt&&out[cntout].endtime<=i)
            del(cntout++);
        if(ans[i]==1) printf("-1\n");
        else printf("%d\n",ans[i]+cntp);
    }

    return 0;
}
lct 主席樹/線段樹
上一篇: [HNOI2016]大數
下一篇: CodeChef - GERALD07 Chef and Graph Queries題面題意做法代碼

繼續閱讀