决斗（线段树）

本文主要是介绍决斗（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

青蛙哥与名侦探柯南正在进行一场对决。他们两个人每人有 $n$ 张牌，每张牌有一个点数。

并且在接下来的 $n$ 个回合中每回合青蛙哥与名侦探柯南两人会各自打出一张牌。

每回合裁判会检查，打出的牌点数更高的一方获胜从而得到一分，如果二人点数相同，则不得分。

然而现在青蛙哥通过偷看的方法得到了名侦探柯南的出牌顺序，他可以任意定一个自己的出牌的顺序。

他首先希望让自己的得分尽可能高，然后就是希望在让自己的得分尽可能高这个前提下，最大化自己从第一回合开始到最后一个回合结束过程中，每回合出牌点数构成的字符串的字典序。

$1\le n,a_i,b_i\le 10^5$

---

假设我们已经求出青蛙最多得 $k$ 分，那么下面按顺序考虑填入什么数字能使字典序最大。

对于第 $i$ 回合，如果我们要赢，可以出最大的，但是如果这么做可能会影响后面需要它来赢的回合；如果我们要输，可以出最小的，但是字典序就不一定最大。容易得到出牌点数在一个区间 $[l,r]$ 内。

这时可以二分求出我们能填的最大点数，然后判断出这张是否会影响得分。

判断的实现可以用线段树。建权值线段树，每个节点维护三元组 $(s,s_1,s_2)$，分别表示 当前值域的得分、柯南剩的牌数、青蛙剩的牌数。在向上合并信息时，青蛙可以用自己的大牌去对柯南的小牌，青蛙的得分是 $R_{s_2}-L_{s_1}$，就是用右区间青蛙牌数减去左区间柯南牌数。$s_1,s_2$ 的维护显然。

具体实现参照代码。

时间复杂度 $O(n{\log }^{2}V)$，其中 $V$ 是值域。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,a[N],b[N];
multiset<int> s;
struct node
{int s,s1,s2;//a b
}tr[N<<2];
void pushup(int rt)
{int x=min(tr[rt<<1|1].s2,tr[rt<<1].s1);tr[rt].s=tr[rt<<1].s+tr[rt<<1|1].s+x;tr[rt].s1=tr[rt<<1].s1+tr[rt<<1|1].s1-x;tr[rt].s2=tr[rt<<1].s2+tr[rt<<1|1].s2-x;
}
void update(int rt,int l,int r,int x,int d1,int d2)
{if(l==r){tr[rt].s1+=d1;tr[rt].s2+=d2;return;}int mid=l+r>>1;if(x<=mid) update(rt<<1,l,mid,x,d1,d2);else update(rt<<1|1,mid+1,r,x,d1,d2);pushup(rt);
}
int main()
{// freopen("duel.in","r",stdin);// freopen("duel.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i],update(1,1,100000,a[i],1,0);for(int i=1;i<=n;i++) cin>>b[i],update(1,1,100000,b[i],0,1),s.insert(b[i]);int ans=tr[1].s;//剩余回合需得分数for(int i=1;i<=n;i++){update(1,1,100000,a[i],-1,0);//删去ai，如果不会对得分有影响，tr[1].s恒为ans，即二分不起作用int l=a[i]+1,r=*s.rbegin(),Ans;while(l<=r){int mid=l+r>>1;update(1,1,100000,mid,0,-1);if(tr[1].s+1==ans) l=mid+1,Ans=mid;//如果有影响分数，就尝试提高点数else r=mid-1;update(1,1,100000,mid,0,1);}update(1,1,100000,Ans,0,-1);if(a[i]<*s.rbegin()&&tr[1].s+1==ans){//二分的答案Ans合法，此回合得分ans--;cout<<Ans<<" ";s.erase(s.find(Ans));}else{//此回合不能得分update(1,1,100000,Ans,0,1);l=1,r=a[i],Ans=l;//青蛙的牌不超过aiwhile(l<=r){int mid=l+r>>1;update(1,1,100000,mid,0,-1);if(tr[1].s==ans) l=mid+1,Ans=mid;//如果不影响分数，就尝试提高点数else r=mid-1;update(1,1,100000,mid,0,1);}update(1,1,100000,Ans,0,-1);cout<<Ans<<" ";s.erase(s.find(Ans));}}
}

这篇关于决斗（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---