CF 1558F

题目

链接

题解

首先考虑最后的答案形式应该是什么样的。观察到一个序列被排好，当且仅当 $\leq n $ 的都被放到最左边，\(\leq n-1\) 的都被放到最左边….\(\leq 1\) 的都被放到最左边，那么反过来，设 \(t_i\) 表示在第 \(t_i\) 个时刻，\(\leq i\) 的 \(i\) 个数被放到了序列的最左边，则 \(\text{ans}=\max_{i=1}^{n}t_i\)

现在只需要求出每个 \(t_{i}\) ，考虑扫描线，在扫到 \(i\) 的时候将 \(\leq i\) 的数都标记成 \(0\) ，剩下的数都标记成 \(1\) ，则所求值就是将所有 \(0\) 都移到最左边的步数。

设 \(p_1...p_i\) 表示当前 \(k\) 个 \(0\) 的位置，\(b_k\) 表示第 \(k\) 个 \(0\) 移动到位置 \(k\) 所需要的步数，\(v_k\) 表示第 \(i\) 个 \(0\) 前有多少个 \(1\)

首先可以发现对于 \(p_k=k\) 有 \(b_k=0\)，并且对于 \(k>1\)，有 $b_{k}\geq b_{k-1}+1 $ ，因为只有当 \(k-1\) 走到 \(k-1\) 上之后 \(k\) 才能走到 \(k\) ，不可能比它早到达

由于每次交换都是 \(0\) 与 \(1\) 交换，那么还可以得出不等式 \(b_k\geq v_k +(k \mod 2)\) ，加上 \(k \mod 2\) 的原因是讨论一下第一步能不能走。

再仔细考虑一下，不难发现 \(b_k=\max(b_{k-1}+1,v_k+(k\mod 2))\) ，因为如果 \(b_k\) 在走的过程中一直没有碰到 \(b_{k-1}\) ，那么肯定是每次都与 \(1\) 在交换 (左边没有出现过 \(0\)) ，而如果走了几步后碰到了 \(b_{k-1}\) ，那么以后它们走的时刻肯定是交错的，那么它的答案就被赋成了 \(b_{k-1}+1\) 。

而我们根据前面推出的性质可以发现 \(b_i\) 一定是全局最大值，那么 \(t_i=\max_{k=1}^{i}v_k+(k\mod 2)+(i-k)\)

在从 \(i\) 转移到 \(i+1\) 的时候，只有一个位置从 \(1\) 变成 \(0\) ，所以直接用线段树维护式子，计算答案。

这个题主要是不断地在化简状态。先把答案表示成另一个状态的 \(\max\) ，然后再在该状态上继续找性质又推出所能表示它的另一个状态，化到只与原序列有关后一遍扫描线利用数据结构求出答案。谁能教教怎么找答案的性质啊 \(/\text{ll}\)

const int N=2e5+5;
int T,n,a[N],pos[N],b[N];
#define mid ((l+r)>>1)
#define ls (u<<1)
#define rs (u<<1|1)
int maxx[N*4],tag[N*4];
void build(int u,int l,int r){
	tag[u]=0;maxx[u]=-1e9;
	if(l==r){
		maxx[u]+=(l%2);
		return ;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void pushdown(int u){
	if(tag[u]){
		maxx[ls]+=tag[u];
		maxx[rs]+=tag[u];
		tag[ls]+=tag[u];
		tag[rs]+=tag[u];
		tag[u]=0;
	}
}
void add(int u,int l,int r,int L,int R,int k){
	if(L>R)return ;
	if(L<=l and R>=r){
		tag[u]+=k;maxx[u]+=k;
		return ;
	}
	pushdown(u);
	if(L<=mid)add(ls,l,mid,L,R,k);
	if(R>mid)add(rs,mid+1,r,L,R,k);
	maxx[u]=max(maxx[ls],maxx[rs]);
}
void modify(int u,int l,int r,int x,int k){
	if(l==r){
		maxx[u]+=k;
		return ;
	}
	pushdown(u);
	if(x<=mid)modify(ls,l,mid,x,k);
	else modify(rs,mid+1,r,x,k);
	maxx[u]=max(maxx[ls],maxx[rs]);
}
void work(int u,int l,int r){
	maxx[u]=tag[u]=0;
	if(l==r)return ;
	work(ls,l,mid);
	work(rs,mid+1,r);
}
void solve(){
	build(1,1,n);
	int tmp=0;
	for(int i=1;i<=n;i++){
		add(1,1,n,i,i,i-1);
	}
	int head=0;
	for(int i=1;i<=n;i++){
		add(1,1,n,pos[i]+1,n,-2);
		modify(1,1,n,pos[i],1e9-1);
		b[pos[i]]=1;
		while(head