【JZOJ6228】【20190621】ni

题目

$ n $ 个数 $ E_i $ ，$ F(i) $ 表示对1-i的数任意排列 $ p $ ，初始 $ X=0 $ ，依次执行：

• (X lt E_{p_j} , X++)
• $X gt E_{p_j} , X-- $
• (X = E_{p_j} ，X不变)

能够得到的最大值,求F(1)~F(n)

$1 le n le 5 imes 10^5 , -10^5 le E_i le 10^5 $

题解

• 可以证明，最优的(p)是E的升序

• 对于确定的序列，X一定是先一直-1，再+1或者不变，设分界点值为(pos)

• solve 1:

  如果出现了相同的数字，我们可以换成不相同的递增数列，例如：
  2 2 2 2 <=> -1 0 1 2

  由于E是升序排的，这对答案没有影响

  考虑增量的时候用并查集维护可以放的位置

  需要维护(pos)和在它前面的数的个数(rk)

  答案是：$ i - 2*rk - [pos+rk=0] $

  具体：(pos)是第一个满足(pos + rk ge 0) 的值

  由于(rk)每次最多++，所以每次加入(i)只需要检查一下(-rk'+1)和(E_i)是否合法

  代码不能再短了QAQ

  #include<bits/stdc++.h>
  using namespace std;
  const int N=2000010,B=1000000;
  int n,E[N],f[N],vis[N];
  int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
  int main(){
  	freopen("ni.in","r",stdin);
  	freopen("ni.out","w",stdout);
  	scanf("%d",&n);
  	for(int i=-B;i<=B;++i)f[i+B]=i+B;
  	int pos=B,rk=0;
  	for(int i=1,x;i<=n;++i){
  		scanf("%d",&x);
  		x=find(x+B)-B;
  		f[x+B]=f[x+B-1];
  		vis[x+B]=1;
  		if(x<pos){
  			rk++;
  			if(x>=-rk+1)pos=x,rk--;
  			else if(-rk+1<pos&&vis[-rk+1+B])pos=-rk+1,rk--;
  		}
  		int ans=i-2*rk-(rk+pos==0);
  		printf("%d
  ",ans);
  	}
  	return 0;
  }
  

• sol 2

  

这是ljz写的解法二