HDU 5333 [LCT][树状数组]

Description

给定一张图，求编号在 [L,R] 之间的点的导出子图的连通块个数。

Solution

和这道题很像的吧。。
离线做，也是类似地记录一个 pre 值。
每条边的权值定为连接的两个点编号的 Min 。

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 304040;
const int INF = 1 << 30;
typedef pair<int, int> P;
inline char get(void) {
static char buf[100000], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, 100000, stdin);
if (S == T) exit(0);
}
return *S++;
}
inline void read(int &x) {
static char c; x = 0;
for (c = get(); c < '0' || c > '9'; c = get());
for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
}
inline int Min(int a, int b) {
return a < b ? a : b;
}
inline int Max(int a, int b) {
return a > b ? a : b;
}
int n, m, q, x, y, cnt, Mcnt;
int fa[N], rk[N];
int ans[N];
struct node {
node *ch[2];
node *fa;
int mn, rev, id, key, mnk;
inline void PushDown(void) {
if (rev) {
ch[0]->rev ^= 1;
ch[1]->rev ^= 1;
swap(ch[0], ch[1]);
rev = 0;
}
}
inline void PushUp(void) {
mn = id; mnk = key;
if (ch[0]->mn < mn) {
mn = ch[0]->mn;
mnk = ch[0]->mnk;
}
if (ch[1]->mn < mn) {
mn = ch[1]->mn;
mnk = ch[1]->mnk;
}
}
};
node *null;
node T[N];
vector<P> Q[N];
vector<int> G[N];
namespace BIT {
int c[N];
int maxn;
int Init(int n) {
maxn = n + 1;
for (int i = 1; i <= maxn; i++) c[i] = 0;
}
inline void Add(int x, int a) {
for (++x; x <= maxn; x += x & -x) c[x] += a;
}
inline int Sum(int x) {
int sum = 0; ++x;
for (; x; x -= x & -x) sum += c[x];
return sum;
}
inline int Sum(int x, int y) {
return Sum(y) - Sum(x - 1);
}
}
inline int Fa(int x) {
return fa[x] == x ? x : fa[x] = Fa(fa[x]);
}
inline int Merge(int x, int y) {
static int f1, f2;
f1 = Fa(x); f2 = Fa(y);
if (f1 == f2) return 0;
if (rk[f1] < rk[f2]) swap(f1, f2);
if (rk[f1] == rk[f2]) rk[f1]++;
fa[f2] = f1; return 1;
}
inline bool IsRoot(node* x) {
return x->fa == null || (x->fa->ch[0] != x && x->fa->ch[1] != x);
}
inline void Rotate(node* x) {
node *y = x->fa, *z = y->fa;
int l = (y->ch[0] != x), r = l ^ 1;
if (!IsRoot(y)) {
if (z->ch[0] == y) z->ch[0] = x;
else z->ch[1] = x;
}
x->fa = z; y->fa = x; x->ch[r]->fa = y;
y->ch[l] = x->ch[r]; x->ch[r] = y;
y->PushUp(); x->PushUp();
}
inline void Down(node* x) {
if (!IsRoot(x)) Down(x->fa);
x->PushDown();
}
inline void Splay(node* x) {
Down(x);
while (!IsRoot(x)) {
node *y = x->fa, *z = y->fa;
if (!IsRoot(y)) {
if (y->ch[0] == x ^ z->ch[0] == y) Rotate(x);
else Rotate(y);
}
Rotate(x);
}
}
inline void Access(node* x) {
for (node *y = null; x != null; x = x->fa) {
Splay(x); x->ch[1] = y;
x->PushUp(); y = x;
}
}
inline void MakeRoot(node* x) {
Access(x); Splay(x); x->rev = 1;
}
inline void Link(node* x, node* y) {
MakeRoot(x); x->fa = y;
}
inline void Cut(node* x, node* y) {
MakeRoot(x); Access(y); Splay(y);
x->fa = y->ch[0] = null; y->PushUp();
}
inline int Query(node* x, node* y) {
MakeRoot(x); Access(y); Splay(y);
return y->mn;
}
inline void New(node* x) {
x->ch[0] = x->ch[1] = x->fa = null;
x->mn = x->id = INF; x->rev = 0;
}
inline void Init(int n) {
null = T;
null->ch[0] = null->ch[1] = null->fa = null;
null->mn = INF;
for (int i = 1; i <= n; i++) New(T + i);
}
inline void AddEdge(int x, int y) {
if (x == y) return;
int res = 0, pos;
if (Merge(x, y)) {
++Mcnt;
New(T + (++cnt));
T[cnt].id = Min(x, y);
T[cnt].key = cnt;
T[cnt].PushUp();
Link(T + x, T + cnt);
Link(T + y, T + cnt);
BIT::Add(y, 1);
} else {
res = Query(T + x, T + y);
if (res < y) {
pos = T[y].mnk;
Cut(T + x, T + pos);
Cut(T + y, T + pos);
BIT::Add(res, -1);
New(T + (++cnt));
T[cnt].id = Min(x, y);
T[cnt].key = cnt;
T[cnt].PushUp();
Link(T + x, T + cnt);
Link(T + y, T + cnt);
BIT::Add(y, 1);
}
}
}
int main(void) {
while (true) {
read(n); read(m); read(q); Mcnt = 0;
Init(cnt = n); BIT::Init(n);
for (int i = 1; i <= n; i++) {
fa[i] = i; G[i].clear(); Q[i].clear();
}
for (int i = 1; i <= m; i++) {
read(x); read(y);
if (x > y) swap(x, y);
G[y].push_back(x);
}
for (int i = 1; i <= q; i++) {
read(x); read(y);
Q[y].push_back(P(x, i));
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < G[i].size(); j++)
AddEdge(i, G[i][j]);
for (int j = 0; j < Q[i].size(); j++)
ans[Q[i][j].second] = Mcnt - BIT::Sum(Q[i][j].first - 1);
}
for (int i = 1; i <= q; i++)
printf("%dn", n - ans[i]);
}
return 0;
}

最后

以上就是甜美墨镜为你收集整理的HDU 5333 [LCT][树状数组]的全部内容，希望文章能够帮你解决HDU 5333 [LCT][树状数组]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。