526互联

G2. Light Bulbs (Hard Version)

发布时间 2023-12-24 21:33:26作者: onlyblues

G2. Light Bulbs (Hard Version)

The easy and hard versions of this problem differ only in the constraints on $n$. In the hard version, the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$. Furthermore, there are no additional constraints on the value of $n$ in a single test case.

There are $2n$ light bulbs arranged in a row. Each light bulb has a color from $1$ to $n$ (exactly two light bulbs for each color).

Initially, all light bulbs are turned off. You choose a set of light bulbs $S$ that you initially turn on. After that, you can perform the following operations in any order any number of times:

  • choose two light bulbs $i$ and $j$ of the same color, exactly one of which is on, and turn on the second one;
  • choose three light bulbs $i, j, k$, such that both light bulbs $i$ and $k$ are on and have the same color, and the light bulb $j$ is between them ($i < j < k$), and turn on the light bulb $j$.

You want to choose a set of light bulbs $S$ that you initially turn on in such a way that by performing the described operations, you can ensure that all light bulbs are turned on.

Calculate two numbers:

  • the minimum size of the set $S$ that you initially turn on;
  • the number of sets $S$ of minimum size (taken modulo $998244353$).

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of pairs of light bulbs.

The second line of each test case contains $2n$ integers $c_1, c_2, \dots, c_{2n}$ ($1 \le c_i \le n$), where $c_i$ is the color of the $i$-th light bulb. For each color from $1$ to $n$, exactly two light bulbs have this color.

Additional constraint on the input: the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output two integers:

the minimum size of the set $S$ that you initially turn on;

the number of sets $S$ of minimum size (taken modulo $998244353$).

Example

input

4
2
2 2 1 1
2
1 2 2 1
2
1 2 1 2
5
3 4 4 5 3 1 1 5 2 2

output

2 4
1 2
1 4
2 8

 

解题思路

  前置知识：向图的强连通分量，线段树优化建图。

  官方的题解看了几遍都看不懂，索性用思路相对简单但实现很复杂的做法。

  假设第 $i$ 种颜色的灯在序列中出现的两个位置分别是 $l_i$ 和 $r_i$，当选择先打开 $l_i$ 位置的灯时，根据第 $1$ 个操作 $r_i$ 位置上的灯也会被打开。同理先打开 $r_i$ 位置的灯。因此对于同一种颜色的灯我们只选择其中一个位置的打开。另外根据第 $2$ 个操作，当打开第 $i$ 种颜色的灯后，区间 $[l_i, r_i]$ 中的灯都会被打开。

  容易发现这个过程具有传递性，因此考虑建图。把 $2n$ 个位置看作是点，对于每种颜色 $i$，分别从 $l_i$ 和 $r_i$ 向区间 $[l_i, r_i]$ 中的每个点都连一条有向边，表示打开 $l_i$ 或 $r_i$ 位置上的灯后，边所指向的这些位置的灯也会被打开。

  最后因为要考虑选哪些点作为起始点，使得图中所有节点都可以被遍历到，因此考虑对这个图求强连通分量，把那些可以相互到达的点进行缩点，缩点后的图就会变成拓扑图（不一定连通）。此时所有入度为 $0$ 的点（缩点后）必然是要选择的点，因为其入度为 $0$，即没有节点能访问到该节点，因此必须要选入度为 $0$ 的节点。当把所有入度为 $0$ 的点选择后，根据拓扑排序知道一定能遍历图中的所有点。

  因此要选择的点的最小值就是缩点后入度为 $0$ 的点的数量，只需在所有该节点所表示的强连通分量中任意选择一个节点即可（因为强连通分量内的点可以互相到达）。因此选择的方案数也知道了，就是每个入度为 $0$ 的点所表示的强连通分量的大小的乘积。

  现在最大的问题就是如何建图，先考虑 G1. Light Bulbs (Easy Version)，由于 $n$ 最大只有 $1000$，因此可以考虑暴力连边建图，即枚举每种颜色 $i$，然后遍历区间 $[l_i, r_i]$ 进行连边。这样整个图边的数量是 $O(n^2)$ 级别的。

  Easy Version 的 AC 代码如下，时间复杂度为 $O(n^2)$：

