【搬自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); }