CF1705E

DDF_ · 2025-09-06 16:53:12 · 题解

题面

给定一个序列，可抽取其中两个相同的数 x 并将其合并为 x+1，问若干次操作后能得到的序列最大值。

题解

你好。

我打这题真是糖丸了。

首先可以发现操作与序列顺序无关，只与各个元素的个数有关，于是可以用桶存每个元素的个数。

然后发现这个合并可以视作一棵二叉树（森林也可以）。

由数值最低的节点一层一层往上合并，下一层每两个子节点合并在这一层创造一个父节点并向这个父节点连边。所以可以把它看作一个高精度二进制数（因为二进制数是逢二进一），然后我们要求的就是这个二进制数的位数。

如果上面这一段看不懂可以感性理解一下（联系那个很火的合成大西瓜）。

可以在数据读入完之后把这个二进制数预处理出来。

发现每次操作会使得一个元素个数减少，一个元素个数增加，这就是这个二进制数的加减操作。

具体地，S = S - 2^{a_{k}-1} + 2^{l-1}。

直接高精度模拟二进制加减法，你会获得 Time limit exceeded on test 7。

于是要用数据结构维护这个高精度二进制数。发现如果整个序列都是 2 \times 10^{5}，它最大值也是 2 \times 10^{5} + \log(n)，所以能达到的最大值为 2 \times 10^{5}+17。

所以就可以用线段树维护，用前面的下标存低位。由于每次都是特定位 +1 和 -1，手模高精度可以发现 +1 操作就是找到找到位于这一位之后第一个 0 的位置 r，将 [l,r] 全部取反；-1 就是找第一个 1 的位置后取反。

然后我们要求的答案是最后一个 1 的位置。

我线段树存的是第一个 0 和 1 的位置以及最后一个 0 和 1 的位置。取反操作就将线段树上 0 和 1 存的位置都互换即可。

时间复杂度 O(n \log(n))。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+55;
int n,q,a[N],cnt[N];
int ans[N],w;
struct segment {
    int l,r;
    int f[2],e[2],tag;
} s[N*4];
inline void init() {
    int jw=0;
    for(int i=1,res;i<=w;i++) {
        res=ans[i]+jw;
        ans[i]=res%2,jw=res/2;
    }
    while(jw) ans[++w]=jw%2,jw/=2;
    return;
}
inline void pushup(int k) {
    s[k].f[0]=min(s[k*2].f[0],s[k*2+1].f[0]),s[k].f[1]=min(s[k*2].f[1],s[k*2+1].f[1]);
    s[k].e[0]=max(s[k*2].e[0],s[k*2+1].e[0]),s[k].e[1]=max(s[k*2].e[1],s[k*2+1].e[1]);
    return;
}
inline void pushdown(int k) {
    swap(s[k*2].f[0],s[k*2].f[1]),swap(s[k*2+1].f[0],s[k*2+1].f[1]);
    swap(s[k*2].e[0],s[k*2].e[1]),swap(s[k*2+1].e[0],s[k*2+1].e[1]);
    s[k*2].tag^=1,s[k*2+1].tag^=1;
    s[k].tag=0;
    return;
}
void build(int l,int r,int k) {
    s[k].l=l,s[k].r=r,s[k].tag=0;
    if(l==r) {
        s[k].f[ans[l]]=l,s[k].f[ans[l]^1]=N;
        s[k].e[ans[l]]=l,s[k].e[ans[l]^1]=-20;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,k*2),build(mid+1,r,k*2+1);
    pushup(k);
    return;
}
int check(int L,int R,int k,int x) {
    int l=s[k].l,r=s[k].r;
    if(l>=L&&r<=R) return s[k].f[x];
    if(s[k].tag) pushdown(k);
    int res=N;
    int mid=(l+r)/2;
    if(mid>=L) res=min(res,check(L,R,k*2,x));
    if(mid<R) res=min(res,check(L,R,k*2+1,x));
    return res;
}
int get(int L,int R,int k) {
    int l=s[k].l,r=s[k].r;
    if(l>=L&&r<=R) return s[k].e[1];
    if(s[k].tag) pushdown(k);
    int res=0;
    int mid=(l+r)/2;
    if(mid>=L) res=max(res,get(L,R,k*2));
    if(mid<R) res=max(res,get(L,R,k*2+1));
    return res;
}
void change(int L,int R,int k) {
    int l=s[k].l,r=s[k].r;
    if(l>=L&&r<=R) {swap(s[k].f[0],s[k].f[1]),swap(s[k].e[0],s[k].e[1]),s[k].tag^=1;return;}
    if(s[k].tag) pushdown(k);
    int mid=(l+r)/2;
    if(mid>=L) change(L,R,k*2);
    if(mid<R) change(L,R,k*2+1);
    pushup(k);
    return;
}
int main() {
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        ans[a[i]]++,w=max(w,a[i]);
    }
    init();
    build(1,N-25,1);
    while(q--) {
        int k,l;
        scanf("%d%d",&k,&l);
        if(a[k]!=l) {
            int r=check(a[k],N-25,1,1);
            change(a[k],r,1);
            a[k]=l,r=check(l,N-25,1,0);
            change(l,r,1);
            w=get(1,N-25,1);
        }
        printf("%d\n",w);
    }
    return 0;
}