bzoj3307 雨天的尾巴 线段树合并

bzoj3307 雨天的尾巴 线段树合并

​​ Description N个点，形成一个树状结构。有M次发放，每次选择两个点x,y 对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成 所有发放后，每个点存放最多的是哪种物品。

Input 第一行数字N，M 接下来N-1行，每行两个数字a,b,表示a与b间有一条边 再接下来M行，每行三个数字x,y,z.如题

Output 输出有N行 每i行的数字表示第i个点存放最多的物品是哪一种，如果有 多种物品的数量一样，输出编号最小的。如果某个点没有物品 则输出0

Sample Input 20 50 8 6 10 6 18 6 20 10 7 20 2 18 19 8 1 6 14 20 16 10 13 19 3 14 17 18 11 19 4 11 15 14 5 18 9 10 12 15 11 14 87 12 1 87 14 3 84 17 2 36 6 5 93 17 6 87 10 14 93 5 16 78 6 15 93 15 5 16 11 8 50 17 19 50 5 4 87 15 20 78 1 17 50 20 13 87 7 15 22 16 11 94 19 8 87 18 3 93 13 13 87 2 1 87 2 6 22 5 20 84 10 12 93 18 12 87 16 10 93 8 17 93 14 7 36 7 4 22 5 9 87 13 10 16 20 11 50 9 16 84 10 17 16 19 6 87 12 2 36 20 9 94 9 2 84 14 1 94 5 5 94 8 17 16 12 8 36 20 17 78 12 18 50 16 8 94 2 19 36 10 18 36 14 19 50 4 12 50 Sample Output 87 36 84 22 87 87 22 50 84 87 50 36 87 93 36 94 16 87 50 50 1<=N,M<=100000 1<=a,b,x,y<=N 1<=z<=10^9

HINT

Source 直接考虑差分一下即可 即每个点储存1到这个点的所有信息 如x,y需要改那么则在x上+1 y上+1

lca-1 fa[lca]-1即可 然后最后合并的时候从底向上合并即可 这个差分可以看做 这个点到跟的路径分别被差分了一下

线段树合并一个log竟然如此慢

另外内存不太会算qwq总觉得应该是120*N

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;struct node{ int y,next;}data[N<<1];int n,h[N],dep[N],Log[N],fa[N][20],rt[N],ans[N],num,m;inline void dfs(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa[x][0]) continue;dep[y]=dep[x]+1;fa[y][0]=x; for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1]; dfs(y); }}inline int lca(int x,int y){ if (dep[x]=tree[r].mx?tree[l].id:tree[r].id;}inline void insert1(int &x,int l,int r,int p,int v){ if (!x) x=++num;int mid=l+r>>1; if (l==r) {tree[x].mx+=v;tree[x].id=l;return;} if(p<=mid) insert1(tree[x].left,l,mid,p,v); else insert1(tree[x].right,mid+1,r,p,v);update(x);}inline int merge(int rt1,int rt2,int l,int r){ if (!rt1||!rt2) return rt1+rt2; if(l==r) {tree[rt1].mx+=tree[rt2].mx;return rt1;}int mid=l+r>>1; tree[rt1].left=merge(tree[rt1].left,tree[rt2].left,l,mid); tree[rt1].right=merge(tree[rt1].right,tree[rt2].right,mid+1,r);update(rt1);return rt1;}const int nn=1e9;inline void print(int x,int l,int r){ int mid=l+r>>1; if (tree[x].left) print(tree[x].left,l,mid); printf("%d %d %d %d\n",l,r,tree[x].mx,tree[x].id); if (tree[x].right) print(tree[x].right,mid+1,r);}inline void dfs1(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa[x][0]) continue; dfs1(y); rt[x]=merge(rt[x],rt[y],1,nn); //printf("%d\n",x);puts("-----");print(rt[x],1,nn); }ans[x]=tree[rt[x]].id;}int main(){ freopen("bzoj3307.in","r",stdin); n=read();for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1;m=read(); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。