OI

BZOJ 3514: Codechef MARCH14 GERALD07加强版

Description

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

Input

第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。

接下来M行，代表图中的每条边。

接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

Output

K行每行一个整数代表该组询问的联通块个数。

Sample Input

3 5 4 0

1 3

1 2

2 1

3 2

2 2

2 3

1 5

5 5

1 2

Sample Output

2

1

3

1

HINT

对于100%的数据，1≤N、M、K≤200,000。

2016.2.26提高时限至60s

Solution

Link-Cut-Tree + 可持久化线段树。

假设我们已经有一张图G，联通块个数为k，考虑加入边(u,v)：

  1. (u,v)连接了两个联通块；
  2. (u,v)与之前的某些边形成了一个双联通分量（环）。

那么1对答案有-1的贡献，2对答案是没有贡献的。

假设我们考虑到了第i条边，如果存在一个最大的a_i，满足加入a_i…i-1这些边能使得加入第i条边没有贡献，那么加入j…i-1(j<=a_i)这些边也能使得i这条边没有贡献。

假设我们已经求出来了a数组，考虑如何在线回答每次询问？

转换一下原问题，容易发现原问题相当于求l<=i<=r,a_i<l的边的个数。

Query(l,r)=N-Sum_i [l<=i<=r且a_i<l]

用可持久化线段树可以比较方便的做出来，离线的话可以树状数组+扫描线搞。

现在考虑a数组怎么求。

依次加入每一条边，按照边的序号维护前i条边的最大生成树，第i条边加入后如果导致某条边从LCT中删掉，删掉的那条边就是我们要求的a_i。

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

#include <cstdio>
#include <assert.h>
#include <algorithm>
using namespace std;
const int N = 200020;
const int INF = 2147483647;
inline int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int w[N<<1], u[N], v[N], a[N], root[N];
namespace LCT {
    int fa[N<<1], mipos[N<<1], c[N<<1][2], rev[N<<1], sta[N<<1], tail;
    void Init(int tot) {
        for (int i = 0; i <= tot; ++i) {
            rev[i] = fa[i] = c[i][0] = c[i][1] = 0;
            mipos[i] = i;
        }
    }
    bool IsRT(int x) {
        return c[fa[x]][0] != x && c[fa[x]][1] != x;
    }
    void Down(int x) {
        if (rev[x]) {
            int &lc = c[x][0], &rc = c[x][1];
            if (lc) rev[lc] ^= 1;
            if (rc) rev[rc] ^= 1;
            swap(lc, rc);
            rev[x] = 0;
        }
    }
    void Push(int x) {
        mipos[x] = x;
        int &lc = c[x][0], &rc = c[x][1];
        if (lc && w[mipos[lc]] < w[mipos[x]])
            mipos[x] = mipos[lc];
        if (rc && w[mipos[rc]] < w[mipos[x]])
            mipos[x] = mipos[rc];
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y], a = (c[y][1] == x), b = a ^ 1;
        if (!IsRT(y)) c[z][c[z][1]==y] = x;
        fa[x] = z; fa[y] = x; if (c[x][b]) fa[c[x][b]] = y;
        c[y][a] = c[x][b]; c[x][b] = y;
        Push(y); Push(x);
    }
    void Splay(int x) {
        sta[++tail] = x;
        for (int i = x; !IsRT(i); i = fa[i])
            sta[++tail] = fa[i];
        while (tail) Down(sta[tail--]);
        while (!IsRT(x)) {
            int y = fa[x];
            if (!IsRT(y)) {
                if (c[fa[y]][0] == y ^ c[y][0] == x) Rotate(x);
                else Rotate(y);
            }
            Rotate(x);
        }
    }
    void Access(int x) {
        int y = 0;
        while (x) {
            Splay(x);
            c[x][1] = y;
            Push(x);
            y = x;
            x = fa[x];
        }
    }
    void MkRT(int x) {
        Access(x);
        Splay(x);
        rev[x] ^= 1;
    }
    void Link(int x, int y) {
        MkRT(x);
        fa[x] = y;
    }
    void Cut(int x, int y) {
        MkRT(x);
        Access(y);
        Splay(x);
        c[x][1] = 0;
        fa[y] = 0;
    }
    int FindRT(int x) {
        Access(x);
        Splay(x);
        while (c[x][0]) x = c[x][0];
        return x;
    }
    int Query(int x, int y) {
        MkRT(x);
        Access(y);
        Splay(y);
        return mipos[y];
    }
}
namespace SGT {
    int lc[N * 22], rc[N * 22], sum[N * 22], tot;
    void Init() {
        tot = 0;
    }
    void Build(int &x, int l, int r) {
        x = ++tot;
        sum[x] = 0;
        if (l == r) lc[x] = rc[x] = 0;
        else {
            int mid = (l + r) >> 1;
            Build(lc[x], l, mid);
            Build(rc[x], mid+1, r);
        }
    }
    void Add(int &x, int y, int l, int r, const int pos) {
        x = ++tot;
        lc[x] = lc[y];
        rc[x] = rc[y];
        sum[x] = sum[y] + 1;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (pos <= mid) Add(lc[x], lc[y], l, mid, pos);
        else Add(rc[x], rc[y], mid+1, r, pos);
    }
    int Ask(int x, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) return sum[x];
        int mid = (l + r) >> 1, ret = 0;
        if (ll <= mid) ret += Ask(lc[x], l, mid, ll, rr);
        if (rr > mid) ret += Ask(rc[x], mid+1, r, ll, rr);
        return ret;
    }
}
int x, y, n, m, q, T, ans;
int main() {
    n = getint(); m = getint(); q = getint(); T = getint();
    LCT::Init(n + m);
    SGT::Init();
    for (int i = 1; i <= n; ++i)
        w[i] = INF;
    for (int i = 1; i <= m; ++i) {
        u[i] = getint();
        v[i] = getint();
        w[i+n] = i;
    }
    for (int i = 1; i <= m; ++i) {
        if (u[i] == v[i]) a[i] = i;
        else {
            if (LCT::FindRT(u[i]) == LCT::FindRT(v[i])) {
                x = LCT::Query(u[i], v[i]);
                a[i] = x - n;
                LCT::Cut(u[x-n], x);
                LCT::Cut(x, v[x-n]);
            }
            else a[i] = 0;
            LCT::Link(u[i], i + n);
            LCT::Link(i + n, v[i]);
        }
    }
    SGT::Build(root[0], 1, m + 1);
    for (int i = 1; i <= m; ++i)
		SGT::Add(root[i], root[i-1], 1, m + 1, a[i] + 1);
	for (int i = 1; i <= q; ++i) {
        x = getint(); y = getint();
        if (T) {
            x ^= ans;
            y ^= ans;
        }
        ans = n - SGT::Ask(root[y], 1, m + 1, 1, x) + SGT::Ask(root[x-1], 1, m + 1, 1, x);
        printf("%d\n", ans);
    }
}