数据结构

从前缀和角度考虑，使用 $sum_{i,j}$ 表示前 $i$ 天第 $j$ 项能力的提升次数。假设一段均衡时期从第 $l$ 天开始，到第 $r$ 天结束，那么对于所有满足 $k \in [1,m]$ 的整数 $k$，$sum_{r,k} - sum_{l-1,k}$ 的值相等，问题在于 $sum_{r,k} - sum_{l-1,k}$ 的值不固定，无法快速查询。

现在强制所有满足条件的整数 $l,r,k$ 的 $sum_{r,k} - sum_{l-1,k}$ 值固定。具体地，每次更新能力值序列后将当前能力值序列 $a$ 的所有值减去 $\min\limits_{i=1}^{m} a_i$ 从而使得序列 $a$ 中总是存在等于 $0$ 的元素。

这样对于从 $l$ 开始，到 $r$ 结束的均衡时期而言，由于 $a$ 中的每个元素都增长了固定值 $x$，而 $x$ 会被减去 $\min\limits_{i=1}^{m} a_i$ 的操作减掉，第 $l-1$ 天和第 $r$ 天的序列 $a$ 是完全相同的。注意第 $l-1$ 天可以是第 $0$ 天。

使用 map<vector<int>,int> 维护，时间复杂度 $O(nm)$。

#include<bits/stdc++.h>
using namespace std;
map<vector<int>,int> w;
int n,m,ans;
int main(){
    scanf("%d%d",&n,&m);
    vector<int> v(m);
    w[v]=0;
    for(int i=1;i<=n;i++){
        static int x,uim;
        scanf("%d",&x);
        for(int &j:v) j+=x&1,x>>=1;
        uim=*min_element(v.begin(),v.end());
        for(int &j:v) j-=uim;
        if(!w.count(v)) w[v]=i;
        else ans=max(ans,i-w[v]);
    }
    printf("%d\n",ans);
    return 0;
}