Code 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2010, M = N * N, mod = 998244353;

int l[N], r[N];
int head[N], e[M], ne[M], idx;
int dfn[N], low[N], sz;
int stk[N], tp, vis[N];
int id[N], sum[N], cnt;
int deg[N];

void add(int u, int v) {
    e[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++sz;
    stk[++tp] = u, vis[u] = 1;
    for (int i = head[u]; i != -1; i = ne[i]) {
        if (!dfn[e[i]]) {
            tarjan(e[i]);
            low[u] = min(low[u], low[e[i]]);
        }
        else if (vis[e[i]]) {
            low[u] = min(low[u], dfn[e[i]]);
        }
    }
    if (dfn[u] == low[u]) {
        cnt++;
        sum[cnt] = 0;
        int t;
        do {
            t = stk[tp--];
            vis[t] = 0;
            id[t] = cnt;
            sum[cnt]++;
        } while (t != u);
    }
}

void solve() {
    int n;
    scanf("%d", &n);
    memset(l, 0, n + 10 << 2);
    for (int i = 1; i <= n << 1; i++) {
        int x;
        scanf("%d", &x);
        if (!l[x]) l[x] = i;
        else r[x] = i;
    }
    idx = 0;
    memset(head, -1, 2 * n + 10 << 2);
    for (int i = 1; i <= n; i++) {
        for (int j = l[i]; j <= r[i]; j++) {
            add(l[i], j);
            add(r[i], j);
        }
    }
    sz = cnt = 0;
    memset(dfn, 0, 2 * n + 10 << 2);
    for (int i = 1; i <= n << 1; i++) {
        if (!dfn[i]) tarjan(i);
    }
    memset(deg, 0, cnt + 10 << 2);
    for (int i = 1; i <= n << 1; i++) {
        for (int j = head[i]; j != -1; j = ne[j]) {
            int x = id[i], y = id[e[j]];
            if (x != y) deg[y]++;
        }
    }
    int ret = 0, s = 1;
    for (int i = 1; i <= cnt; i++) {
        if (!deg[i]) ret++, s = (LL)s * sum[i] % mod;
    }
    printf("%d %d\n", ret, s);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    
    return 0;
}

  现在的 $n$ 变成了 $2 \cdot 10^5$，显然不可以像上面那样暴力建图。由于每次都是将单个点连向某个区间，因此可以考虑用线段树来优化建图。这是因为线段树可以用节点来表示一个区间，因此我们只需把边连向这些节点，这样就可以大大减少边的数量了。

  其中对于线段树中的节点，大区间所表示的节点向小区间所表示的节点连边，即每个父节点都会向其两个儿子连一条边，这是因为必然可以从大区间走到小区间。当然每个儿子也可以向其父节点连一条边，不过由于本题中只需考虑从单点向区间连边，因此为了方便这里仅从父节点向儿子连边。如下图维护区间 $[1,4]$ 的线段树：

  考虑节点 $4$ 向区间 $[1,3]$ 中的点连边：

  另外我们把序列的每个位置单独成一个点来考虑（如上图中的 $4$ 号节点），并让线段树中的叶子节点指向与其相应的点，如图：

  规定线段树用到的节点编号为 $1 \sim 4n$，序列节点用到的编号为 $4n \mathrm{+} 1 \sim 5n$。建树的代码如下：

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        add(u, l + 4 * n);
    }
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        add(u, u << 1);
        add(u, u << 1 | 1);
    }
}

  单点连向区间的代码如下（$x$ 表示映射后的序列节点编号）：

