题解：CF1914G2 Light Bulbs (Hard Version)

· · 题解

这是一道图论+线段树题。

简化题面

有 2n 个灯泡，手动点亮一个灯泡后，与它同色的灯泡会自动点亮，同时它们之间的所有灯泡也会自动点亮。

求把灯泡全部点亮，所需的手动点亮灯泡的次数，以及方案数。

题解

考虑建图，如果一个灯泡 u 被点亮后灯泡 v 会同时点亮，那么就连一条从 u 到 v 的边。

如果若干个灯泡在同一强连通分量内，则只需要手动点亮强联通分量中的任意一个灯泡，整个连通块内的灯泡就会自动亮起。

如果不在同一强连通分量内呢？可以发现，只要一个强联通块有入边，其中的所有灯泡就一定会被自动点亮。

因此：先通过 Tarjan 算法对强连通分量缩点，之后统计所有入度为 0 的强联通分量的数量，就是第一问的答案。根据乘法原理，把入度为 0 的强联通分量的大小相乘来即可，就是第二问的答案。

那么这道题就做完了……吗？

注意到 1 \leq n \leq 2×10^5，而建图的时间复杂度是 O(n^2) 的。

因此我们需要线段树优化建图。

时间复杂度 O(n\log n)

\mathfrak{Code}

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353, M = 2e6 + 10;
int Ts;

namespace Carey
{
    vector<pair<int, int>> E;
    vector<int> G[M], newG[M];

    struct Tree //线段树优化建图的板子
    {
        struct Node
        {
            int l, r; 
        };

        Node T[M];

        void build(int l, int r, int u = 1)
        {
//          printf("%d %d %d\n", l, r, u);
            T[u] = {l, r};

            if(l == r)
            {
                G[Ts + u].push_back(r);
                E.push_back({Ts + u, r});
                return;
            }

            int mid = (l + r) / 2;
            build(l, mid, 2 * u);
            build(mid + 1, r, 2 * u + 1);

            G[Ts + u].push_back(Ts + 2 * u);
            E.push_back({Ts + u, Ts + 2 * u});
            G[Ts + u].push_back(Ts + 2 * u + 1);
            E.push_back({Ts + u, Ts + 2 * u + 1});
        }

        void motify(int l, int r, int p, int u = 1)
        {
            if(l <= T[u].l && T[u].r <= r)
            {
                G[p].push_back(Ts + u);
                E.push_back({p, Ts + u});
                return;
            }

            int mid = (T[u].l + T[u].r) / 2;

            if(l <= mid)
            {
                motify(l, r, p, 2 * u);
            }
            if(r > mid)
            {
                motify(l, r, p, 2 * u + 1);
            }
        }
    };

    int n, m;
    int l[400010], r[400010], a[400010];
    int scc[M], dfn[M], low[M], siz[M], in[M];
    bitset<M> OK, vis;
    map<int, map<int, bool>> M;

    int cnt, val;
    vector<int> K;
    void Tarjan(int u){...} // Tarjan 算法，把每个点所处的强联通分量编号存在 scc[] 数组里。

    int Max = 0;
    Tree T;

    void solve()
    {
        scanf("%d", &n);
        n *= 2;

        Ts = n;
        ... //清空所有数组（多测不清空，爆零两行泪）。

        T.build(1, n);

        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);

            if(l[a[i]] == 0)
            {
                l[a[i]] = i;
            }
            else
            {
                r[a[i]] = i;
            }
        }

        for(int i = 1; i <= n; i++)
        {
            T.motify(l[a[i]], r[a[i]], i);
        }

        cnt = 0;
        val = 0;
        Tarjan(Ts + 1);

        long long ans1 = 0, ans2 = 1;
        for(auto [i, j] : E)
        {
            if(scc[i] != scc[j] && M[i][j] == 0)
            {
                newG[scc[i]].push_back(scc[j]);
                in[scc[j]]++;
                M[i][j] = 1;
            }
        }

        queue<int> Q;
        for(int i = 1; i <= val; i++)
        {
            if(in[i] == 0)
            {
                Q.push(i);
                if(siz[i] != 0)
                {
                    ans1++;
                    ans2 = (ans2 * siz[i]) % mod;
                    OK[i] = true;
                }
            }
        }

        while(!Q.empty())
        {
            int u = Q.front();
            Q.pop();

            for(auto v : newG[u])
            {
                OK[v] = OK[v] | OK[u];
                in[v]--;

                if(in[v] == 0)
                {
                    Q.push(v);
                    if(OK[v] == false && siz[v] != 0)
                    {
                        ans1++;
                        ans2 = (ans2 * siz[v]) % mod;
                        OK[v] = true;
                    }
                }
            }
        }

        printf("%lld %lld\n", ans1, ans2);
        Max = max(Max, val);
    }
};

int main() {...} // 主函数