数据结构(树链剖分,堆):HNOI 2016 network

2215. [HNOI2016]网络

★★★☆   输入文件:network_tenderRun.in   输出文件:network_tenderRun.out   简单对比
时间限制:2 s   内存限制:128 MB

【题目描述】

【输入格式】

【输出格式】

【样例输入1】

13 23

1 2

1 3

2 4

2 5

3 6

3 7

4 8

4 9

6 10

6 11

7 12

7 13

2 1

0 8 13 3

0 9 12 5

2 9

2 8

2 2

0 10 12 1

2 2

1 3

2 7

2 1

0 9 5 6

2 4

2 5

1 7

0 9 12 4

0 10 5 7

2 1

2 4

2 12

1 2

2 5

2 3

【样例输出1】

-1

3

5

-1

1

-1

1

1

3

6

7

7

4

6

【提示】

  这道题是水题。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 using namespace std;
  7 const int maxn=300010;
  8 int n,Q,cnt,fir[maxn],nxt[maxn<<1],to[maxn<<1];
  9 void addedge(int a,int b){
 10     nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
 11 }
 12 
 13 struct Data{
 14     int ID,val;
 15     Data(int id=0,int V=0){
 16         ID=id;val=V;
 17     }
 18     bool operator <(const Data &a)const{
 19         return val<a.val;
 20     } 
 21 };
 22 
 23 priority_queue<Data>Mx[maxn<<2];
 24 
 25 int dep[maxn],fa[maxn],sz[maxn],son[maxn];
 26 bool del[maxn];
 27 
 28 void DFS(int x){
 29     sz[x]=1;
 30     for(int i=fir[x];i;i=nxt[i])
 31         if(to[i]!=fa[x]){
 32             fa[to[i]]=x;
 33             dep[to[i]]=dep[x]+1;
 34             DFS(to[i]);
 35             sz[x]+=sz[to[i]];
 36             if(sz[son[x]]<sz[to[i]])
 37                 son[x]=to[i];
 38         }
 39 }
 40 
 41 int tot,ID[maxn],top[maxn];
 42 
 43 void DFS(int x,int tp){
 44     ID[x]=++tot;top[x]=tp;
 45     if(son[x])DFS(son[x],tp);
 46     for(int i=fir[x];i;i=nxt[i])
 47         if(to[i]!=fa[x]&&to[i]!=son[x])
 48             DFS(to[i],to[i]);
 49 }
 50 
 51 void Build(int x,int l,int r){
 52     Mx[x].push(Data(0,-1));
 53     if(l==r)return;
 54     int mid=(l+r)>>1;
 55     Build(x<<1,l,mid);
 56     Build(x<<1|1,mid+1,r);
 57 }
 58 
 59 int Query(int x,int l,int r,int g){
 60     while(del[Mx[x].top().ID])
 61         Mx[x].pop();
 62     if(l==r)
 63         return Mx[x].top().val;    
 64     int mid=(l+r)>>1;
 65     if(mid>=g)return max(Mx[x].top().val,Query(x<<1,l,mid,g));
 66     else return max(Mx[x].top().val,Query(x<<1|1,mid+1,r,g));
 67 }
 68 
 69 struct Node{
 70     int l,r;
 71     Node(int L=0,int R=0){
 72         l=L;r=R;
 73     }
 74     bool operator <(const Node &a)const{
 75         return l<a.l;
 76     }
 77 }st[maxn];
 78 
 79 void Update(int x,int l,int r,int a,int b,int id,int val){
 80     if(l>=a&&r<=b){
 81         Mx[x].push(Data(id,val));
 82         return;
 83     }
 84     int mid=(l+r)>>1;
 85     if(mid>=a)Update(x<<1,l,mid,a,b,id,val);
 86     if(mid<b)Update(x<<1|1,mid+1,r,a,b,id,val);
 87     return;
 88 }
 89 
 90 void Solve(int x,int y,int id,int val){
 91     int tp=0;
 92     while(top[x]!=top[y]){
 93         if(dep[top[x]]<dep[top[y]])
 94             swap(x,y);
 95             
 96         st[++tp]=Node(ID[top[x]],ID[x]);
 97         x=fa[top[x]];    
 98     }
 99     
100     if(dep[x]<dep[y])swap(x,y);
101     st[++tp]=Node(ID[y],ID[x]);
102     
103     sort(st+1,st+tp+1);
104     
105     int L=1;
106     for(int i=1;i<=tp;i++){
107         if(L<=st[i].l-1)
108             Update(1,1,n,L,st[i].l-1,id,val);
109         L=st[i].r+1;    
110     }
111     
112     if(L<=n)
113         Update(1,1,n,L,n,id,val);
114     
115     return;    
116 }
117 
118 int main(){
119 #ifndef ONLINE_JUDGE
120     freopen("network_tenderRun.in","r",stdin);
121     freopen("network_tenderRun.out","w",stdout);
122 #endif
123     scanf("%d%d",&n,&Q);
124     for(int i=1,a,b;i<n;i++){
125         scanf("%d%d",&a,&b);
126         addedge(a,b);
127         addedge(b,a);
128     }
129         
130     DFS(1);
131     DFS(1,1);
132     Build(1,1,n);
133         
134     for(int t=1,type,a,b,v;t<=Q;t++){
135         scanf("%d",&type);
136         if(type==0){
137             scanf("%d%d%d",&a,&b,&v);
138             Solve(a,b,t,v);
139         }
140         else if(type==1){
141             scanf("%d",&a);
142             del[a]=true;
143         }
144         else if(type==2){
145             scanf("%d",&a);
146             printf("%d
",Query(1,1,n,ID[a]));
147         }
148     }
149     return 0;
150 }

  5月20日BZOJ加了一组数据,上面的程序MLE了,只能使用手写栈。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 using namespace std;
  7 const int maxn=100010;
  8 int n,Q,cnt,fir[maxn],nxt[maxn<<1],to[maxn<<1];
  9 void addedge(int a,int b){
 10     nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
 11 }
 12 priority_queue<int>Mx[maxn<<2],del[maxn<<2];
 13 
 14 int dep[maxn],fa[maxn],sz[maxn],son[maxn],vis[maxn];
 15 int ID[maxn],top[maxn],tot,U[maxn<<1],V[maxn<<1],val[maxn<<1];
 16 int stack[maxn],head;
 17   
 18 void DFS(int x){
 19     stack[++head]=x;
 20     while(head){
 21         x=stack[head];
 22         if(vis[x]){
 23             if(fa[x]){
 24                 sz[fa[x]]+=sz[x];
 25                 if(sz[son[fa[x]]]<sz[x])
 26                     son[fa[x]]=x;
 27             }
 28             head--;
 29             continue;
 30         }
 31         vis[x]=true;sz[x]=1;
 32         for(int i=fir[x];i;i=nxt[i])
 33             if(to[i]!=fa[x]){
 34                 fa[to[i]]=x;
 35                 dep[to[i]]=dep[x]+1;
 36                 stack[++head]=to[i];
 37             }
 38     }
 39 }
 40   
 41 void DFS(int x,int tp){
 42     top[x]=tp;
 43     stack[++head]=x;
 44     while(head){
 45         x=stack[head];
 46         if(vis[x]){
 47             head--;
 48             continue;
 49         }
 50         vis[x]=true;
 51         ID[x]=++tot;
 52         for(int i=fir[x];i;i=nxt[i])
 53             if(to[i]!=fa[x]&&to[i]!=son[x]){
 54                 stack[++head]=to[i];
 55                 top[to[i]]=to[i];
 56             }
 57         if(son[x]){
 58             stack[++head]=son[x];
 59             top[son[x]]=top[x];
 60         }    
 61     }
 62 }
 63 
 64 int Query(int x,int l,int r,int g){
 65     while(!del[x].empty()&&del[x].top()==Mx[x].top())del[x].pop(),Mx[x].pop();
 66     if(l==r)
 67         return Mx[x].empty()?-1:Mx[x].top();    
 68     int mid=(l+r)>>1,ret=Mx[x].empty()?-1:Mx[x].top();
 69     if(mid>=g)return max(ret,Query(x<<1,l,mid,g));
 70     else return max(ret,Query(x<<1|1,mid+1,r,g));
 71 }
 72 
 73 struct Node{
 74     int l,r;
 75     Node(int L=0,int R=0){
 76         l=L;r=R;
 77     }
 78     bool operator <(const Node &a)const{
 79         return l<a.l;
 80     }
 81 }st[maxn<<2];
 82 
 83 void Update(int x,int l,int r,int a,int b,int val,int on){
 84     if(l>=a&&r<=b){
 85         if(on)
 86             Mx[x].push(val);
 87         else
 88             del[x].push(val);
 89         return;
 90     }
 91     int mid=(l+r)>>1;
 92     if(mid>=a)Update(x<<1,l,mid,a,b,val,on);
 93     if(mid<b)Update(x<<1|1,mid+1,r,a,b,val,on);
 94     return;
 95 }
 96 
 97 void Solve(int x,int y,int val,int on){
 98     int tp=0;
 99     while(top[x]!=top[y]){
100         if(dep[top[x]]<dep[top[y]])
101             swap(x,y);
102             
103         st[++tp]=Node(ID[top[x]],ID[x]);
104         x=fa[top[x]];    
105     }
106     
107     if(dep[x]<dep[y])swap(x,y);
108     st[++tp]=Node(ID[y],ID[x]);
109     
110     sort(st+1,st+tp+1);
111     
112     int L=1;
113     for(int i=1;i<=tp;i++){
114         if(L<=st[i].l-1)
115             Update(1,1,n,L,st[i].l-1,val,on);
116         L=st[i].r+1;    
117     }
118     
119     if(L<=n)
120         Update(1,1,n,L,n,val,on);
121     
122     return;    
123 }
124 
125 int main(){
126 #ifndef ONLINE_JUDGE
127     //freopen("network_tenderRun.in","r",stdin);
128     //freopen("network_tenderRun.out","w",stdout);
129 #endif
130     scanf("%d%d",&n,&Q);
131     for(int i=1,a,b;i<n;i++){
132         scanf("%d%d",&a,&b);
133         addedge(a,b);
134         addedge(b,a);
135     }
136         
137     DFS(1);
138     memset(vis,0,sizeof(vis));
139     DFS(1,1);
140         
141     for(int t=1,type,a;t<=Q;t++){
142         scanf("%d",&type);
143         if(type==0){
144             scanf("%d%d%d",&U[t],&V[t],&val[t]);
145             Solve(U[t],V[t],val[t],1);
146         }
147         else if(type==1){
148             scanf("%d",&a);
149             Solve(U[a],V[a],val[a],0);
150         }
151         else if(type==2){
152             scanf("%d",&a);
153             printf("%d
",Query(1,1,n,ID[a]));
154         }
155     }
156     return 0;
157 }

如下:

尽最大的努力,做最好的自己!
原文地址:https://www.cnblogs.com/TenderRun/p/5467763.html