BZOJ1803: Spoj1487 Query on a tree III-白红宇的个人博客

发布日期：2021-05-06 03:47:17 浏览次数：24 分类：技术文章

本文共 2215 字，大约阅读时间需要 7 分钟。

裸的主席树+DFS序

然后我差错查了好长时间发现时查询的时候k没有减应该到右子树结果到了左子树。。。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         using namespace std; char c;inline void read(int&a){ a=0;do c=getchar();while(c<'0'||c>'9'); while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();} int Begin[200001],End[200001];int l[200001];int Sort[200001];int con;set 
          
           are;map
           
            mp;struct Chain { Chain *next; int other;Chain(){next=NULL; }}*Head[200001];struct Sege{ int sum; Sege *lc,*rc;}*Tree[200001];Sege a[2000001];Sege *Stack[2000001];int top;inline void begin(){ for(top=0;top<=2000000;top++) Stack[top]=&a[top];top--;}inline Sege*New(){ return Stack[top--];} Sege *build(int l,int r){ if(l^r) { int mid=(l+r)>>1; Sege *tp=New(); tp->sum=0; tp->lc=build(l,mid);tp->rc=build(mid+1,r); return tp; } Sege *tp=New(); tp->sum=0; tp->lc=tp->rc=NULL; return tp;} int Q,x,y;Sege *Add(Sege *last,int l,int r,int data){ if(l^r) { int mid=(l+r)>>1; Sege *tp=New(); *tp=*last; if(Sort[mid]>=data) tp->lc=Add(last->lc,l,mid,data); else tp->rc=Add(last->rc,mid+1,r,data); tp->sum++; return tp; } Sege *tp=New(); *tp=*last; tp->sum++; return tp;} int Query(Sege *L,Sege *R,int k,int l,int r){ if(l^r) { if(R->lc->sum-L->lc->sum>=k) return Query(L->lc,R->lc,k,l,(l+r)>>1); else return Query(L->rc,R->rc,k-R->lc->sum+L->lc->sum,((l+r)>>1)+1,r); } return Sort[l];}int cnt;void BTree(int v){ Begin[v]=++cnt; Tree[cnt]=Add(Tree[cnt-1],1,con,l[v]); for(Chain *tp=Head[v];tp;tp=tp->next) if(!Begin[tp->other]) BTree(tp->other); End[v]=cnt;} inline void addside(int a,int b){ Chain *tp=new Chain; tp->next=Head[a]; tp->other=b; Head[a]=tp;}int main(){ int n; freopen("std.in","r",stdin); freopen("self.out","w",stdout); read(n);begin(); are.clear(); mp.clear(); for(int i=1;i<=n;i++) read(l[i]),are.insert(l[i]),mp[l[i]]=i; set
            
             ::iterator tp=are.end(); /*tp--; for(tp;tp!=are.begin();tp--) Sort[++con]=*tp; Sort[++con]=*tp; */ for(tp=are.begin();tp!=are.end();tp++) Sort[++con]=*tp; Tree[0]=build(1,con); for(int i=2;i<=n;i++) { int a,b; read(a),read(b);addside(a,b);addside(b,a); } BTree(1); read(Q); while(Q--) { read(x),read(y); printf("%d\n",mp[Query(Tree[Begin[x]-1],Tree[End[x]],y,1,con)]); }}

上一篇：莫比乌斯反演

下一篇：12.22.2015

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章