P12029 题解

Central_GYM · 2026-10-25 15:46:30 · 题解

发现题解区全是 set，提供一种比较魔怔的不用 set 实现的做法。

思路

我们用 b_i 表示奶牛 i 收到的票数，下面是两个比较明显的结论：

如果让奶牛 x,y 成为两个首领是可行的，那么有 b_x+b_y\ge \max b_i。

对于一头牛 a 很明显可能会有很多牛可以同时做到和 a 匹配（即两个首领）有解，可以发现在这些牛中最优的情况只可能是最左侧和最右侧。如果两头牛 x,y 的票数是一样的，那么假如 z 能和 x 匹配，z 也一定能和 y 匹配，反之若 x 不行则 y 也一定不行。我们把这两个放一块想我们就很容易发现在票数一样的牛中，真正可能对答案有所贡献的只有可能是最左侧或者最右侧的牛，也就是下标最小/大的牛。

我们有一个大致的思路，就是用一个链表去维护我们当前有哪些票数，在求解的时候进行双指针，一侧从小到大，另一侧从大到小，每一次我们分别算一遍 max_l-min_r 和 max_r-min_l 的贡献即可，接下来的问题就在于怎么去维护这样一个票数的链表，以及对于每一个票数，怎么去维护其最大值和最小值以及怎么在 \sqrt n 时间内求出所有票数。

维护

我们使用位图来解决这道题，我们 64 位为一组，我们每一位的状态只分为 0/1（即出现或者没出现），对其压缩我们就可以将其变成一个使用 unsigned long long 可以存下来的整数，我们以这个为基础可以再进行嵌套。对于存在哪些票数，我们采用三层位图：

ull valbits[M],valtop[P],valtops;
//valbits 一个数表示 64 个值，也就是二进制下一位表示一种票数
//valtop 一个数表示 64*64，也就是二进制下一位表示一个 64 的小单元内有无出现的票数
//valtops 表示全部，也就是二进制下一位表示一个 64*64 的小单元内有无出现的票数

对于当前票数 i 下有哪些牛我们采用两层位图：

ull blocks[N][P],top[N];//第一维也就是 N 是指当前票数，每一个票数我们都有一个桶
//blocks 一个数表示 64*64 也就是二进制下一位表示一个 64 的小单元内有无满足的牛
//top 表示全部，也就是二进制下一位表示一个 64*64 的小单元内有无满足的牛

这里我们开不够三层位图，但是我们可以同时维护前面的计数 b_i，对于最后的 64 位我们直接枚举。

下面主要讲解几个主要的实现功能，可以对照最后的代码观看，

加点操作

我们现在有一个牛 p，我们需要把它挂到 b_p 也就是其对应票数的桶里，我们分为三步：

在位图上对应的进行标记，
把这个 p 给它挂到 b_p 底下的链表里，
更新 b_p 最大最小，注意如果一开始 b_p 这个桶底下压根就没挂东西，我们需要先把这个桶给打开，也就是上层位图上加上这个位置。

修改操作

我们可以大致将修改操作分成两个阶段，也就是将 x 从原本的 b_x 的桶里扔出去（这一步如果旧 b_x 是 0 的话不用执行），再给它放到新的 b_x 的桶里：

将 x 从原本的 b_x 下链表中扔出来，
我们对 x 原本所处的 64 位一组的小块暴力判断，观察是否变空了，如果是的话，再对其进行重构，
判断原本的桶是否直接没有牛了，如果是，将其在上层位图中删掉，重置最大最小；如果不是，我们需要考虑最大最小是否发生改变，如果变了，我们在 b_x 的位图里快速检索第一位/最后一位的 1，然后最后一小组暴力求解，找出新的最大最小。
第二阶段，修改 b_x ，将其加入新桶，也就是建新点，可以直接调用上面的建点操作实现。

实际统计答案

我们还是将其进行拆解：
在上层位图中升序找出所有存在的票值，倒着求一遍后缀最小/最大（后面的票值更大，也就是当前的可行后面的全可行，可以直接最大最小），并找出票值的最大也就是最后的数，

正着遍历，同时另一侧双指针倒着遍历，进行求解，最后输出答案。

去掉链表

注意到经过位图维护以后链表不再是必须的了，因为唯一可能用到链表的部分就是判断桶中是否存在元素，然而这一点我们只需要一个计数器，也就是说我们实际不需要再写链表了，直接写个 cnt_i 模拟链表中元素个数即可。

代码

