這道題。。太特么多細節(jié)了。。

題意：在平面直角坐標系中給你N個點，stan和ollie玩一個游戲，首先stan在豎直方向上畫一條直線，該直線必須要過其中的某個點，然后ollie在水平方向上畫一條直線，該直線的要求是要經(jīng)過一個stan之前畫過的點。 這時候平面就被分割成了四塊，兩個人這時候會有一個得分，stan的得分是平面上第1、3象限內(nèi)的點的個數(shù)，ollie的得分是平面上第2、4象限內(nèi)的點的個數(shù)，在統(tǒng)計的時候在所畫線上的點都不計算在內(nèi)。求最終stan使得自己的最差得分最高，并且輸出此時ollie的得分。

?

題解：

我們可以枚舉哪顆星星是中心點，然后就可以知道他們所確定的直線。

線上可以維護四個值：up，down，left，right，分別表示線上四個方位有多少顆星星。

然后我們只要求BL,就可以知道其它：

TL=橫坐標比x小的星星總數(shù)-BL-left

TR=y坐標比x大的星星總數(shù)-TL-up

BR=y坐標比x小的星星總數(shù)-BL-down

各種細節(jié)><

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 8 const int N=200010,INF=(int)1e9+100; 9 int n,pl,mx,c[N],cntx[N],cnty[N],sumx[N],sumy[N],sx[N][2],sy[N][2],u[N],d[N],l[N],r[N],a1[N],a2[N]; 10 bool num[N]; 11 struct node{ 12 int x,y; 13 }a[N]; 14 struct nd{ 15 int d,id,tmp; 16 }p[2*N]; 17 18 bool cmp_num(int x,int y){return x<y;} 19 bool cmp_d(nd x,nd y){return x.d<y.d;} 20 bool cmp_a(node x,node y) 21 { 22 if(x.x==y.x) return x.y<y.y; 23 return x.x<y.x; 24 } 25 int maxx(int x,int y){return x>y ? x:y;} 26 27 void clear() 28 { 29 memset(cntx,0,sizeof(cntx)); 30 memset(cnty,0,sizeof(cnty)); 31 memset(sumx,0,sizeof(sumx)); 32 memset(sumy,0,sizeof(sumy)); 33 memset(c,0,sizeof(c)); 34 memset(a1,63,sizeof(a1)); 35 memset(a2,-1,sizeof(a2)); 36 } 37 38 void add(int x) 39 { 40 for(int i=x;i<=mx;i+=(i&(-i))) c[i]++; 41 } 42 int getsum(int x) 43 { 44 int ans=0; 45 for(int i=x;i>=1;i-=(i&(-i))) ans+=c[i]; 46 return ans; 47 } 48 49 int main() 50 { 51 freopen("a.in","r",stdin); 52 // freopen("me.out","w",stdout); 53 while(1) 54 { 55 scanf("%d",&n); 56 if(n==0) break; 57 pl=0;clear(); 58 for(int i=1;i<=n;i++) 59 { 60 scanf("%d%d",&a[i].x,&a[i].y); 61 p[++pl].d=a[i].x;p[pl].id=i;p[pl].tmp=0; 62 p[++pl].d=a[i].y;p[pl].id=i;p[pl].tmp=1; 63 } 64 sort(p+1,p+1+pl,cmp_d); 65 mx=0;p[0].d=INF; 66 for(int i=1;i<=pl;i++) 67 { 68 if(p[i].d!=p[i-1].d) mx++; 69 if(p[i].tmp==0) a[p[i].id].x=mx; 70 else a[p[i].id].y=mx; 71 } 72 73 sort(a+1,a+1+n,cmp_a); 74 // for(int i=1;i<=n;i++) 75 // printf("%d %d\n",a[i].x,a[i].y); 76 for(int i=1;i<=n;i++) 77 { 78 d[i]=cntx[a[i].x];cntx[a[i].x]++; 79 l[i]=cnty[a[i].y];cnty[a[i].y]++; 80 } 81 // for(int i=1;i<=mx;i++) 82 // printf("i = %d %d %d\n",i,cntx[i],cnty[i]); 83 for(int i=1;i<=n;i++) 84 { 85 u[i]=cntx[a[i].x]-d[i]-1; 86 r[i]=cnty[a[i].y]-l[i]-1; 87 } 88 for(int i=1;i<=mx;i++) 89 { 90 sumx[i]=sumx[i-1]+cntx[i]; 91 sumy[i]=sumy[i-1]+cnty[i]; 92 } 93 for(int i=1;i<=n;i++) 94 { 95 int x=a[i].x,y=a[i].y; 96 sx[i][0]=sumx[x-1]; 97 sx[i][1]=sumx[mx]-sumx[x]; 98 sy[i][0]=sumy[y-1]; 99 sy[i][1]=sumy[mx]-sumy[y]; 100 } 101 // for(int i=1;i<=n;i++) 102 // { 103 // printf("%d sx0 %d sx1 %d sy0 %d sy1 %d d %d u %d l %d r %d\n",i,sx[i][0],sx[i][1],sy[i][0],sy[i][1],d[i],u[i],l[i],r[i]); 104 // } 105 for(int i=1;i<=n;i++) 106 { 107 int x=a[i].x,y=a[i].y; 108 int BL=getsum(a[i].y-1)-d[i]; 109 int TL=sx[i][0]-BL-l[i]; 110 int TR=sy[i][1]-TL-u[i]; 111 int BR=sy[i][0]-BL-d[i]; 112 add(y); 113 if(TR+BL<a1[x]) a1[x]=TR+BL,a2[x]=TL+BR; 114 else if(TR+BL==a1[x]) a2[x]=maxx(a2[x],TL+BR); 115 // printf("%d BL = %d BR = %d TR = %d TL = %d\n",i,BL,BR,TR,TL); 116 } 117 int ans=0,nl=0;; 118 for(int i=1;i<=mx;i++) 119 { 120 if(a1[i]<INF) ans=maxx(ans,a1[i]); 121 } 122 printf("Stan: %d; Ollie:",ans); 123 memset(num,0,sizeof(num)); 124 for(int i=0;i<=n;i++) 125 if(a1[i]==ans) num[a2[i]]=1; 126 for(int i=0;i<=n;i++) 127 if(num[i]) printf(" %d",i); 128 printf(";\n"); 129 } 130 return 0; 131 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/KonjakJuruo/p/6040504.html

總結(jié)

以上是生活随笔為你收集整理的【poj2464】树状数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。