void modify(int u, int l, int r, int x) {
    if (tr[u].l >= l && tr[u].r <= r) {
        add(x, u);
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, x);
        if (r >= mid + 1) modify(u << 1 | 1, l, r, x);
    }
}

  最后对这个图求强连通分量进行缩点。不过与上面说过的“选择的点的最小值是缩点后入度为 $0$ 的点的数量”不同，此时强连通分量内只有序列节点（即编号为 $4n \mathrm{+} 1 \sim 5n$ 的节点）才有贡献，线段树的节点没有贡献，意味着入度为 $0$ 的点所表示的强连通分量可能都是由线段树的节点构成的。因此我们应该把这些点从拓扑图中删去。

  由于在求完强连通分量后，所得到的强连通分量的倒序就是缩点后的图的拓扑序，假设一共有 $\text{cnt}$ 个强连通分量，只需要从第 $\text{cnt}$ 个强连通分量倒序遍历，把入度为 $0$ 且 $\text{sum}_i$ 为 $0$ 的点（表示第 $i$ 个强连通分量中序列节点的个数）删去，即枚举第 $i$ 个强连通分量中的所有点，并把与这些点相邻的（不在同一个强连通分量内的）点的度数减 $1$。

  最后再统计所有入度为 $0$，且 $\text{sum}_i$ 不为 $0$ 的点即可。

  AC 代码如下，时间复杂度为 $O(n \log{n})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e6 + 10, M = 1.8e7 + 10, mod = 998244353;

int n;
int l[N], r[N];
int head[N], e[M], ne[M], idx;
int dfn[N], low[N], sz;
int stk[N], tp, vis[N];
int id[N], sum[N], cnt;
vector<int> scc[N];
int deg[N];
struct Node {
    int l, r;
}tr[N];

void add(int u, int v) {
    e[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        add(u, l + 4 * n);
    }
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        add(u, u << 1);
        add(u, u << 1 | 1);
    }
}

void modify(int u, int l, int r, int x) {
    if (tr[u].l >= l && tr[u].r <= r) {
        add(x, u);
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, x);
        if (r >= mid + 1) modify(u << 1 | 1, l, r, x);
    }
}

void tarjan(int u) {
    dfn[u] = low[u] = ++sz;
    stk[++tp] = u, vis[u] = 1;
    for (int i = head[u]; i != -1; i = ne[i]) {
        if (!dfn[e[i]]) {
            tarjan(e[i]);
            low[u] = min(low[u], low[e[i]]);
        }
        else if (vis[e[i]]) {
            low[u] = min(low[u], dfn[e[i]]);
        }
    }
    if (dfn[u] == low[u]) {
        cnt++;
        scc[cnt].clear();
        sum[cnt] = 0;
        int t;
        do {
            t = stk[tp--];
            vis[t] = 0;
            id[t] = cnt;
            scc[cnt].push_back(t);
            if (t > n << 2) sum[cnt]++;
        } while (t != u);
    }
}

void solve() {
    scanf("%d", &n);
    n <<= 1;
    memset(l, 0, n + 10 << 2);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (!l[x]) l[x] = i;
        else r[x] = i;
    }
    idx = 0;
    memset(head, -1, 5 * n + 10 << 2);
    build(1, 1, n);
    for (int i = 1; i <= n >> 1; i++) {
        modify(1, l[i], r[i], l[i] + 4 * n);
        modify(1, l[i], r[i], r[i] + 4 * n);
    }
    sz = cnt = 0;
    memset(dfn, 0, 5 * n + 10 << 2);
    for (int i = 1; i <= 5 * n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    memset(deg, 0, cnt + 10 << 2);
    for (int i = 1; i <= 5 * n; i++) {
        for (int j = head[i]; j != -1; j = ne[j]) {
            int x = id[i], y = id[e[j]];
            if (x != y) deg[y]++;
        }
    }
    for (int i = cnt; i; i--) {
        if (!deg[i] && !sum[i]) {
            for (auto &x : scc[i]) {
                for (int j = head[x]; j != -1; j = ne[j]) {
                    if (i != id[e[j]]) deg[id[e[j]]]--;
                }
            }
        }
    }
    int ret = 0, s = 1;
    for (int i = 1; i <= cnt; i++) {
        if (!deg[i] && sum[i]) {
            ret++;
            s = (LL)s * sum[i] % mod;
        }
    }
    printf("%d %d\n", ret, s);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    
    return 0;
}

 

参考资料

  Codeforces Round 916 (Div. 3) A - G：https://zhuanlan.zhihu.com/p/673159169

  DS 优化建图：https://www.luogu.com.cn/blog/forever-captain/DS-optimize-graph

  「算法笔记」线段树优化建图 - maoyiting - 博客园：https://www.cnblogs.com/maoyiting/p/13764109.html