P3590 [POI2015] TRZ 神秘做法

前言

神秘新颖好玩的题，有个不知道是啥的做法，感觉讲不太明白。。

思路

第一步转化应该比较简单，先前缀和，然后 $[l,r]$ 合法相当于 $\forall x,y\in \{B,C,S\},pre_{r,x}-pre_{l-1,x}≠pre_{r,y}-pre_{l-1,y}$，即 $pre_{r,x}-pre_{r,y}≠pre_{l-1,x}-pre_{l-1,y}$，相当于得到三个数组 $a_{i,0}=pre_{i,B}-pre_{i,C},a_{i,1}=pre_{i,B}-pre_{i,S},a_{i,2}=pre_{i,C}-pre_{i,S}$，要对每个 $r$ 检查三维都与自己不一样的最小的 $l$。

如果这个问题只有一维就很简单：维护前缀的最小值和颜色与最小值不同的次小值，这样颜色与最小值不同时直接匹配最小值，否则匹配次小值即可。但二维和三维的问题就无法简单维护了，看起来需要进行很多分讨。

这个时候尝试建出一个 DAG 状物，每次更新时动态在里面一边走一边尝试加点，假如当前所在的点为 $u$（初始为最小值 $0$），已经走过的边权集合为 $S$，要加的点是 $v$，枚举边权 $w\in \{0,1,2\}$，若 $a_{u,w}≠a_{v,w}$ 且 $w\notin S$，如果 $u$ 还没有边权为 $w$ 的出边就连接 $(u,v,w)$ 这条边，否则就沿这条出边走到下一个点并重复加边过程，直到某次成功加上边或者走过的边集已经是全集 $\{0,1,2\}$ 为止。

查询的时候就在这个图上从 $0$ 开始走，若当前点 $u$ 第 $i$ 维跟要查询的第 $i$ 维相等，就走到 $nxt_{u,i}$，如果三维都不相等就更新答案，最后把所有路径上的答案取 $\min$ 即可。

注意一个点可能会被连入多条边，例如 $(0,1,0)$ 和 $(0,1,1)$ 两条边，但两条入边的意义是不同的，所以需要用虚点来建图。即 $a_{0,0}≠a_{1,0}$ 且 $a_{0,1}≠a_{1,1}$ 时，可以建出两个虚点 $2$ 和 $3$，它们两个代表的实点都是 $1$，然后分别连 $(0,2,0)$ 和 $(0,3,1)$。

到这里可能会看得比较云里雾里，把这个建图和查询时在图上走的过程画图手玩一下可以帮助理解。

图上的点数是常数级的，所以总复杂度 $\mathcal{O}(n)$。注意特判整个区间都是一个字符的情况。

代码

constexpr int N = 1e6+5;

int n,a[N][3];
int nxt[N][3],id[N],cnt = 0;

void insert(int u,int s,int v){
    for(int i=0;i<3;i++){
        if(a[id[u]][i]==a[v][i] || (s>>i&1))    continue;
        if(nxt[u][i]==-1)  nxt[u][i] = ++cnt,id[cnt] = v;
        else    insert(nxt[u][i],s|(1<<i),v);
    }
}

int query(int u,int v){
    if(u==-1)   return inf;
    bool flg = 1;
    int res = inf;
    for(int i=0;i<3;i++){
        if(a[id[u]][i]==a[v][i]){
            flg = 0;
            int now = query(nxt[u][i],v);
            res = min(res,now);
        }
    }
    if(flg) res = min(res,id[u]);
    return res;
}

void solve(){
    cin>>n;
    int ans = 1,now = 0,lst = -1;
    int Cnt[3] = {};
    for(int i=1;i<=n;i++){
        char c;cin>>c;
        int t = (c=='B'?0:(c=='C'?1:2));
        Cnt[t]++;
        a[i][0] = Cnt[0]-Cnt[1],a[i][1] = Cnt[0]-Cnt[2],a[i][2] = Cnt[1]-Cnt[2];
        if(t==lst)  now++,ans = max(ans,now);
        else    now = 1;
        lst = t;
    }
    reset(nxt,-1);
    for(int i=1;i<=n;i++){
        int now = query(0,i);
        ans = max(ans,i-now);
        insert(0,0,i);
    }
    cout<<ans;
}