BZOJ5218: [Lydsy2017省队十连测]友好城市

Description

在Byteland 一共有n 座城市，编号依次为1 到n，这些城市之间通过m 条单向公路连接。对于两座不同的城市a 和

b，如果a 能通过这些单向道路直接或间接到达b，且b 也能如此到达a，那么它们就会被认为是一对友好城市。Byt

eland 的交通系统十分特殊，第i 天只有编号在[li, ri] 的单向公路允许通行，请写一个程序，计算每天友好城

市的对数。

注意：(a, b) 与(b, a) 没有区别。

Input

第一行包含三个正整数n, m, q，分别表示城市的个数、单向公路的条数以及询问的天数。

接下来m 行，每行两个正整数ui, vi，表示一条从城市ui 出发，通往城市vi 的单向道路。

接下来q 行，每行两个正整数li, ri，表示一个询问。

1 ≤ ui, vi ≤ n, ui != vi, 1 ≤ li ≤ ri ≤ m。N<=150,M<=300000,Q<=50000

Output

输出q 行，每行一个整数，即友好城市的对数。

Sample Input

3 3 3
1 2
2 3
2 1
1 1
1 2
1 3

Sample Output

0
0
1

HINT

Source

首先我们要了解一下一种复杂度可以和操作系统位数有关的强连通缩点算法：O((n^2)/32)的Kosaraju算法：前往了解。用邻接矩阵这个算法本来是O(n^2)的，考虑怎么除一个32下来：我们每一次都把边表&上able数组，如果一个点i未被到达过那么able[i]=1，否则able[i]=0。然后每一次我们一边for循环一边lowbit，就可以精确找到所有没有被到达过的有连边点。然后剩下的问题是知道2^n是多少，如何知道n了，这个地方我们写了个哈希，根据生日悖论我们开10001的哈希池稳得一逼。(builtin是啥？喵喵喵？)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long
#define UB Ultra_Bitset
#define ui unsigned int
#define lowbit(x) (x & (-x))
#define Down(i, a, b) for(int i = a; i >= b; --i)
#define For(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
const int N = 152, B = 32, P = 10001;
const int maxn = 3e5 + 5, BLK = 500;
int rest[N], dv[N];
struct Query {
	int l, r, lb, rb, id;
	void init(int rl, int rr, int rid) 
	{l = rl, r = rr, id = rid, lb = l / BLK, rb = r / BLK;}
	bool operator < (const Query & A) const {
		return lb == A.lb ? ((lb & 1) ? rb > A.rb : rb < A.rb) : (lb < A.lb);
	}
} qs[50005];
struct edge {
	int u, v;
} e[maxn];
struct UB {
	ui b[5];
	void operator &= (const UB & A) {For(i, 0, 4) b[i] = A.b[i];}
	void clear() {b[0] = b[1] = b[2] = b[3] = b[4] = 0;}
	void e1(const int &pos) {
		b[dv[pos]] |= 1u << rest[pos];
	}
	void e0(const int &pos) {
		b[dv[pos]] &= ~(1u << rest[pos]);
	}
	bool operator [] (const int &a) {return b[dv[a]] & (1u << rest[a]);}
} mp[152], rev[152], ch[152], tmp, able, full;

int n, bit, tp[155], cnt, hsh[P + 5], v, m, u, Q;
int l, r, L, R, tot[155][155];
ui lb;
LL ans[50005];

void dfs(int u) {
	able.e0(u);ui tm;
	For(i, 0, 4) {
		while(true) {
			tm = rev[u].b[i] & able.b[i];
			if(!(lb = lowbit(tm))) break;
			dfs((i << 5) | hsh[lb % P]);
		}
	}
	tp[cnt++] = u;
}

int Gsz(int u) {
	able.e0(u);
	int ret = 1;ui tm;
	For(i, 0, 4) {
		while(true) {
			tm = mp[u].b[i] & able.b[i];
			if(!(lb = lowbit(tm))) break;
			ret += Gsz((i << 5) | hsh[lb % P]);
		}
	}
	return ret;
}

LL Kosaraju(int n) {
	LL ans = 0, tmp;
	cnt = 0, able = full;
	For(i, 0, n - 1) 
		if(able[i]) dfs(i);
	able = full;
	Down(i, n - 1, 0) 
		if(able[tp[i]]) {
			tmp = Gsz(tp[i]);
			ans += tmp * (tmp - 1) / 2;
		}
	return ans;
}

void Go(int x, int y) {
	while(R < y) {
		u = e[++R].u, v = e[R].v;
		if(!tot[u][v]) mp[u].e1(v), rev[v].e1(u);
		++tot[u][v];
	} 
	while(L > x) {
		u = e[--L].u, v = e[L].v;
		if(!tot[u][v]) mp[u].e1(v), rev[v].e1(u);
		++tot[u][v];
	} 
	while(R > y) {
		u = e[R].u, v = e[R--].v, --tot[u][v];
		if(!tot[u][v]) mp[u].e0(v), rev[v].e0(u);
	} 
	while(L < x) {
		u = e[L].u, v = e[L++].v, --tot[u][v];
		if(!tot[u][v]) mp[u].e0(v), rev[v].e0(u);
	} 
}

int main() {
	//freopen("friend.in", "r", stdin);
	//freopen("friend.out", "w", stdout);
	For(i, 0, B - 1) hsh[(1u << i) % P] = i;
	scanf("%d%d%d", &n, &m, &Q);
	For(i, 0, n - 1) 
		rest[i] = i % B, dv[i] = i / B, full.e1(i);
	For(i, 1, m) {
		scanf("%d%d", &e[i].u, &e[i].v);
		--e[i].u, --e[i].v;
	}
	L = R = 0;
	For(i, 1, Q) {
		scanf("%d%d", &l, &r);
		qs[i].init(l, r, i);
	}
	sort(qs + 1, qs + 1 + Q);
	L = R = 0;
	for(int i = 1; i <= Q; ++i) {
		Go(qs[i].l, qs[i].r);
		ans[qs[i].id] = Kosaraju(n);
	}
	for(int i = 1; i <= Q; ++i)
		printf("%lld\n", ans[i]);
	return 0;
}

Rockdu's Blog