【搬自usaco2015Dec】【JZOJ4684】卡牌游戏 题解

usaco原题叫 High Card Low Card

【题目大意】

  有2n张牌，分别是1~2n。WWT有其中的n张牌，你有另n张。
  游戏规则本来是这样的：每一回合，你和WWT同时打出一张牌，谁大谁赢。但是，你可以在任意一个时刻将游戏规则改为“谁小谁赢”，但你只能改一次。
  现在给定WWT的牌和出牌顺序，求你最多赢多少局。
  n<=50000

【n^2部分分】

  枚举分割点，然后分割点上面的排序，分割点下面的排序，做个贪心。

【n log n】

  还是枚举分割点，然后我们需要快速地知道分割点上面的答案f[i]以及分割点下面的答案g[i+1]。以f为例看看怎么求。

  许多人会想到排序贪心，这搞了半天又回归到部分分。我们不必贪心，用线段树那样的分治就好了。
  把WWT的牌叫做a，你的牌叫做b。考虑一棵值域线段树（轴为1~2n），我插入1个a[i]，它只能被a[i]+1~2n打掉；我插入1个b[i]，它只能打掉1~b[i]-1。
  于是我们每个区间维护两个值：ta表示区间内有多少个a没被打掉，tb表示区间内有多少个b剩余。（想想如果a在区间的很右边，那它在这个区间内就打不掉的了，得留着放在更大的区间来打。b如果在区间很左边，那它在这个区间内打不到a的话，就留着在更大的区间去打）
  接下来就是两个区间的合并。假设当前区间的值为ta、tb，左儿子为ta[l]、tb[l]，右儿子为ta[r]、tb[r]。那么ta=ta[r]+max(0,ta[l]-tb[r])，tb=tb[l]+max(0,tb[r]-ta[l])。如果你理解了上面那段话，这个合并就很好理解了。以ta为例，ta[l]是可以被tb[r]干掉的，而ta[r]则不能被干掉，所以就这样合并啦。。。

  回归本题。我们还是以f为例：顺序处理每一局。对于第i局，插入a，然后插入b，然后直接询问根节点的ta。注意根节点的ta就表示第1局到第i局共输了多少局，所以f[i]=i-ta。g数组同理。这样就做完啦。。。

代码

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int maxn=(1e5)+5;

int n,m,a[maxn],b[maxn];

int tr1[4*maxn][2],tr2[4*maxn][2];//第二维的0表示ta，1表示tb
void tr_xg1(int k,int l,int r,int x,int z)
{
	if (l==r)
	{
		if (z==1) tr1[k][0]=1; else tr1[k][1]=1;
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	if (x<=t1) tr_xg1(t,l,t1,x,z); else tr_xg1(t+1,t1+1,r,x,z);
	tr1[k][0]=tr1[t][0]+max(0,tr1[t+1][0]-tr1[t][1]);
	tr1[k][1]=tr1[t+1][1]+max(0,tr1[t][1]-tr1[t+1][0]);
}
void tr_xg2(int k,int l,int r,int x,int z)
{
	if (l==r)
	{
		if (z==1) tr2[k][0]=1; else tr2[k][1]=1;
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	if (x<=t1) tr_xg2(t,l,t1,x,z); else tr_xg2(t+1,t1+1,r,x,z);
	tr2[k][0]=tr2[t+1][0]+max(0,tr2[t][0]-tr2[t+1][1]);
	tr2[k][1]=tr2[t][1]+max(0,tr2[t+1][1]-tr2[t][0]);
}

bool bz[maxn];
int f[maxn],g[maxn];
int main()
{
	scanf("%d",&n);
	m=2*n;
	fo(i,1,n)
	{
		scanf("%d",&a[i]);
		bz[a[i]]=1;
	}
	int b0=0;
	fd(i,m,1) if (!bz[i]) b[++b0]=i;
	
	fo(i,1,n)
	{
		tr_xg1(1,1,m,a[i],-1);
		tr_xg1(1,1,m,b[i],1);
		f[i]=i-tr1[1][1];
	}
	fd(i,n,1)
	{
		tr_xg2(1,1,m,a[i],-1);
		tr_xg2(1,1,m,b[i],1);
		g[i]=(n-i+1)-tr2[1][1];
	}
	
	int ans=0;
	fo(i,0,n) ans=max(ans,f[i]+g[i+1]);
	
	printf("%d\n",ans);
}