poj 2464 Brownie Points II(2本の線分樹-線分樹区間和)
Brownie Points II
Time Limit: 5000MS
Memory Limit: 65536K
Total Submissions: 1354
Accepted: 478
Description
Stan and Ollie play the game of Odd Brownie Points. Some brownie points are located in the plane, at integer coordinates. Stan plays first and places a vertical line in the plane. The line must go through a brownie point and may cross many (with the same x-coordinate). Then Ollie places a horizontal line that must cross a brownie point already crossed by the vertical line.
Those lines divide the plane into four quadrants. The quadrant containing points with arbitrarily large positive coordinates is the top-right quadrant.
The players score according to the number of brownie points in the quadrants. If a brownie point is crossed by a line, it doesn't count. Stan gets a point for each (uncrossed) brownie point in the top-right and bottom-left quadrants. Ollie gets a point for each (uncrossed) brownie point in the top-left and bottom-right quadrants.
Stan and Ollie each try to maximize his own score. When Stan plays, he considers the responses, and chooses a line which maximizes his smallest-possible score.
Input
Input contains a number of test cases. The data of each test case appear on a sequence of input lines. The first line of each test case contains a positive odd integer 1 < n < 200000 which is the number of brownie points. Each of the following n lines contains two integers, the horizontal (x) and vertical (y) coordinates of a brownie point. No two brownie points occupy the same place. The input ends with a line containing 0 (instead of the n of a test).
Output
For each input test, print a line of output in the format shown below. The first number is the largest score which Stan can assure for himself. The remaining numbers are the possible (high) scores of Ollie, in increasing order.
Sample Input
Waterloo local 2005.06.11
タイトル:http://poj.org/problem?id=2464
题意:この问题の题意は本当に私达のこのようなE文の悪い菜鸟を虐げて、题意の理解は正しいで1晩使って、木があります==
2人でゲームをしています.平面にはnつの点があります.stanは1つの点を選んで、この点を通る縦線を描きます.ollieは縦線を通る点を選んで、横線を描きます.それから平面は4つの象限に分けられます.1、3象限の点数はstanの点数で、2、4象限の点数はollieの点数で、座標軸の点数は計算されません.今stanは彼が必ず得ることができる最大の得点を知りたいと思って、つまり1本の縦線を選んで、最悪の情況の下で得る点数は最大で、ollieはstanが縦線を選んだ後でできるだけ最大を取って、もちろん、stanは多種の選法があるかもしれないので、ollieも複数の得点があります.
分析:この问题は题意をはっきり见てから、実は方法はとても考えやすいですが、実现するのは本当に面倒で、私の方法は他の人とは违うようですが、大同小異で、まずy座標を離散化して、それから统计はy座標の点数より大きいとそれより小さい点数を上回って、stanがxの最小の縦線を选ぶと仮定して、それでは明らかです.ollieは各横線を選択した後、2人の点数を統計することができます(一部の横線は選択できませんが)、2本の線分ツリーを構築し、1本の統計stanの点数、もう1本の統計ollieの点数、stanの線分ツリーの初期値は大きなy座標の初期値ですが、ollieはちょうど反対で、それからx座標を押して、小さいから大きいまですべての点をスキャンして、1つの点について、まずその線分を含む線分で1を減らして、それから尋ねます.次に、新しい線分に1を加え、x座標が同じ点に対して、この縦線が同じであるため、集団で操作します.
説明があまりよくないので、詳しくはコードを参照してください==
注意点:ollieの得点が同じなら1回出力し、座標軸上の点は計算されず、統計時に境界賦値に注意する
コード:
Time Limit: 5000MS
Memory Limit: 65536K
Total Submissions: 1354
Accepted: 478
Description
Stan and Ollie play the game of Odd Brownie Points. Some brownie points are located in the plane, at integer coordinates. Stan plays first and places a vertical line in the plane. The line must go through a brownie point and may cross many (with the same x-coordinate). Then Ollie places a horizontal line that must cross a brownie point already crossed by the vertical line.
Those lines divide the plane into four quadrants. The quadrant containing points with arbitrarily large positive coordinates is the top-right quadrant.
The players score according to the number of brownie points in the quadrants. If a brownie point is crossed by a line, it doesn't count. Stan gets a point for each (uncrossed) brownie point in the top-right and bottom-left quadrants. Ollie gets a point for each (uncrossed) brownie point in the top-left and bottom-right quadrants.
Stan and Ollie each try to maximize his own score. When Stan plays, he considers the responses, and chooses a line which maximizes his smallest-possible score.
Input
Input contains a number of test cases. The data of each test case appear on a sequence of input lines. The first line of each test case contains a positive odd integer 1 < n < 200000 which is the number of brownie points. Each of the following n lines contains two integers, the horizontal (x) and vertical (y) coordinates of a brownie point. No two brownie points occupy the same place. The input ends with a line containing 0 (instead of the n of a test).
Output
For each input test, print a line of output in the format shown below. The first number is the largest score which Stan can assure for himself. The remaining numbers are the possible (high) scores of Ollie, in increasing order.
Sample Input
11
3 2
3 3
3 4
3 6
2 -2
1 -3
0 0
-3 -3
-3 -2
-3 -4
3 -7
0
Stan: 7; Ollie: 2 3;
Waterloo local 2005.06.11
タイトル:http://poj.org/problem?id=2464
题意:この问题の题意は本当に私达のこのようなE文の悪い菜鸟を虐げて、题意の理解は正しいで1晩使って、木があります==
2人でゲームをしています.平面にはnつの点があります.stanは1つの点を選んで、この点を通る縦線を描きます.ollieは縦線を通る点を選んで、横線を描きます.それから平面は4つの象限に分けられます.1、3象限の点数はstanの点数で、2、4象限の点数はollieの点数で、座標軸の点数は計算されません.今stanは彼が必ず得ることができる最大の得点を知りたいと思って、つまり1本の縦線を選んで、最悪の情況の下で得る点数は最大で、ollieはstanが縦線を選んだ後でできるだけ最大を取って、もちろん、stanは多種の選法があるかもしれないので、ollieも複数の得点があります.
分析:この问题は题意をはっきり见てから、実は方法はとても考えやすいですが、実现するのは本当に面倒で、私の方法は他の人とは违うようですが、大同小異で、まずy座標を離散化して、それから统计はy座標の点数より大きいとそれより小さい点数を上回って、stanがxの最小の縦線を选ぶと仮定して、それでは明らかです.ollieは各横線を選択した後、2人の点数を統計することができます(一部の横線は選択できませんが)、2本の線分ツリーを構築し、1本の統計stanの点数、もう1本の統計ollieの点数、stanの線分ツリーの初期値は大きなy座標の初期値ですが、ollieはちょうど反対で、それからx座標を押して、小さいから大きいまですべての点をスキャンして、1つの点について、まずその線分を含む線分で1を減らして、それから尋ねます.次に、新しい線分に1を加え、x座標が同じ点に対して、この縦線が同じであるため、集団で操作します.
説明があまりよくないので、詳しくはコードを参照してください==
注意点:ollieの得点が同じなら1回出力し、座標軸上の点は計算されず、統計時に境界賦値に注意する
コード:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const int mm=222222;
const int mn=mm<<2;
struct point
{
int x,y;
}g[mm];
int dly[mn][2];
int y[mm],a[mm],b[mm],q[mm];
void pushdown(int rt,int o)
{
if(dly[rt][o])
{
dly[ls][o]+=dly[rt][o];
dly[rs][o]+=dly[rt][o];
dly[rt][o]=0;
}
}
void build(int l,int r,int rt)
{
dly[rt][0]=dly[rt][1]=0;
if(l==r)
{
dly[rt][0]=b[l],dly[rt][1]=a[l];
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
}
void updata(int L,int R,int val,int l,int r,int rt,int o)
{
if(L<=y[l]&&R>=y[r])
{
dly[rt][o]+=val;
return;
}
pushdown(rt,o);
int m=(l+r)>>1;
if(L<=y[m])updata(L,R,val,lson,o);
if(R>=y[m+1])updata(L,R,val,rson,o);
}
int query(int x,int l,int r,int rt)
{
if(l==r)return rt;
pushdown(rt,0);
pushdown(rt,1);
int m=(l+r)>>1;
if(x<=y[m])return query(x,lson);
return query(x,rson);
}
bool cmp(point a,point b)
{
return a.x<b.x;
}
int main()
{
int i,j,k,l,r,n,m,ans,maxx,minn;
while(scanf("%d",&n),n)
{
for(i=0;i<n;++i)
{
scanf("%d%d",&g[i].x,&g[i].y);
y[i]=g[i].y;
}
sort(y,y+n);
sort(g,g+n,cmp);
a[0]=0;
for(m=i=0;i<n;++i)
if(y[m]<y[i])
{
b[m]=n-i;
y[++m]=y[i];
a[m]=i;
}
b[m]=0;// wa
build(0,m,1);
ans=r=i=0;
while(i<n)
{
for(j=i;j<n;++j)//x
{
if(g[j].y>y[0])updata(y[0],g[j].y-1,-1,0,m,1,0);
if(g[j].y<y[m])updata(g[j].y+1,y[m],-1,0,m,1,1);
if(g[j].x!=g[j+1].x)break;
}
maxx=0,minn=n;
for(k=i;k<=j;++k)
{
l=query(g[k].y,0,m,1);
minn=min(minn,dly[l][0]);
maxx=max(maxx,dly[l][1]);
}
if(minn==ans)q[r++]=maxx;
if(minn>ans)
{
ans=minn;
q[0]=maxx;
r=1;
}
for(;i<=j;++i)
{
if(g[i].y>y[0])updata(y[0],g[i].y-1,1,0,m,1,1);
if(g[i].y<y[m])updata(g[i].y+1,y[m],1,0,m,1,0);
}
}
sort(q,q+r);
for(k=i=0;i<r;++i)// 1
if(q[k]<q[i])q[++k]=q[i];
printf("Stan: %d; Ollie:",ans);
for(i=0;i<=k;++i)printf(" %d",q[i]);
puts(";");
}
return 0;
}