题目地址：BZOJ：Problem 3514. — Codechef MARCH14 GERALD07加强版

题目描述

N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。

输入输出格式

输入格式：
第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。
接下来M行，代表图中的每条边。
接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

输出格式：
K行每行一个整数代表该组询问的联通块个数。

输入输出样例

输入样例#1：

3 5 4 0
1 3
1 2
2 1
3 2
2 2
2 3
1 5
5 5
1 2

输出样例#1：

2
1
3
1

说明

对于100%的数据，1≤N、M、K≤200,000。
2016.2.26提高时限至60s

题解

首先这题强制在线了。考虑原来的GERALD07是怎么做的，用LCT来维护生成树，LCT记录下当前连通块内编号最小的边，离线处理答案，权值线段树来查符合条件的边数，答案即为n-边数。该题链接见：[CC-GERALD07]Chef and Graph Queries 题解 | KSkun’s Blog。
现在搞在线了怎么搞，那我们考虑把权值线段树改成主席树，然后查另外一个答案。我们在加边的过程中检查是否成环，成环了就把环中编号最小的边给删掉，然后把这条边的编号记下来。对于编号为[l, r]的边，问题的答案即n-这一段编号的边插入的时候删掉的编号小于l的边的数量。
下面我们证明它的正确性。对于一个加边时删边编号不小于l的边，其实删不删这一块本来就是连通的，并不能对答案产生贡献；反过来，删掉了前面那条边，其实这里并不连通了，此时把这条边加上以后变联通，其实对答案来说有-1的贡献。
至于n-的原因，如果原始有n个点没有边，那就是n个连通块，此时加1条边，就会合并掉某两个连通块，答案变为n-1，以此类推。
这个代码的常数巨大，复杂度没有用，就算BZOJ开了60s我也是蹭着限制AC的，太吓人了。

代码

// Code by KSkun, 2018/3
#include <cstdio>

inline void swap(int &a, int &b) {
    register int t = a;
    a = b;
    b = t;
}

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 400005, INF = 1e9;

struct LCTNode {
    int ch[2], fa, val, mn;
    bool rev;
} lct[MAXN];

inline bool isleft(int p) {
    return lct[lct[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    register int fa = lct[p].fa;
    return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
}

inline void update(int p) {
    register int ls = lct[p].ch[0], rs = lct[p].ch[1];
    lct[p].mn = p;
    if(lct[lct[ls].mn].val < lct[lct[p].mn].val) lct[p].mn = lct[ls].mn;
    if(lct[lct[rs].mn].val < lct[lct[p].mn].val) lct[p].mn = lct[rs].mn;
}

inline void reverse(int p) {
    swap(lct[p].ch[0], lct[p].ch[1]);
    lct[p].rev ^= 1;
}

inline void pushdown(int p) {
    register int ls = lct[p].ch[0], rs = lct[p].ch[1];
    if(lct[p].rev) {
        if(ls) reverse(ls);
        if(rs) reverse(rs);
        lct[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p;
        p = lct[p].fa;
    }
    pushdown(p);
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
    lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
    lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
    lct[p].ch[!t] = fa; lct[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(register int q = 0; p; q = p, p = lct[p].fa) {
        splay(p);
        lct[p].ch[1] = q;
        update(p);
    }
}

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

inline int findrt(int p) {
    access(p);
    splay(p);
    while(lct[p].ch[0]) p = lct[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

inline void link(int u, int v) {
    split(u, v);
    lct[u].fa = v;
}

inline void cut(int u, int v) {
    split(u, v);
    if(lct[v].ch[0] != u || lct[lct[v].ch[0]].ch[1]) return;
    lct[u].fa = lct[v].ch[0] = 0;
}

inline int query(int u, int v) {
    split(u, v);
    return lct[v].mn;
}

struct SGTNode {
    int val, lch, rch;
} sgt[MAXN * 20];
int stot = 0, rt[MAXN];

inline void insert(int &o, int l, int r, int x) {
    sgt[++stot] = sgt[o]; o = stot;
    sgt[o].val++;
    if(l == r) return;
    register int mid = (l + r) >> 1;
    if(x <= mid) insert(sgt[o].lch, l, mid, x);
    else insert(sgt[o].rch, mid + 1, r, x);
}

inline int query(int o1, int o2, int l, int r, int rr) {
    if(r == rr) return sgt[o2].val - sgt[o1].val;
    register int mid = (l + r) >> 1;
    if(rr <= mid) return query(sgt[o1].lch, sgt[o2].lch, l, mid, rr);
    else return sgt[sgt[o2].lch].val - sgt[sgt[o1].lch].val + query(sgt[o1].rch, sgt[o2].rch, mid + 1, r, rr);
}

int n, m, q, type, ut, vt, lst[MAXN], u[MAXN], v[MAXN];

int main() {
    n = readint(); m = readint(); q = readint(); type = readint();
    lct[0].val = INF;
    for(register int i = 1; i <= n; i++) {
        lct[i].mn = i;
        lct[i].val = INF;
    }
    register int tot = n;
    for(register int i = 1; i <= m; i++) {
        ut = u[i] = readint(); vt = v[i] = readint();
        if(ut == vt) {
            lst[i] = i;
            continue;
        }
        if(findrt(ut) == findrt(vt)) {
            int t = query(ut, vt), tv = lct[t].val;
            lst[i] = tv;
            cut(u[tv], t);
            cut(v[tv], t);
        }
        tot++;
        lct[tot].mn = tot;
        lct[tot].val = i;
        link(ut, tot);
        link(vt, tot);
    }
    for(register int i = 1; i <= m; i++) {
        rt[i] = rt[i - 1];
        insert(rt[i], 0, m, lst[i]);
    }
    register int lastans = 0;
    while(q--) {
        ut = readint(); vt = readint();
        if(type) {
            ut ^= lastans;
            vt ^= lastans;
        }
        printf("%d\n", lastans = n - query(rt[ut - 1], rt[vt], 0, m, ut - 1));
    }
    return 0;
}