JZOJ 5064 友好城市

发表于 | 分类于 |

众所周知 Kosaraju 算法是 \(O(n + m)\) 的，改成邻接矩阵就是 \(O(n^2)\) 的，用 bitset 优化就可以变成 \(O\left(\frac{n^2}w\right)\) 的。

那么我们需要得到编号在一个区间内的边组成的邻接矩阵。
考虑分块，整块利用 ST 表优化。

代码： 

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
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 150;
const int M = 3e5;
const int BLK = 550;
const int CNT = M / BLK + 5;
const int LG = 10;
int n,m,q,block,lg2[CNT + 5];
struct edge
{
    int u,v;
} e[M + 5];
int pos[M + 5];
int id[N + 5],rk[N + 5],dfn_tot,ans;
bitset<N + 5> g[LG + 5][CNT + 5][N + 5],gr[LG + 5][CNT + 5][N + 5],G[N + 5],Gr[N + 5],S,E;
void dfs1(int p)
{
    int &tot = dfn_tot;
    S[p] = 0;
    for(register int i;;)
    {
        i = (G[p] & S)._Find_first();
        if(i > n)
            break ;
        dfs1(i);
    }
    rk[id[p] = ++tot] = p;
}
int dfs2(int p)
{
    int ret = 1;
    S[p] = 0,E = Gr[p] & S;
    for(register int i;;)
    {
        i = (Gr[p] & S)._Find_first();
        if(i > n)
            break;
        ret += dfs2(i);
    }
    return ret;
}
int main()
{
    freopen("friend.in","r",stdin),freopen("friend.out","w",stdout);
    read(n),read(m),read(q),block = BLK;
    for(register int i = 1;i <= m;++i)
        read(e[i].u),read(e[i].v),pos[i] = (i - 1) / block + 1,
        g[0][pos[i]][e[i].u][e[i].v] = gr[0][pos[i]][e[i].v][e[i].u] = 1;
    for(register int i = 2;i <= pos[m];++i)
        lg2[i] = lg2[i >> 1] + 1;
    for(register int i = 1;i <= LG;++i)
        for(register int j = 1;j + (1 << i) - 1 <= pos[m];++j)
            for(register int k = 1;k <= n;++k)
                g[i][j][k] = g[i - 1][j][k] | g[i - 1][j + (1 << i - 1)][k],
                gr[i][j][k] = gr[i - 1][j][k] | gr[i - 1][j + (1 << i - 1)][k];
    int c = 0;
    for(int l,r,L,R,lg;q;--q)
    {
        ++c;
        read(l),read(r),L = pos[l] + 1,R = pos[r] - 1,S.reset(),dfn_tot = ans = 0;
        for(register int i = 1;i <= n;++i)
            G[i].reset(),Gr[i].reset(),S[i] = 1,id[i] = 0;
        if(L <= R)
        {
            lg = lg2[R - L + 1];
            for(register int i = 1;i <= n;++i)
                G[i] |= g[lg][L][i] | g[lg][R - (1 << lg) + 1][i],
                Gr[i] |= gr[lg][L][i] | gr[lg][R - (1 << lg) + 1][i];
            for(register int i = R * block + 1;i <= r;++i)
                G[e[i].u][e[i].v] = Gr[e[i].v][e[i].u] = 1;
        }
        for(register int i = l;i <= min(L * block,r);++i)
            G[e[i].u][e[i].v] = Gr[e[i].v][e[i].u] = 1;
        for(register int i = 1;i <= n;++i)
            if(S[i])
                dfs1(i);
        S.reset();
        for(register int i = 1;i <= n;++i)
            S[i] = 1;
        for(register int i = n,sz;i;--i)
            if(S[rk[i]])
                sz = dfs2(rk[i]),ans += sz * (sz - 1) >> 1;
        printf("%d\n",ans);
    }
}