相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf
解题报告
这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法
有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$
然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了
Code
#include<bits/stdc++.h> #define LL long long #define UI unsigned int #define lowbit(x) ((x)&-(x)) using namespace std; const int N = 159; const int M = 300009; const int QQ = 50009; const int BlockSize = 1200; const UI ALL = (1ll << 32) - 1; int n, m, q, U[M], V[M], ans[QQ]; struct Query{ int l, r, blk, id; inline bool operator < (const Query &Q) const { return blk < Q.blk || (blk == Q.blk && r < Q.r); } }qy[QQ]; struct Bitset{ UI v[5]; inline void flip(int x) { v[x >> 5] ^= 1 << (x & 31); } inline void set(int x) { v[x >> 5] |= 1 << (x & 31); } inline void reset() { memset(v, 0, sizeof(v)); } inline bool operator [](int x) { return v[x >> 5] & (1 << (x & 31)); } }g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N]; inline int read() { char c = getchar(); int ret = 0, f = 1; while (c < '0' || c > '9') { f = c == '-'? -1: 1; c = getchar(); } while ('0' <= c && c <= '9') { ret = ret * 10 + c - '0'; c = getchar(); } return ret * f; } inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) { a1[u].set(v); a2[v].set(u); } class Kosaraju{ vector<int> que; Bitset vis; public: inline int solve() { vis.reset(); que.clear(); for (int i = 1; i <= n; ++i) { if (!vis[i]) { dfs0(i); } } vis.reset(); int ret = 0; for (int j = n - 1; ~j; j--) { int i = que[j]; if (!vis[i]) { int cnt = dfs1(i); ret += cnt * (cnt - 1) / 2; } } return ret; } private: inline void dfs0(int w) { vis.flip(w); for (int i = 0; i < 5; i++) { for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) { int t = (__builtin_ffs(j) - 1) | (i << 5); if (!vis[t]) { dfs0(t); } } } que.push_back(w); } inline int dfs1(int w) { vis.flip(w); int ret = 1; for (int i = 0; i < 5; i++) { for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) { int t = (__builtin_ffs(j) - 1) | (i << 5); if (!vis[t]) { ret += dfs1(t); } } } return ret; } }scc; int main() { freopen("friend.in", "r", stdin); freopen("friend.out", "w", stdout); n = read(); m = read(); q = read(); for (int i = 1; i <= m; i++) { U[i] = read(); V[i] = read(); AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]); } for (int i = 1; i <= q; i++) { qy[i].l = read(); qy[i].r = read(); qy[i].blk = qy[i].l / BlockSize; qy[i].id = i; } sort(qy + 1, qy + 1 + q); Bitset CurG[N], CurRG[N]; for (int i = 1, L = 1, R = 0; i <= q; i++) { if (qy[i].blk != qy[i - 1].blk || i == 1) { L = qy[i].blk + 1; R = L - 1; for (int j = 1; j <= n; j++) { CurG[j].reset(); CurRG[j].reset(); } } if (qy[i].r / BlockSize - 1 > R) { for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) { for (int k = 1; k <= n; k++) { for (int h = 0; h < 5; h++) { CurG[k].v[h] ^= PreG[j][k].v[h]; CurRG[k].v[h] ^= PreRG[j][k].v[h]; } } } R = qy[i].r / BlockSize - 1; } if (L <= R) { for (int i = 1; i <= n; i++) { g[i] = CurG[i]; rg[i] = CurRG[i]; } for (int l = qy[i].l; l < L * BlockSize; l++) { AddEdge(U[l], V[l], g, rg); } for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) { AddEdge(U[r], V[r], g, rg); } ans[qy[i].id] = scc.solve(); } else { for (int i = 1; i <= n; i++) { g[i].reset(); rg[i].reset(); } for (int j = qy[i].l; j <= qy[i].r; ++j) { AddEdge(U[j], V[j], g, rg); } ans[qy[i].id] = scc.solve(); } } for (int i = 1; i <= q; i++) { printf("%d\n", ans[i]); } return 0; }