题目：

分析：

很明显，查询的是删掉某条边后两端点所在连通块大小的乘积。

有加边和删边，想到LCT。但是我不会用LCT查连通块大小啊。~~果断弃了~~

有加边和删边，还跟连通性有关，于是开始yy线段树分治做法（不知道线段树分治？推荐一个~~伪模板~~题~~事实上这个链接是指向我的博客的~~）。把每次操作（加边或查询）看做一个时刻，一条边存在的区间就是它加入后没有被查询的时间区间的并。于是用可撤销并查集维护一下连通块大小即可。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #undef i#undef j#undef k#undef min#undef max#undef true#undef false#undef swap#undef sort#undef if#undef for#undef while#undef printf#undef scanf#undef putchar#undef getchar#define _ 0using namespace std;namespace zyt{ template
          
            inline bool read(T &x) { char c; bool f = false; x = 0; do c = getchar(); while (c != EOF && c != '-' && !isdigit(c)); if (c == EOF) return false; if (c == '-') f = true, c = getchar(); do x = x * 10 + c - '0', c = getchar(); while (isdigit(c)); if (f) x = -x; return true; } inline bool read(char &c) { do c = getchar(); while (c != EOF && !isgraph(c)); return c != EOF; } template
           
             inline void write(T x) { static char buf[20]; char *pos = buf; if (x < 0) putchar('-'), x = -x; do *pos++ = x % 10 + '0'; while (x /= 10); while (pos > buf) putchar(*--pos); } typedef long long ll; const int N = 1e5 + 10, B = 17, QUERY = 0, ADD = 1; int n, q; ll ans[N]; struct node { bool type; int x, y; }arr[N]; namespace UFS { int fa[N], rk[N], size[N], top; struct node { int x, y, fax, rky, sizey; }stack[N]; void init(const int n) { for (int i = 1; i <= n; i++) fa[i] = i, rk[i] = size[i] = 1; } int f(const int u) { return fa[u] == u ? u : f(fa[u]); } bool merge(const int u, const int v) { int x = f(u), y = f(v); if (x == y) return false; if (rk[x] > rk[y]) swap(x, y); stack[top++] = (node){x, y, fa[x], rk[y], size[y]}; fa[x] = y, size[y] += size[x]; if (rk[x] == rk[y]) ++rk[y]; return true; } int query(const int u) { assert(f(u) < N); return size[f(u)]; } void undo(const int bck) { while (top > bck) { --top; int x = stack[top].x, y = stack[top].y; assert(x < N && y < N); fa[x] = stack[top].fax; rk[y] = stack[top].rky; size[y] = stack[top].sizey; } } } namespace Segment_Tree { struct edge { int x, y, next; }e[N * (B + 1)]; int head[1 << (B + 1) | 11], ecnt; inline void init() { memset(head, -1, sizeof(head)); } inline void add(const int a, const int b, const int c) { e[ecnt] = (edge){b, c, head[a]}, head[a] = ecnt++; } inline void insert(const int rot, const int lt, const int rt, const int ls, const int rs, const int x, const int y) { if (ls <= lt && rt <= rs) { add(rot, x, y); return; } int mid = (lt + rt) >> 1; if (ls <= mid) insert(rot << 1, lt, mid, ls, rs, x, y); if (rs > mid) insert(rot << 1 | 1, mid + 1, rt, ls, rs, x, y); } inline void solve(const int rot, const int lt, const int rt) { int bck = UFS::top; for (int i = head[rot]; ~i; i = e[i].next) UFS::merge(e[i].x, e[i].y); if (lt == rt) { if (arr[lt].type == QUERY) ans[lt] = (ll)UFS::query(arr[lt].x) * UFS::query(arr[lt].y); UFS::undo(bck); return; } int mid = (lt + rt) >> 1; solve(rot << 1, lt, mid); solve(rot << 1 | 1, mid + 1, rt); UFS::undo(bck); } } map
            
             
              , int> lastins; int work() { read(n), read(q); UFS::init(n); Segment_Tree::init(); for (int i = 1; i <= q; i++) { char opt; read(opt), read(arr[i].x), read(arr[i].y); if (arr[i].x > arr[i].y) swap(arr[i].x, arr[i].y); arr[i].type = (opt == 'Q' ? QUERY : ADD); pair
              
                p = make_pair(arr[i].x, arr[i].y); if (arr[i].type == ADD) lastins[p] = i; else { Segment_Tree::insert(1, 1, q, lastins[p], i - 1, p.first, p.second); lastins[p] = i + 1; } } for (map
               
                
                 , int>::iterator it = lastins.begin(); it != lastins.end(); it++) if (it->second <= q) Segment_Tree::insert(1, 1, q, it->second, q, it->first.first, it->first.second); Segment_Tree::solve(1, 1, q); for (int i = 1; i <= q; i++) if (arr[i].type == QUERY) write(ans[i]), putchar('\n'); return (0^_^0); }}int main(){ return zyt::work();}

转载于:https://www.cnblogs.com/zyt1253679098/p/10265586.html

你可能感兴趣的文章