A. Mind Control

签到题，求指定长度区间内相距 n-m 的两个元素之中的最大值的最小值的最大值（）

容易得到 O(n^2) 的做法，使用单调队列可以优化到 O(n) 。

B. Irreducible Anagrams

算是个结论题吧。。感觉还是需要一些思维的。

结论：一个子串有至少一个“irreducible anagram”，那么它必须满足以下三个条件之一：

• 长度为 1。 这种情况是显然成立的。

• 包含三种或以上不同字符。 设最后一次出现的位置最靠前的一种字符为 a ，第一次出现的位置最靠后的一种字符最后一次出现的位置最靠前的一种字符为 b ，那么考虑这样构造：将所有字符 b 放在串首，将所有字符 a 放在串末，中间放其他的字符（bbb...bb???...??aaa...aa）。那么我们构造的这个串一定是原串的一个 irreducible anagram。

• 第一个字符和最后一个字符不同。 不妨只考虑该串恰好由两种字符组成的情况。设第一个字符为 a ，最后一个字符为 b ，那么构造（bbb...bbaaa...aa）即可，否则一定不行。

考场上可能不是很容易以证明这些结论，但摸索一下并不难发现它们。

C. Prefix Enlightenment

刚看这题的时候，我是严重怀疑它的可做性的（

条件中任意三个集合的交集为空，这等价于一个更有用的结论：每个元素会在不超过两个集合中出现。然后还保证有解，这题就变得可做多了。

考虑类似 2-sat 的建图方式，将每个集合拆成两个点，分别表示选和不选。在两个点间连一条无向边表示这两个点对应的状态相同。那么对于每个元素要讨论两种情况：

• 有两个集合包含了这种元素 这种情况下，若这个元素初始时为 0 ，则这两个集合必然是一个选一个不选，此时交叉连边；若这个元素初始时为 1 ，则这两个集合必然是同时选或不选，此时两边分别连边。

• 有不到两个集合包含了这种元素 这种情况下，若这个元素初始时为 0 ，这个集合必须选；若这个元素初始时为 1 ，则这个集合必须不选。

用并查集维护图的连通性，每个连通块中表示选的点的个数（sz1）和表示不选的点的个数（sz2）。那么一个连通块中所有点的状态都是相同的。再维护一个标记表示这个连通块里有没有必须为 0 或必须为 1 的状态。如果没有这种标记，那么状态可以任意取 0/1，对答案的贡献为 \min(sz1, sz2)；否则整个连通块的状态就是确定的，分情况对答案的贡献只能是 sz1 或 sz2。由于题目保证，标记一定不会冲突。

这种做法每个点的两种状态会对答案各贡献一次，所以最终的答案要除以 2。代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=330000;
char s[MAXN];
int p1[MAXN], p2[MAXN];
int ans;
struct DSU
{
    int fa[2*MAXN], sz1[2*MAXN], sz2[2*MAXN];
    int tag[2*MAXN];
    void init(int n)
    {
        for (int i=1; i<=2*n; i++) fa[i]=i, tag[i]=-1;
        for (int i=1; i<=n; i++)
        {
            sz1[i]=1, sz2[i]=0;
            sz1[i+n]=0, sz2[i+n]=1;
        }
    }
    int getf(int x)
    {
        if (x==fa[x]) return x;
        return fa[x]=getf(fa[x]);
    }
    void assign(int u, int k)
    {
        int x=getf(u);
        if (tag[x]==-1)
        {
            ans-=min(sz1[x], sz2[x]);
            if (k==1) ans+=sz1[x];
            else ans+=sz2[x];
            tag[x]=k;
        }
    }
    void merge(int u, int v)
    {
        int x=getf(u), y=getf(v);
        if (x!=y)
        {
            if (tag[x]==-1&&tag[y]==-1)
            {
                ans-=min(sz1[x], sz2[x]);
                ans-=min(sz1[y], sz2[y]);
                ans+=min(sz1[x]+sz1[y], sz2[x]+sz2[y]);
            }
            else if (~tag[x]&&tag[y]==-1)
            {
                tag[y]=tag[x];
                ans-=min(sz1[y], sz2[y]);
                if (tag[x]==1) ans+=sz1[y];
                else ans+=sz2[y];
            }
            else if (~tag[y]&&tag[x]==-1)
            {
                ans-=min(sz1[x], sz2[x]);
                if (tag[y]==1) ans+=sz1[x];
                else ans+=sz2[x];
            }
            fa[x]=y, sz1[y]+=sz1[x], sz2[y]+=sz2[x];
        }
    }
} dsu;
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    int n, m;
    scanf("%d%d%s", &n, &m, s+1);
    for (int i=1; i<=m; i++)
    {
        int k; scanf("%d", &k);
        for (int j=1; j<=k; j++)
        {
            int x; scanf("%d", &x);
            if (!p1[x]) p1[x]=i;
            else p2[x]=i;
        }
    }
    dsu.init(m);
    for (int i=1; i<=n; i++)
    {
        if (!p2[i])
            if (s[i]=='0')
            {
                dsu.assign(p1[i], 1);
                dsu.assign(p1[i]+m, 0);
            }
            else
            {
                dsu.assign(p1[i], 0);
                dsu.assign(p1[i]+m, 1);
            }
        if (p2[i])
            if (s[i]=='0')
            {
                dsu.merge(p1[i], p2[i]+m);
                dsu.merge(p1[i]+m, p2[i]);
            }
            else
            {
                dsu.merge(p1[i], p2[i]);
                dsu.merge(p1[i]+m, p2[i]+m);
            }
        printf("%d\n", ans/2);
    }
    return 0;
}