(TIOJ) 1903 . 【Gate】這個笑容由我來守護 - EXTREME [可刪邊並查集] [時間線段樹] [unodered_map]

http://tioj.ck.tp.edu.tw/problems/1903

((解釋有空再補))

#include <iostream>
#include <stdio.h>
#include <utility>
#include <map>
#include <set>
#include <vector>
#include <cassert>
#include <unordered_map>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
const LL MAX_N = 5e5 + 6;
namespace std {
  template <> struct hash<pii> {
    LL operator()(const pii &p) const {
      return p.first*MAX_N+p.second;
    }
  };
}

struct Node {
    static Node mem[4*MAX_N];
    Node *lc,*rc;
    vector<pii> v;
    Node() {
        lc=rc=NULL;
        v.clear();
    }
} Node::mem[4*MAX_N],*ptr=Node::mem;

Node* Build(int L,int R) {
    Node* node=new(ptr++)Node();
    if (L==R) {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    return node;
}

void modify(Node* node,int L,int R,int l,int r,pii edge) {
    if (L>r || l>R) return;
    else if (l<=L && R<=r) {
        node->v.push_back(edge);
        return;
    }
    int mid=(L+R)>>1;
    modify(node->lc,L,mid,l,r,edge);
    modify(node->rc,mid+1,R,l,r,edge);
}

int ans[MAX_N];

struct Event {
    int tx,ty;
    int ori_sz_tx,ori_sz_ty;
    int ori_p_tx,ori_p_ty;
    pii range;
    void gao(int _tx,int _ty,int _ori_sz_tx,int _ori_sz_ty,int _ori_p_tx,int _ori_p_ty,pii _range) {
        tx=_tx;
        ty=_ty;
        ori_sz_tx=_ori_sz_tx;
        ori_sz_ty=_ori_sz_ty;
        ori_p_tx=_ori_p_tx;
        ori_p_ty=_ori_p_ty;
        range=_range;
    }
};

vector<Event> ee;

struct DisjointSet {
    int p[MAX_N];
    int sz[MAX_N];
    int ans;
    void init(int n) {
        ans=n;
        for (int i=0;n>=i;i++) {
            p[i] = i;
            sz[i]=1;
        }
    }
    int Find(int x) {
        return p[x]==x?x:Find(p[x]);
    }
    void Union(int x,int y,pii range) {
        int tx=Find(x);
        int ty=Find(y);
        if (tx == ty) {
            return;
        }
        if (sz[tx] < sz[ty]) swap(tx,ty);
        assert(sz[tx]>=sz[ty]);
        Event e;
        e.gao(tx,ty,sz[tx],sz[ty],p[tx],p[ty],range);
        ee.push_back(e);
        sz[tx] += sz[ty];
        p[ty] = p[tx];
        ans--;
    }
    void recover(Event e) {
        p[e.tx] = e.ori_p_tx;
        p[e.ty] = e.ori_p_ty;
        sz[e.tx] = e.ori_sz_tx;
        sz[e.ty] = e.ori_sz_ty;
        ans++;
    }
} djs;

void visit(Node* node,int L,int R) {
    //deal with the edges
    pii range=make_pair(L,R);
    for (pii i:node->v) {
        djs.Union(i.first,i.second,range);
    }
    if (L==R) {
        ans[L] = djs.ans;
    }
    else {
        int mid=(L+R)>>1;
        visit(node->lc,L,mid);
        visit(node->rc,mid+1,R);
    }
    while (!ee.empty() && ee.back().range == range) {
        djs.recover(ee.back());
        ee.pop_back();
    }
}

LL hash(pii i) {
    return i.first*MAX_N+i.second;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        ptr=Node::mem;
        int n,m,q;
        scanf("%d %d %d",&n,&m,&q);
        djs.init(n);
        Node* root=Build(1,q+1);
        unordered_map<pii,pii> mp;  //start,count
        for (int i=1;m>=i;i++) {
            int a,b;
            scanf("%d %d",&a,&b);
            if (a>b) swap(a,b);
            pii edge=make_pair(a,b);
            pii ret=mp[edge];
            if (ret == make_pair(0,0)) ret=make_pair(1,1);
            else ret.second++;
            mp[edge]=ret;
        }
        int nn=q+1;
        for (int i=2;q+1>=i;i++) {
            getchar();
            char c;
            int a,b;
            scanf("%c %d %d",&c,&a,&b);
            if (a>b) swap(a,b);
            pii edge=make_pair(a,b);
            if (c=='N') {
                pii ret=mp[edge];
                if (ret == make_pair(0,0)) mp[edge] = make_pair(i,1);
                else {
                    ret.second++;
                    mp[edge]=ret;
                }
            }
            else if (c=='D') {
                pii ret=mp[edge];
                ret.second--;
                if (ret.second==0) {
                    modify(root,1,nn,ret.first,i-1,edge);
                    ret=make_pair(0,0);
                }
                mp[edge]=ret;
            }
        }
        for (auto p:mp) {
            pii edge=p.first;
            pii st=p.second;
            if (st.second==0) continue;
            modify(root,1,nn,st.first,q+1,edge);
        }
        visit(root,1,nn);
        for (int i=2;nn>=i;i++) {
            printf("%d\n",ans[i]);
        }
    }
}