随机构造特殊运算的应用

异或

由于异或有 \(a\oplus b \oplus b=a\) 且满足交换律的性质，因此可以通过异或前缀和来做询问区间内某个数是否出现了偶数次。

例题

她看到宫河日向在货架上放了 \(n\leq 10^5\) 种漫画，货架总共有 \(m\leq 10^5\) 列，其中第 \(i\) 种漫画在第 \(l_i\) 列到第 \(r_i\) 列中的每一列上都各有一本。
泉此方决定选择一个区间，并买下这个区间中每一列上摆放的所有漫画。
对于买下的每一种漫画，泉此方会分别留下若干本（可能为零）保存用和鉴赏用，再剩下一本传教用，所以她希望至少买下一种漫画，且买下的每一种漫画都有奇数本。
但这时柊镜到了，于是泉此方并没有买下任何漫画，不过她想知道，所有可以满足她心意的区间包含的列数之和为多少。

根据前面的结论，出现偶数次是好做的，我们只需要给每种漫画随机赋一个权值，统计区间异或和为零的情况。
那要求奇数次呢？设 \(sxor_i\) 可以注意到为前缀和，对于第 i 种漫画，\(\forall [l,r]\)，要求漫画 i 出现了奇数次，如果 \(l_i\leq l\leq r_i\) 那么 \(sxor_r \oplus sxor_l=0\)，如果 \(l<l_i\) 那么 \(sxor_r \oplus sxor_l=1\)。问题的核心在于 l 这个位置有没有第 i 种漫画，那么只需要在 \(l_i\) 处再加一本漫画书，令 \(l<l_i\) 的情况结果取反，就是好统计的。
记得去掉空区间的贡献。

    cin >> n >> m;
    for (int i=1,l,r;i<=n;i++)
    {
        cin >> l >> r;
        ull w=rnd();
        b[l]^=w;
        c[l]^=w;c[r+1]^=w;
        cnt[l]++;cnt[r+1]--;
    }
    for (int i=1;i<=m+1;i++) b[i]^=b[i-1],c[i]^=c[i-1],cnt[i]+=cnt[i-1];
    for (int i=1;i<=m+1;i++) c[i]^=c[i-1];
    for (int i=1;i<=m;i++)
    {
        ull val=(c[i]^b[i]);
        mp[val]++;ml[val]+=i;
        ans+=1ll*mp[val]*(i+1)-ml[val];
    }
    cnt[m+1]=0x3f3f3f3f;
    for (int i=1,ccnt=0;i<=m+1;i++)
    {
        if (cnt[i]==0) ccnt++;
        else
        {
            if (ccnt) ans-=1ll*(ccnt+2)*(ccnt+1)*ccnt/6;
            ccnt=0;
        }
    }
    cout << ans;

矩阵乘法

矩阵乘法满足结合律，不满足交换律，这与一个合法的括号序列的要求相似，因此可以在括号序列的的统计中发挥作用。具体来说，对于每一种括号，左括号随机构造一个二阶矩阵 \(A\)，右括号为 \(A^{-1}\)，一个括号序列合法当且仅当其所有括号对应矩阵的乘积为 \(I\)，这用线段树是可以快速维护的。