CF1795G

发表于 | 分类于 |

题目链接:https://codeforces.com/contest/1795/problem/G

首先,考虑什么是合法的序列.排列中的第1个数,必定初始度数等于其本身度数,我们可以找到所有符合该条件的数,则这几个数之间绝对不会连边(因为连边则不存在合法序列).所以这些数可以随意排列其位置,我们将这些数去掉之后,再根据上述步骤直至所有节点去掉.

可以发现,我们可以根据上述步骤将数分成若干组,每个组内数字的顺序可以随意互换,但要注意组之间也可以形成答案,比如样例3中,5与1连边,度数为1,目标度数为0,则5可以在3之前或者3之后.

显然,每个数字消去前,在其之前要消去的数字,是一个固定的集合A,在其之后要消去的数字,也是一个固定的集合B,显然,集合AB之间,A与该数字,B与该数字之间都无法对答案作贡献.

将无向图转换,我们将设集合A中的点为u,该数字为v,我们将(u,v)这条无向边变成从u到v的有向边,设集合B中的点为w,则将(v,w)这条无向边变成从v到w的有向边,则上述中的定序关系可以按照边的方向传递,一条从u到v的边,表示u必须在v之前出现.则我们的答案就是该有向图不能相互到达的点(若可以相互到达,则代表定序),而该有向图存在一个拓扑序(若存在环则不存在合法序列),拓扑序在求有向图的时候即可顺便求出.

故我们先求出该有向图的所有边(按照上述步骤进行一个类似拓扑排序即可),然后统计能互相到达的点对数,显然,有向无环图求互相到达点对数是比较典的按照拓扑序的逆序进行bitset并.

然而,如果直接使用bitset会导致O(N^2)的空间复杂度,O(N^2/64)的时间复杂度.其中时间复杂度勉强能过,空间复杂度无法忍受.

划重点:有一个类似分块的trick,因为bitset的时间复杂度和bitset的大小成线性,我们可以缩小bitset的大小而不影响时间复杂度.如开N个大小为64的bitset,我们每次以64为一组,遍历1~N,每次只统计能到达该组的点的节点个数,最外层循环时间复杂度为O(N/64),内层每轮重置bitset复杂度为O(N/64*N),bitset并的复杂度为O(N/64*M);其中M为边的总数,统计节点个数的复杂度为O(N/64*N),最终时间复杂度仍为O(N^2/64),但空间复杂度已为O(64*N)

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using i64 = int64_t;
/*head*/

#define fi first
#define se second
#define rep(i, a, b) for (i64 i = (a); i < (b); i++)
#define sz(x) ((i64)x.size())
// #define DE_BUG
/*define*/
const int P = 998244353;
const int maxn = 1e5 + 10;
// assume -P <= x < 2P

inline i64 read()
{
    i64 s = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s;
}

inline void write(i64 x)
{

    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
i64 n, k, m;
std::vector<i64> g[maxn];
i64 que[maxn];
bool vis[maxn];
void solve()
{
    std::cin >> n >> m;
    std::vector<i64> a(n), deg(n, 0);
    for (i64 i = 0; i < n; i++)
    {
        std::cin >> a[i];
        g[i].clear();
        vis[i] = 0;
    }
    for (i64 i = 0; i < m; i++)
    {
        i64 u, v;
        std::cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++, deg[v]++;
    }
    std::vector<std::pair<i64, i64>> edge;
    i64 tail = 0, head = 0;
    for (i64 i = 0; i < n; i++)
    {
        if (deg[i] == a[i])
        {
            que[tail++] = i;
            vis[i] = 1;
        }
    }
    while (head < tail)
    {
        for (auto &e : g[que[head]])
        {
            if (!vis[e])
            {
                edge.push_back({que[head], e});
                deg[e]--;
                if (deg[e] == a[e])
                {
                    que[tail++] = e;
                    vis[e] = 1;
                }
            }
        }
        head++;
    }
    std::reverse(edge.begin(), edge.end());
    assert(tail == head && tail == n);
    std::bitset<64> tmp[n];
    i64 res = 0;
    for (i64 i = 0; i < n; i += 64)
    {
        for (i64 j = i; j < std::min(n, i + 64); j++)
        {
            tmp[j][j - i] = 1;
        }
        for (auto &e : edge)
        {
            tmp[e.first] |= tmp[e.second];
        }
        for (i64 j = 0; j < n; j++)
        {
            i64 num = tmp[j].count();
            //std::cerr << num << "?\n";
            res += num;
            tmp[j] = 0;
        }
    }
    std::cout << (n * (n + 1)) / 2 - res << "\n";
}
int main()
{
    i64 T = 1;
    std::cin.tie(0)->sync_with_stdio(0);
    std::cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}