复杂度 O(n+q\sqrt n)，存在常数，吸氧后有不错的表现。

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define ull unsigned long long
using namespace std;
const ull N=2e5+5;
const ull M=(N+63)>>6;
const ull P=(M+63)>>6;
ull n,T,a[N],b[N],cnt[N];
int ARIS[N],KEI[N];
ull blocks[N][P];
ull top[N];
ull valbits[M],valtop[P],valtops;
ull getmin(ull p){//最小 
 ull v=__builtin_ctzll(top[p]);
 ull c=blocks[p][v];
 ull q=(v<<6)+__builtin_ctzll(c);
 ull L=(q<<6)+1;
 ull R=min(n,(q+1)<<6);
 for(ull i=L;i<=R;i++){//最后 64 位暴力 
     if(b[i]==p){
         return i;
     }
 }
 return 0;
}
ull getmax(ull p){//最大 
 ull v=63-__builtin_clzll(top[p]);
 ull c=blocks[p][v];
 ull q=(v<<6)+63-__builtin_clzll(c);
 ull L=(q<<6)+1;
 ull R=min(n,(q+1)<<6);
 for(ull i=R;i>=L;i--){
     if(b[i]==p){
         return i;
     }
 }
 return 0;
}
void del(ull p){//删掉上层位图中这个桶的存在标记 
 ull v=p>>6;
 valbits[v]&=~(1ull<<(p&63));
 if(!valbits[v]){
     ull w=v>>6;
     valtop[w]&=~(1ull<<(v&63));
     if(!valtop[w]){
         valtops&=~(1ull<<w);
     }
 }
} 
void clear(ull v,ull p){//删标记 
 ull w=p>>6;
 blocks[v][w]&=~(1ull<<(p&63));
 if(!blocks[v][w]){
     top[v]&=~(1ull<<w);
 }
}
void rebuild(ull v,ull p){//暴力查值 
 ull L=(p<<6)+1;
 ull R=min(n,((p+1)<<6));
 for(ull i=L;i<=R;i++){
     if(b[i]==v){
         return ;
     }
 }
 clear(v,p);//删掉这个块的存在标记 
}
void acts(ull p){//上层位图标记 
 ull v=p>>6;
 if(!valbits[v]){
     ull w=v>>6;
     if(!valtop[w]){
         valtops|=1ull<<w;
     }
     valtop[w]|=1ull<<(v&63);
 }
 valbits[v]|=1ull<<(p&63);
}
void sets(ull p,ull v){//标记块非空 
 ull w=v>>6;
 ull op=1ull<<(v&63);
 if(!(blocks[p][w]&op)){
     blocks[p][w]|=op;
     top[p]|=1ull<<w;
 }
}
void build(int p){//建点 
 if(!b[p]){
     return ;
 }
 sets(b[p],(p-1)>>6);
 bool fl=!(cnt[b[p]]);
 cnt[b[p]]++;//挂到链表 
 if(fl){
     acts(b[p]);//在上层位图加点 
     KEI[b[p]]=ARIS[b[p]]=p;
 }
 else{//最大最小牛更新 
     KEI[b[p]]=min(KEI[b[p]],p);
     ARIS[b[p]]=max(ARIS[b[p]],p);
 }
}
void update(ull p,ull x){//更新 
 ull v=b[p];
 if(v>0){
     cnt[v]--;
     ull w=(p-1)>>6;
     b[p]+=x;
     rebuild(v,w);//检查是否重构 
     if(!cnt[v]){//删点 
         del(v);
         ARIS[v]=KEI[v]=0;
     }
     else{//更新 
         if(KEI[v]==p){
             KEI[v]=getmin(v);
         }
         if(ARIS[v]==p){
             ARIS[v]=getmax(v);
         }
     }
 }
 else{//之前压根不在桶里 
     b[p]+=x;
 }
 build(p);
}
vector<ull> gets(){
 vector<ull> ans;
 ull x=valtops;
 while(x){
     ull i=__builtin_ctzll(x);
     x&=(x-1);
     ull u=valtop[i];
     while(u){
         ull j=__builtin_ctzll(u);
         u&=(u-1);
         ull v=(i<<6)+j;
         ull w=valbits[v];
         while(w){
             ull k=__builtin_ctzll(w);
             w&=(w-1);//将这一位删掉以便找下一个 
             ull q=(v<<6)+k;
             if(q&&q<=n){
                 ans.pb(q);
             }
         }
     }
 } 
 return ans;
}
ull solve(){
 vector<ull> q=gets();//所有票值 
 ull m=q.size();
 if(!m){
     return 0;
 }
 ull maxx=q.back();//最大票值 
 int kei[m+5],aris[m+5];//后缀最大最小 
 for(int i=m-1;i>=0;i--){
     kei[i]=KEI[q[i]];
     aris[i]=ARIS[q[i]];
     if(i+1<m){
         kei[i]=min(kei[i],kei[i+1]);
         aris[i]=max(aris[i],aris[i+1]);
     }
 }
 int ans=0,j=m;//双指针 
 for(ull i=0;i<m;i++){
     while(j&&q[j-1]+q[i]>=maxx){
         j--;
     }
     if(j==m){
         continue;
     }
     ans=max(ans,aris[j]-KEI[q[i]]);
     ans=max(ans,ARIS[q[i]]-kei[j]);
 }
 return ans;
}
int main(){
 ios::sync_with_stdio(0);cin.tie(0);
 cin>>n>>T;
 for(ull i=1;i<=n;i++){
     cin>>a[i];
     b[a[i]]++;
 }
 for(ull i=1;i<=n;i++){
     build(i);
 }
 while(T--){
     ull op,x;
     cin>>op>>x;
     if(a[op]!=x){
         update(a[op],-1);
         update(x,1);
         a[op]=x;
     }
     cout<<solve()<<'\n';
 }
 return 0;
}/*
再见了，王女 
*/

:::info[人类成分说明] 思路和原始代码来自 ai，考虑到我赛时根本想不出来这种雷霆维护方式，题解里的代码是我又写出来优化了一点的一份，题解内容使用人脑生成，如果存在不通顺/错误指出会修改。

:::

P12029 题解

思路

维护

加点操作

修改操作

实际统计答案

去掉链表

代码