首页 > 代码库 > Hdu 5029 Relief grain(熟练剖分)
Hdu 5029 Relief grain(熟练剖分)
题目大意:
给出一棵树。
然后有m个操作,每个操作都在两点的路径上分配不同的粮食。
最后要求输出所有村庄有的最多的粮食的种类。
思路分析:
一眼就看得出来是树链剖分的题目。
现在的问题就是,每一次操作,如何维护每个点的最多的食物编号,以及最多的食物的数量。要记录这两个值是肯定的。
首先可以想到将所有的操作按照z排序。这样每一回合操作,称一回合为处理同一种颜色。一回合结束之后,后面的操作就不会影响前面取得的最大值。因为后面的操作的食物的种类不一样,是不可以再继续累加的。
然后可以发现一个规律,就是每处理完一种颜色之后,在线段树上,颜色比这种颜色编号大的颜色都存在了这个节点的树形结构的上面。也就是父亲节点甚至是父亲节点的父亲节点。
所以我们就直接考虑pushdown部分吧,这是这道题目的难点。
假设操作只有 2 3 4这三种食物。
我们首先先处理完了所有食物种类为2的所有操作。
现在在处理种类为3的操作。如果这个操作的指定区间的lazy标记的颜色也是3.那么就直接累加,毫无疑问。但是如果这个区间是2...由于我们现在还在处理3,你不确定后面还有多少种类为3的操作,所以我们就要将这个种类为2的lazy往下推(用递归的pushdown实现)。然后将3更新。
按照如上操作处理了3之后。
现在我们处理种类为4的。我们注意到之前说的规律。
2一定在3下面,那么4的下面也之后有3.
所以现在种类4的操作,碰到了4.那么也是直接累加无疑问。好,如果碰到操作三,按照我们上述的,要将3pushdown。但是,在pushdown3的过程中,这个3又会遇到lazy颜色为2的。产生冲突。但是我们注意到,如果是4将3推下去,而且3又碰到了2,也就以为着,这个子树只有一个节点的lazy是3了。为什么,还是那个规律。自己想一下就明白。
所以意思就是下面不会有三,那个节点的全部三就是所有操作的全部三。当递推下的3的数量比碰到的那个2的数量还要小,也就意味着以下的节点的答案不可能是3 的。
但是如果2比三小,可能这下面还有一些2没有累加,所以就把2递推下去,再递推3下去,再更新4.
好,现在我们分析时间复杂度。
首先m此操作。
然后查找熟练logn
线段树更新logn
那么这个pushdown的递归呢。
因为递归层数是不会超过logn的。
所以最多也就是 m*log^3...
当然最优解肯定不是这个。。。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <utility> #pragma comment(linker,"/STACk:10240000,10240000") #define maxn 100005 #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define mid ((s+e)>>1) using namespace std; int next[maxn<<1],to[maxn<<1],head[maxn],tot;//临界表 int pre[maxn],root[maxn],siz[maxn],son[maxn],w[maxn],dep[maxn],id;//原树的父亲 链上的根 siz 有最大siz的子树 重新分配的id 深度 getid中来计数的 pair<int,int>ans[maxn<<2];//线段树变量 pair<int,int>cov[maxn<<2]; int n,cur; void init() { pre[1]=0; dep[1]=0; tot=0;id=0; memset(head,0,sizeof head); } void addedge(int u,int v) { tot++; next[tot]=head[u]; to[tot]=v; head[u]=tot; } void dfs(int now)//to get size,son,dep,pre... { son[now]=0; siz[now]=1; for(int p =head[now]; p ; p=next[p]) { int t=to[p]; if(t!=pre[now]) { pre[t]=now; dep[t]=dep[now]+1; dfs(t); if(siz[t]>siz[son[now]])son[now]=t; siz[now]+=siz[t]; } } } void getid(int now,int rt)//to get w and root... { w[now]=++id; root[now]=rt; if(son[now])getid(son[now],rt); for(int p = head[now] ; p ; p=next[p]) { int t=to[p]; if(t!=son[now]&&t!=pre[now]) getid(t,t); } } void pushdown(int num,int s,int e) { if(s==e) { cov[num].first=cov[num].second=0; return; } if(cov[num].second) { if(cov[num<<1].second==cov[num].second) cov[num<<1].first+=cov[num].first; else { if(cov[num<<1].first<cov[num].first || cov[num].second==cur) { pushdown(lson); cov[num<<1]=cov[num]; } } if(s==mid) { if(cov[num<<1].first>ans[num<<1].first) ans[num<<1]=cov[num<<1]; } if(cov[num<<1|1].second==cov[num].second) cov[num<<1|1].first+=cov[num].first; else { if(cov[num<<1|1].first<cov[num].first || cov[num].second==cur) { pushdown(rson); cov[num<<1|1]=cov[num]; } } if(mid+1==e) { if(cov[num<<1|1].first>ans[num<<1|1].first) ans[num<<1|1]=cov[num<<1|1]; } cov[num].first=cov[num].second=0; } } void build(int num,int s,int e) { ans[num].first=ans[num].second=0; cov[num].first=0; cov[num].second=0; if(s==e)return; build(lson); build(rson); } void update(int num,int s,int e,int l,int r,int val) { if(l<=s && r>=e) { if(cov[num].second==val) cov[num].first++; else { pushdown(num,s,e); cov[num].first++; cov[num].second=val; } if(s==e){ if(cov[num].first>ans[num].first) ans[num]=cov[num]; } return; } pushdown(num,s,e); if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); } int query(int num,int s,int e,int pos) { if(s==e)return ans[num].second; pushdown(num,s,e); if(pos<=mid)return query(lson,pos); else return query(rson,pos); } void work(int x,int y,int val) { while(root[x]!=root[y]) { if(dep[root[x]]<dep[root[y]])swap(x,y); update(1,1,n,w[root[x]],w[x],val); x=pre[root[x]]; } if(dep[x]>dep[y])swap(x,y); update(1,1,n,w[x],w[y],val); } struct node { int x,y,z; bool operator < (const node &cmp)const{ return z<cmp.z; } }line[maxn]; int main() { int m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0)break; init(); for(int i=1;i<=n-1;i++) { int s,e; scanf("%d%d",&s,&e); addedge(s,e); addedge(e,s); } dfs(1); getid(1,1); build(1,1,n); for(int i=1;i<=m;i++) { scanf("%d%d%d",&line[i].x,&line[i].y,&line[i].z); } sort(line+1,line+1+m); for(int i=1;i<=m;i++){ int x,y,z; cur=line[i].z; work(line[i].x,line[i].y,line[i].z); } cur=-1; for(int i=1;i<=n;i++) { printf("%d\n",query(1,1,n,w[i])); } } return 0; } /* 2 4 1 2 1 1 1 1 2 2 2 2 2 2 2 1 5 3 1 2 3 1 3 4 5 3 2 3 3 1 5 2 3 3 3 5 4 1 2 2 3 3 4 4 5 1 5 1 1 3 2 1 2 2 1 1 3 5 5 1 2 2 3 3 4 4 5 1 1 1 1 2 1 1 3 2 1 5 2 1 3 2 5 5 1 2 2 3 3 4 4 5 1 2 1 1 2 1 1 3 2 1 1 2 1 1 2 5 10 1 2 2 3 3 4 4 5 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 2 1 1 3 1 1 3 1 1 3 1 1 3 0 0 */
Hdu 5029 Relief grain(熟练剖分)