zkx06111's Blog

//树状数组首杀！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define lowbit(x) ((x)&(-x))
#define MAXN 200005
 
using namespace std;
 
int tree[MAXN],top,n; //tree为树状数组；top为离散化后y的最大值
set<int> out; //out为输出的集合
struct Point {
    int x,y,rk; //x,y为坐标；rk代表按y离散化后的序号；
    int xn,yn; //xn,yn为该点所在横、竖线上点的个数；
    int ans, //ans为以该点来划分，Stan取得个数；
        mn; //mn为画过该点的竖线Stan取得个数的最小值；
}p[MAXN];
 
void add(int x,int v) {
    while (x<MAXN) {
        tree[x]+=v;
        x+=lowbit(x);
    }
}
 
int get(int x) {
    int res=0;
    while (x) {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
 
int get(int x,int y) {
    return get(y)-get(x-1);
}
 
bool cmpy(Point a,Point b) {
    return a.y<b.y;
}
 
bool cmp1(Point a,Point b) {
    if (a.x==b.x) return a.y>b.y;
    return a.x<b.x;
}
 
bool cmp2(Point a,Point b) {
    if (a.x==b.x) return a.y<b.y;
    return a.x>b.x;
}
 
int main() {
    memset(tree,0,sizeof(tree));
    scanf("%d",&n);
    for (int i=0;i<n;++i) {
        scanf("%d%d",&p[i].x,&p[i].y);
        p[i].ans=p[i].xn=p[i].yn=0;
    }
    //读入
    sort(p,p+n,cmpy);
    top=1;
    for (int i=0;i<n;++i) {
        if (i && p[i].y!=p[i-1].y) ++top;
        p[i].rk=top; add(p[i].rk,1);
    }
    //离散化
    for (int i=0;i<n;++i) {
        int j,t=0;
        for (j=i;p[i].y==p[j].y && j<n;++j) ++t;
        for (j=i;p[i].y==p[j].y && j<n;++j) p[i].yn=t;
        i=j-1;
    }
    //计算yn
    sort(p,p+n,cmp1);
    for (int i=0;i<n;++i) {
        add(p[i].rk,-1);
        p[i].ans+=get(p[i].rk+1,top);
    }
    for (int i=0;i<n;++i) {
        int j,t=0;
        for (j=i;p[i].x==p[j].x && j<n;++j) ++t;
        for (j=i;p[i].x==p[j].x && j<n;++j) p[i].xn=t;
        i=j-1;
    }
    //计算每个点右上方点的个数并同时计算yn
    memset(tree,0,sizeof(tree));
    for (int i=0;i<n;++i) add(p[i].rk,1); //把数组恢复原状
    sort(p,p+n,cmp2);
    for (int i=0;i<n;++i) {
        add(p[i].rk,-1);
        p[i].ans+=get(1,p[i].rk-1);
    }
    //计算每个点左下方点的个数
    for (int i=0;i<n;++i) {
        int j,Min=99999999;
        for (j=i;p[i].x==p[j].x && j<n;++j) Min=min(p[j].ans,Min);
        for (j=i;p[i].x==p[j].x && j<n;++j) p[j].mn=Min;
        i=j-1;
    }
    //计算每条竖线Stan拿到的最小值
    int Max=0; out.clear();
    for (int i=0;i<n;++i) {
        if (p[i].mn!=p[i].ans) continue;
        if (p[i].ans>Max) {
            Max=p[i].ans;
            out.clear();
            out.insert(n-p[i].ans-p[i].xn-p[i].yn+1); //Ollie拿到的饼数
        }
        else if (p[i].ans==Max)
            out.insert(n-p[i].ans-p[i].xn-p[i].yn+1);
    }
    printf("Stan: %d; Ollie:",Max);
    for (set<int>::iterator it=out.begin(); it!=out.end();++it)
        printf(" %d",*it);
    printf(";\n");
    return 0;
}