这题相当的精彩，写完这个对码力和思维都有很大的提升。
题目的意思是stan先画竖线，oll画横线且过stan的一个点，stan先画，因为两个人都想赢，oll后画，所以oll肯定会在stan的基础上找最大的，那么stan所求的自然是最小的情况，因为总点数是固定的
但是stan也想赢，所以他可以决定竖线的位置，使得最小值最大，这就是我们想要求的值
1.本题相当于把每个点当作原点求四个象限的值，我们可以想到，可以用树状数组求一个象限的值，并维护left,right,up,down，和large（比当前点y的y大的数，用来求第一象限）因为我们知道，坐标系上的点是不算在象限内的，所以便于计算
那么我们如何这些呢？，我们排序两次，第一次按y排序，这样如果一个点的y跟前面的一样，那么他的x肯定比前面的大，所以可以求left，同理，倒序枚举可以计算r，如果不清楚关系，可以在纸上画个数轴模拟，同时求large。同理求down，up；具体可以看代码
2.求出这些值后，我们就能分别计算各个象限了，比如第三象限就是 sum(find(q[i].y))-l[q[i].id]-down[q[i].id]
其他情况自己来推，这样才会有提升
3.注意要下标隐射，因为我们排序后的位置就不是原来的位置了
4.注意离散化。
#include<algorithm> #include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<set> using namespace std; typedef long long ll; const int N=2e5+10; const int inf=0x3f3f3f3f; int l[N],r[N],up[N],down[N]; int large[N]; int tr[N]; vector<int> num; int find(int x){ return lower_bound(num.begin(),num.end(),x)-num.begin()+1; } struct node{ int x,y; int id; }p[N]; bool cmp1(node a,node b){ if(a.y==b.y) return a.x<b.x; return a.y<b.y; } bool cmp2(node a,node b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int lowbit(int x){ return x&-x; } void add(int x,int c){ int i; for(i=x;i<=N;i+=lowbit(i)) tr[i]+=c; } int sum(int x){ int i; int res=0; for(i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } int main(){ int i; int n; while(cin>>n,n){ num.clear(); for(i=0;i<n;i++){ scanf("%d%d",&p[i].x,&p[i].y); p[i].id=i; } memset(l,0,sizeof l); memset(r,0,sizeof r); memset(up,0,sizeof up); memset(down,0,sizeof down); memset(tr,0,sizeof tr); memset(large,0,sizeof large); sort(p,p+n,cmp1); for(i=1;i<n;i++){ if(p[i].y==p[i-1].y) l[p[i].id]=l[p[i-1].id]+1; if(p[n-i-1].y==p[n-i].y){ r[p[n-1-i].id]=r[p[n-i].id]+1; large[p[n-1-i].id]=large[p[n-i].id]; } else large[p[n-1-i].id]=i; } for(i=0;i<n;i++) num.push_back(p[i].y); sort(num.begin(),num.end()); num.erase(unique(num.begin(),num.end()),num.end()); sort(p,p+n,cmp2); for(i=1;i<n;i++){ if(p[i].x==p[i-1].x) down[p[i].id]=down[p[i-1].id]+1; if(p[n-i-1].x==p[n-i].x){ up[p[n-i-1].id]=up[p[n-i].id]+1; } } int tmp=0; set<int> st; int px=p[0].x; for(i=0;i<n;i++){ int oll=0; int sta=inf; while(i<n&&p[i].x==px){ int pos=find(p[i].y); int bl=sum(pos)-l[p[i].id]-down[p[i].id]; int tl=i-sum(pos); int trr=large[p[i].id]-tl-up[p[i].id]; int br=n-1-tl-trr-bl-l[p[i].id]-r[p[i].id]-up[p[i].id]-down[p[i].id]; int ans=tl+br; add(pos,1); if(ans>oll){ oll=ans; sta=trr+bl; } else if(ans==oll){ sta=min(sta,trr+bl); } i++; } if(i<n) px=p[i--].x; if(sta>tmp){ tmp=sta; st.clear(); st.insert(oll); } else if(sta==tmp) st.insert(oll); } printf("Stan: %d; Ollie:",tmp); set<int>::iterator it; for(it = st.begin(); it != st.end(); it++) printf(" %d", *it); printf("; "); } }