poj 2464 线段树统计区间..两棵树

仔细分析的话，不用说了，我只是尽自己的力量去写一个尽量好看的代码。。。

思路说一下：

就是先统计这个点的上区间有多少点，下区间有多少点，然后x排序再求上下区间，这个时候便可以得知已经更新进去的点一定在该点的左下方、左上方、下方。。。

由此统计出每个点被作为标准点画出，每个人的得分情况。。

View Code

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<algorithm>
  5 #include<string.h>
  6 using namespace std;
  7 using std::sort;
  8 using std::unique;
  9 const int N = 200022;
 10 const int INF = 0x7fffffff;
 11 struct point
 12 {
 13     int x,y,k;
 14 }P[N];
 15 int lt[N],lb[N],rt[N],rb[N],Ollie[N];
 16 int Up[N],Down[N];
 17 int X[N];
 18 int sum[N<<2];
 19 bool cmp1(point a,point b)
 20 {
 21      if(a.y==b.y)
 22      return a.x<b.x;
 23      return a.y<b.y;
 24 }
 25 bool cmp2(point a,point b)
 26 {
 27     if(a.x==b.x)
 28     return a.y<b.y;
 29     return a.x<b.x;
 30 }
 31 void update(int t,int l,int r,int i)
 32 {
 33      sum[t]++;
 34      if(l==r)return ;
 35      int m=(l+r)>>1;
 36      if(i<=m)update(t<<1,l,m,i);
 37      else update(t<<1|1,m+1,r,i);
 38 }
 39 int query(int t,int l,int r,int L,int R)
 40 {
 41      if(L>R)return 0;
 42      if(L<=l&&r<=R)return sum[t];
 43      int m=(l+r)>>1;
 44      int ans=0;
 45      if(L<=m)ans+=query(t<<1,l,m,L,R);
 46      if(R>m)ans+=query(t<<1|1,m+1,r,L,R);
 47      return ans;
 48 }
 49 int Max(int a,int b)
 50 {
 51     return a>b?a:b;
 52 }
 53 int main()
 54 {
 55     int n;
 56     while(~scanf("%d",&n)&&n)
 57     {
 58         for(int i=1;i<=n;i++)
 59         {
 60             scanf("%d%d",&P[i].x,&P[i].y);
 61             P[i].k=i;
 62         }
 63         sort(P+1,P+n+1,cmp1);
 64         int topy=0;
 65         for(int i=1;i<=n;i++)
 66         {
 67             if(i==n){P[i].y=topy;break;}
 68             if(P[i].y==P[i+1].y)P[i].y=topy;
 69             else P[i].y=topy++;
 70         }
 71         memset(sum,0,sizeof(sum));
 72         for(int i=1;i<=n;i++)update(1,0,topy,P[i].y);
 73         for(int i=1;i<=n;i++)
 74         {
 75             Up[P[i].k]=query(1,0,topy,P[i].y+1,topy);
 76             Down[P[i].k]=query(1,0,topy,0,P[i].y-1);
 77         }
 78         sort(P+1,P+n+1,cmp2);
 79         int topx=0;
 80         for(int i=1;i<=n;i++)
 81         {
 82             if(i==n){P[i].x=topx;break;}
 83             if(P[i].x==P[i+1].x)P[i].x=topx;
 84             else P[i].x=topx++;
 85         }
 86         memset(sum,0,sizeof(sum));
 87         int Stan=0,top=0;
 88         for(int i=0;i<=topx;i++)X[i]=INF;
 89         for(int i=1;i<=n;i++)
 90         {
 91             lt[i]=query(1,0,topy,P[i].y+1,topy);
 92             lb[i]=query(1,0,topy,0,P[i].y-1);
 93             rb[i]=Down[P[i].k]-lb[i];
 94             for(int j=i-1;j>=1&&P[i].x==P[j].x;j--)lb[i]--;
 95             rt[i]=Up[P[i].k]-lt[i];
 96             for(int j=i+1;j<=n&&P[i].x==P[j].x;j++)rt[i]--;
 97             if(lb[i]+rt[i]<X[P[i].x])
 98             {
 99                 X[P[i].x]=lb[i]+rt[i];
100             }
101             update(1,0,topy,P[i].y);
102         }
103         for(int i=0;i<=topx;i++)Stan=Max(Stan,X[i]);
104         for(int i=1;i<=n;i++)
105         {
106             if(Stan==X[P[i].x])
107             Ollie[top++]=lt[i]+rb[i];
108         }
109         sort(Ollie,Ollie+top);
110         top=unique(Ollie,Ollie+top)-Ollie;
111         printf("Stan: %d; Ollie:",Stan);
112         for(int i=0;i<top;i++)printf(" %d",Ollie[i]);
113         printf(";\n");
114     }
115     return 0;
116 }