CF1705E Mark and Professor Koro 题解

[可能更好的阅读体验](https://www.cnblogs.com/jiangtaizhe001/p/16491542.html) [题目传送门](http://codeforces.com/problemset/problem/1705/E) ### 题目大意 黑板上有 $n$ 个数字 $a_1,a_2,\dots,a_n$，现在你可以将黑板上相同的两个数字 $x$ 擦掉，然后写上 $x+1$，求最后能得到的最大数字。 当然你需要支持单点修改。 $1\le n,q,a_i\le 2\times10^5$ ### 题目解析 不难发现题目给定的操作比较像二进制加法。如果把所有能够合并的数字都合并，那么每个数字最多出现一次，如果出现了数字 $x$ 那么就说明二进制下从右往左第 $x$ 位是 $1$，否则是 $0$。 考虑修改其实就是删去一个数字，然后加上一个数字。如果说把 $a_x$ 改为 $y$，也就是减去 $2^{a_x}$，加上 $2^{y}$。 这样也就是维护一个大整数。 考虑加上一个数字，如果这一位是 $0$，直接把这一位改成 $1$，否则找到更高位出现的第一个 $0$，把这个 $0$ 改成 $1$，然后把这一段 $1$ 改成 $0$。 删除其实是一样的。如果这一位是 $1$，就把这一位改成 $0$，否则找到更高位的第一个 $1$，改成 $0$，然后把连续的 $1$ 改成 $0$。 也就是说需要维护一个数据结构支持区间修改，查询一个点右边第一个 $0/1$，并且能查询最高位的 $1$。 用线段树+线段树二分维护就可以了，维护区间最小值和最大值以及区间覆盖的懒惰标记即可。 最后注意答案可能超过 $2\times 10^5$，数组要开大一点。 时间复杂度 $O(T\log n)$ ```cpp int n,T,x,y,tmp,a[maxn],t[maxn],minx[maxn<<2],maxx[maxn<<2],f[maxn<<2],L,R,C; void up(int rt){ minx[rt]=mmin(minx[rt<<1],minx[rt<<1|1]); maxx[rt]=mmax(maxx[rt<<1],maxx[rt<<1|1]); return; } void down(int rt){ if(f[rt]!=-1){ minx[rt<<1]=maxx[rt<<1]=f[rt<<1]=f[rt]; minx[rt<<1|1]=maxx[rt<<1|1]=f[rt<<1|1]=f[rt]; f[rt]=-1; } return; } void build(int l,int r,int rt){ f[rt]=-1; if(l==r){ maxx[rt]=minx[rt]=t[l]; return; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); up(rt); return; } void update(int l,int r,int rt){ if(L<=l&&r<=R){ minx[rt]=maxx[rt]=f[rt]=C; return; } int mid=(l+r)>>1; down(rt); if(mid>=L) update(l,mid,rt<<1); if(mid<R) update(mid+1,r,rt<<1|1); up(rt); return; } int query1(int l,int r,int rt){ if(maxx[rt]==0) return INF; if(l==r) return l; int mid=(l+r)>>1; down(rt); if(mid>=L&&maxx[rt<<1]){ int tmp=query1(l,mid,rt<<1); if(tmp!=INF) return tmp; } return query1(mid+1,r,rt<<1|1); } int query0(int l,int r,int rt){ if(minx[rt]) return INF; if(l==r) return l; int mid=(l+r)>>1; down(rt); if(mid>=L&&!minx[rt<<1]){ int tmp=query0(l,mid,rt<<1); if(tmp!=INF) return tmp; } return query0(mid+1,r,rt<<1|1); } int findans(int l,int r,int rt){ if(!maxx[rt]) return -1; if(l==r) return l; int mid=(l+r)>>1; down(rt); if(maxx[rt<<1|1]) return findans(mid+1,r,rt<<1|1); else return findans(l,mid,rt<<1); } int main(){ n=read(); T=read(); int i; for(i=1;i<=n;i++) a[i]=read(),t[a[i]]++; for(i=1;i<=N;i++) t[i+1]+=t[i]/2,t[i]&=1; build(1,N,1); while(T--){ x=read(); y=read(); L=a[x]; tmp=query1(1,N,1); L=R=tmp; C=0; update(1,N,1); if(tmp>a[x]){ L=a[x]; R=tmp-1; C=1; update(1,N,1); } L=y; tmp=query0(1,N,1); L=R=tmp; C=1; update(1,N,1); if(tmp>y){ L=y; R=tmp-1; C=0; update(1,N,1); } a[x]=y; print(findans(1,N,1)),pc('\n'); } return 0; } ```