BZOJ3514: Codechef MARCH14 GERALD07加强版【LCT】【主席树】【思维】

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

思路

考虑怎么解决联通块个数

首先我们如果从左向右扫所有的边加进联通块中

可以用LCT维护一个动态的生成树

然后一旦出现环就删除环中编号最小的一个边

然后我们考虑一下左端点如果大于当前删除的边的编号，实际上还是存在这个联通块的

所以说我们只需要统计在\([l,r]\)这个区间中左端点小于\(l\)的个数就可以知道有多少个联通块了

然后当当前节点存在自环的时候就会发现他的删除的边的编号就是自己，不然会有多余的贡献

然后主席树维护就没了

#include<bits/stdc++.h>

using namespace std;

const int N = 4e5 + 10;

int n, m, k, typ;

int u[N], v[N];

int lastans = 0;

namespace Link_Cut_Tree {

int ch[N][2], fa[N], minval[N], val[N], rev[N], cnt = 0;

bool isroot(int t) {

  return ch[fa[t]][0] != t && ch[fa[t]][1] != t;

}

void pushup(int t) {

  minval[t] = val[t];

  if (ch[t][0]) minval[t] = min(minval[t], minval[ch[t][0]]);

  if (ch[t][1]) minval[t] = min(minval[t], minval[ch[t][1]]);

}

void pushnow(int t) {

  swap(ch[t][0], ch[t][1]);

  rev[t] ^= 1;

}

void pushdown(int t) {

  if (!isroot(t)) pushdown(fa[t]);

  if (rev[t]) {

    pushnow(ch[t][0]);

    pushnow(ch[t][1]);

    rev[t] = 0;

  }

}

void newnode(int vl) {

  ++cnt;

  fa[cnt] = ch[cnt][0] = ch[cnt][1] = 0;

  minval[cnt] = val[cnt] = vl;

  rev[cnt] = 0;

}

bool son(int t) {

  return t == ch[fa[t]][1];

}

void rotate(int t) {

  int f = fa[t], g = fa[f];

  bool a = son(t), b = a ^ 1;

  if (!isroot(f)) ch[g][son(f)] = t;

  fa[t] = g;

  ch[f][a] = ch[t][b];

  fa[ch[t][b]] = f;

  ch[t][b] = f;

  fa[f] = t;

  pushup(f);

  pushup(t);

}

void splay(int t) {

  pushdown(t);

  while (!isroot(t)) {

    int f = fa[t];

    if (!isroot(f)) {

      if (son(f) ^ son(t)) rotate(t);

      else rotate(f);

    }

    rotate(t);

  }

}

void access(int t) {

  int tmp = 0; // 需要设定初值

  while (t) {

    splay(t);

    ch[t][1] = tmp;

    pushup(t);

    tmp = t;

    t = fa[t];

  }

}

void makeroot(int t) {

  access(t);

  splay(t);

  pushnow(t);

}

void link(int x, int y) {

  makeroot(x);

  fa[x] = y;

}

void cut(int x, int y) {

  makeroot(x);

  access(y);

  splay(y);

  fa[x] = ch[y][0] = 0;

  pushup(y);

}

};

using Link_Cut_Tree::minval;

using Link_Cut_Tree::newnode;

using Link_Cut_Tree::link;

using Link_Cut_Tree::cut;

using Link_Cut_Tree::makeroot;

using Link_Cut_Tree::access;

namespace Functional_Segment_Tree {

const int LOG = 30;

int cnt = 0;

int siz[N * LOG], ls[N * LOG], rs[N * LOG], rt[N];

void insert(int &t, int last, int l, int r, int pos) {

  t = ++cnt;

  ls[t] = ls[last];

  rs[t] = rs[last];

  siz[t] = siz[last] + 1;

  if (l == r) return;

  int mid = (l + r) >> 1;

  if (pos <= mid) insert(ls[t], ls[last], l, mid, pos);

  else insert(rs[t], rs[last], mid + 1, r, pos);

}

int query(int t, int last, int l, int r, int ql, int qr) {

  if (ql <= l && r <= qr) return siz[t] - siz[last];

  int mid = (l + r) >> 1;

  if (qr <= mid) return query(ls[t], ls[last], l, mid, ql, qr);

  else if (ql > mid) return query(rs[t], rs[last], mid + 1, r, ql, qr);

  else return query(ls[t], ls[last], l, mid, ql, mid) + query(rs[t], rs[last], mid + 1, r, mid + 1, qr);

}

};

using Functional_Segment_Tree::rt;

using Functional_Segment_Tree::insert;

using Functional_Segment_Tree::query;

namespace Union_Find {

int fa[N << 1];

void init() {

  for (int i = 1; i <= n; i++)

    fa[i] = i;

}

int find(int x) {

  return x == fa[x] ? x : fa[x] = find(fa[x]);

}

bool merge(int x, int y) {

  int fax = find(x), fay = find(y);

  if (fax == fay) return 0;

  fa[fax] = fay;

  return 1;

} 

}

using Union_Find::init;

using Union_Find::merge;

int main() {

#ifdef dream_maker

  freopen("input.txt", "r", stdin);

#endif

  scanf("%d %d %d %d", &n, &m, &k, &typ);

  for (int i = 1; i <= n; i++) newnode(m + 1);

  for (int i = 1; i <= m; i++) newnode(i);

  init();

  for (int i = 1; i <= m; i++) {

    scanf("%d %d", &u[i], &v[i]);

    if (u[i] == v[i]) {

      insert(rt[i], rt[i - 1], 0, m, i);

      continue;

    }

    if (merge(u[i], v[i])) {

      insert(rt[i], rt[i - 1], 0, m, 0);

      link(u[i], n + i);

      link(v[i], n + i);

    } else {

      makeroot(u[i]);

      access(v[i]);

      makeroot(v[i]);

      int cur = minval[v[i]];

      cut(v[cur], n + cur);

      cut(u[cur], n + cur);

      link(v[i], n + i);

      link(u[i], n + i);

      insert(rt[i], rt[i - 1], 0, m, cur);

    }

  }

  for (int i = 1; i <= k; i++) {

    int l, r; scanf("%d %d", &l, &r);

    if (typ) l ^= lastans, r ^= lastans;

    if (l > r) swap(l, r);

    lastans = n - query(rt[r], rt[l - 1], 0, m, 0, l - 1);

    printf("%d\n", lastans);

  }

  return 0;

}

巴特西