hdu5107 线段树

hdu 5107 这题说的是给了一个二维的平面，平面内有30000个点每个点都有自己的高度，然后又30000次的查询，每次查询给的是(X,Y,K), 要求出set(x,y){x,y|x<=X&&y<=Y } 的所有点，中第K 大的数是多少，存在输出该高度，允许重复；否者输出-1，。

本来想用主席树做，发现，找前节点还是比较麻烦的。再加上k<=10 还是比较小的，然后我们按照y设置为线段树的页节点，然后发现每个页节点最多存10种高度，然后他们的父节点只需要合并孩子的两个长度为10的高度数组，我们将所有的点包括询问的点进行离散化，按x按y从小到大排序，离散化后查询在数组中，保证了x一定小于等于当前要插入或者是查询的点，这样就可以减少对于x的处理，然后接下来就是让该点的y找到相应的叶节点，然后用该建筑物的h更新叶节点。如果是查询就查寻（1，IDX（P[i].y））

#include <algorithm>

#include <cstdio>

#include <string.h>

#include <vector>

using namespace std;

const int maxn=;

typedef int ll;

struct point{

    ll x,h[];

}AN;

struct build{

    ll x,y,h;

    ll id,op;

    bool operator < ( const build A ) const {

         return x<A.x||(x==A.x&&y<A.y)||(x==A.x&&y==A.y&&op<A.op)||(x==A.x&&y==A.y&&op==A.op&&id<A.id);

    }

}P[maxn*];

ll Y[maxn*];

ll ans[maxn];

ll Va,loc,cL,cR,tim;

struct Itree{

   point V[maxn**];

   void build(int o,int L, int R){

        V[o].x=;

        if(L==R) return ;

        int mid =(L+R)/;

        build(o*, L, mid );

        build(o*+, mid+, R);

   }

   void inser(int o ){

       int i=;

       for( i=; i<V[o].x; i++){

         if(Va<V[o].h[i]) break;

       }

       if(i==) return;

       for(int j = V[o].x; j>i; --j)

         V[o].h[j]=V[o].h[j-];

       V[o].h[i]=Va;

       V[o].x=min(V[o].x+,);

   }

   point maintain( point o1, point o2){

      point ans;

       int i,j,k;

       i=j=k=;

       while( (i<o1.x||j<o2.x )&&( k<) ){

             if(j>=o2.x ||( i<o1.x && o1.h[i]<o2.h[j]  ) )

                  ans.h[k++] = o1.h[i++];

             else ans.h[k++] = o2.h[j++];

       }

       ans.x=k;

       return ans;

   }

   void update(int o, int L, int R){

        if(L==R){

          inser(o); return ;

        }

        int mid = (L+R)>>;

        if(loc<=mid) update(o*,L, mid);

        else update(o*+,mid+,R);

        V[o]=maintain(V[o*], V[o*+]);

   }

   void query(int o, int L, int R){

         if(cL<=L && R<= cR){

            if(tim==){

                 tim=;

                 AN=V[o];

            }else {

                AN=maintain(AN,V[o]);

            }

            return ;

         }

         int mid = (L+R)>>;

         if(cL<=mid) query(o*,L,mid);

         if(cR>mid) query(o*+, mid+, R);

   }

}T;

int main()

{

   int n,m;

   while(scanf("%d%d",&n,&m)==){

        for(int i=; i<n; ++i){

            scanf("%d%d%d",&P[i].x,&P[i].y,&P[i].h);

             P[i].id=i;

            P[i].op=;

            Y[i]=P[i].y;

        }

        for(int i=; i<m; ++i){

             scanf("%d%d%d",&P[i+n].x,&P[i+n].y,&P[i+n].h);

             P[i+n].id=n+i;

             P[i+n].op=;

             Y[i+n]=P[i+n].y;

        }

        sort(Y,Y+n+m);

        int Ynum = unique(Y,Y+n+m)-Y;

        T.build(,,Ynum);

        sort(P,P+n+m);

        for(int i=; i<n+m; ++i){

             if(P[i].op==){

                 loc = lower_bound(Y,Y+Ynum,P[i].y)-Y+;

                  Va= P[i].h;

                  T.update(, , Ynum);

             }else{

                 tim=;

                 cR = lower_bound(Y,Y+Ynum,P[i].y)-Y+;

                 cL=;

                 T.query(,,Ynum);

                 if(AN.x>=P[i].h){

                     ans[P[i].id-n]=AN.h[ P[i].h- ];

                 } else{

                     ans[P[i].id-n]=-;

                 }

             }

        }

        for(int i=; i<m; ++i)

             printf("%d\n",ans[i]);

   }

   return ;

}

巴特西

hdu5107 线段树

最新文章

热门文章