题解：P16120 [USTCPC 2026] Hamming Dominance

· · 题解

题意简述

长度为 n 的二进制串初始全为 0，依次翻转指定位置。每次翻转后，统计不同字符串构成的有序对 (A,B)：两者都是当前串的循环移位，且 A 的任意前缀中 1 的数量不小于 B 的等长前缀。

相同的循环移位结果仅算一个字符串，不能按移位次数重复计数。

解题思路

先允许重复，将每个循环起点都看成一个对象，最后再处理相同字符串的重复计数。

把当前串无限循环，记从位置 p 开始、长度为 d 的窗口中 1 的数量为 w_d(p)。所有位置都按模 n 解释，特别地，w_0(p)=0。

设 A 从位置 p 开始，B 从位置 p+d 开始。对于长度为 t 的前缀，两者的汉明权重之差可以通过消去公共部分改写为：

\sum_{j=0}^{t-1}s_{p+j}-\sum_{j=0}^{t-1}s_{p+d+j}=w_d(p)-w_d(p+t)

这个恒等式不要求 t\ge d：两边分别表示同一对起点间的区间差，展开四个前缀和后就会得到相同结果。因此有序对合法，当且仅当对全部 t=1\sim n，都有 w_d(p)\ge w_d(p+t)。

当 t 遍历 1\sim n，p+t 恰好遍历所有循环起点，所以条件等价于 w_d(p) 是所有长度为 d 的循环窗口和中的最大值。

于是，对于每个偏移 d=0\sim n-1，维护长度为 d 的窗口和的最大值及其出现次数。将这些次数相加，就得到按起点区分的合法有序对数量。d=0 时所有窗口和都为 0，固定贡献为 n，无需建立数据结构。

翻转位置 x 时，所有包含 x 的窗口和同时加上 v，其中从 0 变为 1 时 v=1，反之 v=-1。对于窗口长度 d，包含 x 的窗口起点恰好是循环区间 [x-d+1,x]。当左端点小于 1 时，将它拆成 [1,x] 和 [x-d+1+n,n] 两段即可。

因此，为每个 d=1\sim n-1 分别建立一棵支持区间加、查询全局最大值出现次数的线段树。每次翻转进行 n-1 次循环区间加，然后累加各棵树根节点的最大值出现次数。

本题的内存限制需要单独处理。常规线段树为每个节点保存最大值、次数和懒标记，并按 4n 分配空间，无法容纳全部线段树。这里同时压缩节点编号与懒标记。

对于区间 [l,r] 的内部节点，用分割点 \lfloor(l+r)/2\rfloor 作为编号。每个分割点对应相邻的两个位置，整棵树中恰好有一个节点首次将它们分开，因此内部节点的分割点两两不同，仅需要 n-1 个编号。叶子单独用其位置编号保存。

内部节点保存 val 和 cnt，分别表示最大值和出现次数；叶子仅保存数值 a，因为一个叶子的出现次数总为 1。三个数组都使用 short。出现次数至多为 n；整组数据仅有 n 次翻转，每次对一个窗口的改变量绝对值至多为 1，各节点保存的数值也处于 [-n,n]，所以 n\le 2000 时足够使用。

不再为内部节点显式保存懒标记，而是保留下面的关系。设节点最大值为 M，两个子节点保存的最大值为 L,R，这个节点尚未作用到子节点的统一加法为 z，则有：

M=\max(L,R)+z

若修改完整覆盖当前节点，仅改变它保存的最大值，不修改子节点，次数也不变。若需要递归修改子节点，先由旧数值计算 z=M-\max(L,R)，再递归修改，最后用新的子节点最大值恢复 M，并合并达到最大值的子节点次数。整个过程中不必下传 z：两个子节点都没有包含这一共同偏移，它不影响两者大小的比较。

这样，每棵树仅保存三个长度为 n 的短整型数组，主体内存约为 6n^2 字节，能够满足限制。代码中的 query 统一读取叶子和内部节点，update 在局部变量 tag 中暂存通过上式恢复的偏移。

最后消除循环移位产生的重复。设当前串的最小循环周期为 p，则共有 p 个不同的循环移位，每个不同字符串都被 n/p 个起点重复表示。一个字符串有序对会在起点有序对中出现 (n/p)^2 次，且这些表示是否满足前缀支配完全相同，因此将之前统计的结果除以 (n/p)^2 即可。

每次翻转后，用前缀函数重新求最小周期。设最长相等真前后缀长度为 b，对应代码中的 nxt[n]，令 p=n-b；若 p 不整除 n，当前串不能由这个长度的块完整重复，最小循环周期应取 n。全零、全一和其他有周期的字符串都由同一公式处理，n=1 时固定贡献也会得到答案 1。

每次翻转进行 O(n) 次区间修改和一次 O(n) 的前缀函数计算，总时间复杂度为 O(n^2\log n)，空间复杂度为 O(n^2)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=2005;
struct SEG
{
    short val[N],cnt[N],a[N];
    void build(int l,int r)
    {
        if(l==r){a[l]=0;return;}
        int mid=l+r>>1;
        val[mid]=0;
        cnt[mid]=r-l+1;
        build(l,mid);
        build(mid+1,r);
    }
    pii query(int l,int r)
    {
        return l==r?pii(a[l],1):pii(val[l+r>>1],cnt[l+r>>1]);
    }
    void update(int l,int r,int x,int y,int v)
    {
        if(l==r){a[l]+=v;return;}
        int mid=l+r>>1;
        if(x<=l&&r<=y){val[mid]+=v;return;}
        auto ls=query(l,mid),rs=query(mid+1,r);
        int tag=val[mid]-max(ls.first,rs.first);
        if(x<=mid)update(l,mid,x,y,v);
        if(y>mid)update(mid+1,r,x,y,v);
        ls=query(l,mid);
        rs=query(mid+1,r);
        val[mid]=max(ls.first,rs.first)+tag;
        cnt[mid]=(ls.first>=rs.first?ls.second:0)+(rs.first>=ls.first?rs.second:0);
    }
}tr[N];
int nxt[N];
bool s[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        fill(s,s+n+1,0);
        for(int i=1;i<n;i++)tr[i].build(1,n);
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            s[x]=!s[x];
            int v=s[x]?1:-1,ans=n;
            for(int j=1;j<n;j++)
            {
                int l=x-j+1;
                if(l>0)tr[j].update(1,n,l,x,v);
                else
                {
                    tr[j].update(1,n,1,x,v);
                    tr[j].update(1,n,l+n,n,v);
                }
                ans+=tr[j].cnt[n+1>>1];
            }
            for(int j=2;j<=n;j++)
            {
                int k=nxt[j-1];
                while(k&&s[j]!=s[k+1])k=nxt[k];
                if(s[j]==s[k+1])k++;
                nxt[j]=k;
            }
            int len=n-nxt[n];
            if(n%len)len=n;
            int cnt=n/len;
            if(i>1)cout<<' ';
            cout<<ans/(cnt*cnt);
        }
        cout<<'\n';
    }
    return 0;
}