题解 UVA10869 Brownie Points II

题意

平面上有若干点，\(\text{stan}\) 通过一个点划了一条直线，\(\text{ollie}\) 通过在这条直线上的点作了一条垂线，那么平面被分成 \(4\) 个象限，\(\text{stan}\) 获得的分数为一、三象限的点的数量，\(\text{ollie}\) 获得的分数为二、四象限上的点的数量，线上的点不归任何人所有。两人都采用最优的策略使自己获得的点数最大。由于 \(\text{stan}\) 的选择具有主动权，在对自己利益最大的情况下，求 \(\text{stan}\) 所能够获得的最小可能分数的最大值，输出该分数，并输出 \(\text{ollie}\) 所有可能的分数。

Solution

我们可以枚举每一个点作为两条直线的交点，然后计算四个象限的点数。那么可以将第一维排序，再用数据结构求出其前/后的数中大于/小于它的数。实现的方法有扫描线、主席树、树套树等等，可以自由发挥。

实际上，此题的难点在于后面对于两人分数的处理，细节较多。由于两人都用最优策略，所以当 \(\text{stan}\) 的直线上有多个点时，\(\text{ollie}\) 会选择自己得分最多的情况来作垂线。那么我们要把第一维相同的点选出最优情况后再与答案比较。

另外，若用静态数据结构实现，因为处于线上的点不计，所以需要除去其前后第一维相同的点后再在此区间计算其排名。

Code

我写的是树套树，因为不用离散化（其实是主席树写挂了

#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define upp(x,y) (upper_bound(v[x].begin(),v[x].end(),y))
#define low(x,y) (lower_bound(v[x].begin(),v[x].end(),y))
#define Rank(x,y) (upp(x,y)-v[x].begin())
#define ins(x,y) {v[x].insert(upp(x,y),y);}
using namespace std;
const int N=2e5+5;
int n,c[N],ans1,same1[N],same2[N],st[N],ol[N],las[N],nxt[N];
pair<int,int>a[N];
map<int,int>mp;
set<int>ans2;
vector<int>v[N<<2];
void build(int p,int k,int x=1,int l=1,int r=n){
    ins(x,k);
    if(l==r)return;
    int mid=l+r>>1;
    if(p<=mid)build(p,k,ls(x),l,mid);
    else build(p,k,rs(x),mid+1,r);
}
int rk(int k,int l,int r,int x=1,int L=1,int R=n){
    if(l>r)return 0;
    if(l==L&&r==R)return Rank(x,k);
    int mid=L+R>>1;
    if(r<=mid)return rk(k,l,r,ls(x),L,mid);
    else if(l>mid)return rk(k,l,r,rs(x),mid+1,R);
    else return rk(k,l,mid,ls(x),L,mid)+rk(k,mid+1,r,rs(x),mid+1,R);
}
int main(){
	while(~scanf("%d",&n)){//注意多组数据
        if(!n)return 0;
        ans1=-1;
        mp.clear();ans2.clear();
        for(int i=0;i<N*4;i++)v[i].clear();
        memset(las,0,sizeof(las));memset(nxt,0,sizeof(nxt));
        memset(same1,0,sizeof(las));memset(same2,0,sizeof(nxt));
        for(int i=0;i<=n;i++)a[i]=make_pair(1e9,1e9);
        for(int i=1;i<=n;i++)scanf("%d%d",&a[i].first,&a[i].second);
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            c[i]=a[i].second;
            same1[i]=mp[c[i]];
            mp[c[i]]++;
            if(a[i].first==a[i-1].first)las[i]=las[i-1];
            else las[i]=i;
        }
        for(int i=n;i;i--){//处理第一维相同的点
            if(a[i].first==a[i+1].first)nxt[i]=nxt[i+1];
            else nxt[i]=i;
        }
        for(int i=1;i<=n;i++)same2[i]=mp[c[i]]-1-same1[i],build(i,c[i]);
        for(int i=1;i<=n;i++){
            int r3=rk(c[i],1,las[i]-1)-same1[i],r4=rk(c[i],nxt[i]+1,n)-same2[i];
            int r1=n-nxt[i]-r4-same2[i],r2=las[i]-1-r3-same1[i];
            st[i]=r1+r3,ol[i]=r2+r4;//计算二人得分
        }
        for(int i=1;i<=n;i=nxt[i]+1){
            int ollie=-1,stan=-1;
            for(int j=las[i];j<=nxt[i];j++){//stan的线上有多个点时考虑最优
                if(ol[j]>ollie)ollie=ol[j],stan=st[j];
                else if(ol[j]==ollie)stan=min(stan,st[j]);
            }
            if(stan>ans1)ans1=stan,ans2.clear(),ans2.insert(ollie);
            else if(stan==ans1)ans2.insert(ollie);
        }
        printf("Stan: %d; Ollie:",ans1);
        for(int x:ans2)printf(" %d",x);
        puts(";");
    }
    return 0;
}

最后一首 \(\text{stan}\) 送给大家：Stan - Eminem/Dido