CF1914G2 Light Bulbs (Hard Version) 题解

· · 题解

对样例进行分析，不难发现，可以将区间分成一块块，每一块由一些相交的相同数字对构成。

当两个数字对区间包含时，小的区间显然不必要点亮。

否则当它们相交时，点亮其中任何一个即可，相当于将整个块点亮。

即，最后块的数量即为第一个答案。

判断一个数是否出现偶数次，可以使用异或哈希。

考虑如何统计答案二。

不妨开一个 map，记录最后一个某哈希值 cur_{i} 出现的位置 lst_{cur_{i}}。

对每一个前缀异或哈希和为 0，即块的端点 i，我们从它的下一个点 i+1 即 j 开始跳，每次跳到 lst_{cur_{j}}+1，即下一个区间相交的位置，跳到 cur_{j} 为 0 即块的另一个端点停止。可以避免算到中间异或和为 0 的块，因为中间跳得到的 cur_{j} 都不等于 0。

这样，我们把每一个闭区间的贡献乘一起，就可以得到第二问的答案。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=4e5+5;
const int mod=998244353;
int T=1,n,ans1,ans2;
int w[maxn],cur[maxn];
map<int,int>lst;
mt19937_64 rnd(random_device{}());
int get()
{
    int x=0;
    while(!x){
        x=rnd();
    }
    return x;
}
int Add(int x,int y){return ((x+y)%mod+mod)%mod;}
int Mul(int x,int y){return x*y%mod;}
void solve()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        w[i]=get();
    }
    lst.clear();
    ans1=0;ans2=1;
    for(int i=1;i<=2*n;i++){
        int x;
        scanf("%lld",&x);
        cur[i]=cur[i-1]^w[x];
        lst[cur[i]]=i;
        if(!cur[i]){
            ans1++;
        }
    }
    for(int i=0;i<2*n;i++){
        if(cur[i]){
            continue;
        }
        int j=i+1,res=1;
        while(cur[j]){
            j=lst[cur[j]]+1;
            res++;
        }
        ans2=Mul(ans2,res);
    }
    printf("%lld %lld\n",ans1,ans2);
}
signed main()
{
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    scanf("%lld",&T);
    while(T--){
        solve();
    }
    return 0;
}
//dyyyyds