正文 

当前位置： 首页 > 程序 > java教程

p4556[vani有约会]雨天的尾巴（线段树合并）(代码片段)

bztminamoto bztminamoto     2023-01-26     493

关键词：

传送门

一道线段树合并
首先不难看出树上差分
我们把每一次修改拆成四个，在(u,v)分别放上一个，在(lca)和(fa[lca])各减去一个，那么只要统计一下子树里的总数即可
然而问题就在于怎么统计。直接暴力肯定是要咕咕的，那么线段树合并就派上用场了
总之就是每个点开一个动态开点线段树，然后一遍dfs，让它的所有儿子的线段树合并到它这里
我按以前的写法不知为什么写挂了……然后换抄了种写法还是挂……后来发现是写抄的时候没有注意合并的顺序……

//minamoto
#include<bits/stdc++.h>
#define IT vector<node>::iterator
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read()
    int res,f=1;char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;

char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot()fwrite(sr,1,C+1,stdout),C=-1;
void print(int x)
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='
';

const int N=1e5+5;
struct node
    int c,cnt;
//  inline bool operator <(node b)return cnt==b.cnt?c>b.c:cnt<b.cnt;
    friend bool operator <(node a,node b)return a.cnt==b.cnt?a.c>b.c:a.cnt<b.cnt;
    inline node operator +(node b)return c,cnt+b.cnt;
;vector<node>v[N];
struct egint v,nx;e[N<<1];int head[N],tot;
inline void add(int u,int v)e[++tot]=v,head[u],head[u]=tot;
int rt[N],fa[N],dfn[N],top[N],sz[N],son[N],dep[N],ans[N],n,m,u,vva,c;
void dfs1(int u)
    sz[u]=1,dep[u]=dep[fa[u]]+1;
    go(u)if(v!=fa[u])
        fa[v]=u,dfs1(v),sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    

void dfs2(int u,int t)
    top[u]=t;if(!son[u])return;dfs2(son[u],t);
    go(u)if(v!=fa[u]&&v!=son[u])dfs2(v,v);

inline int LCA(int u,int v)
    while(top[u]!=top[v])
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    return dep[u]<dep[v]?u:v;

namespace LOLI
    int L[N<<5],R[N<<5],tot;node v[N<<5];
    inline void init()fp(i,1,n)rt[i]=++tot;
    void ins(int p,int l,int r,node val)
        if(l==r)return (void)(v[p]=val+v[p]);int mid=(l+r)>>1;
        if(val.c<=mid)ins(L[p]=L[p]?L[p]:++tot,l,mid,val);
        else ins(R[p]=R[p]?R[p]:++tot,mid+1,r,val);v[p]=max(v[L[p]],v[R[p]]);
    
    void merge(int x,int y,int l,int r)
//      printf("%d %d %d %d
",x,y,l,r);
        if(l==r)return (void)(v[x]=v[x]+v[y]);int mid=(l+r)>>1;
        if(L[x]&&L[y])merge(L[x],L[y],l,mid);else if(L[y])L[x]=L[y];
        if(R[x]&&R[y])merge(R[x],R[y],mid+1,r);else if(R[y])R[x]=R[y];
        v[x]=max(v[L[x]],v[R[x]]);
    

void dfs(int u)
//  printf("%d
",u);
    go(u)if(v!=fa[u])dfs(v),LOLI::merge(rt[u],rt[v],1,1e5);
    for(IT it=v[u].begin();it!=v[u].end();++it)LOLI::ins(rt[u],1,1e5,*it);
    ans[u]=LOLI::v[rt[u]].c;

int main()
//  freopen("testdata.in","r",stdin);
    n=read(),m=read(),LOLI::init();
    fp(i,1,n-1)u=read(),vva=read(),add(u,vva),add(vva,u);
    dfs1(1),dfs2(1,1);
    fp(i,1,m)
        u=read(),vva=read(),c=read();int lca=LCA(u,vva);
        v[u].push_back(nodec,1),v[vva].push_back(nodec,1);
        v[lca].push_back(nodec,-1),v[fa[lca]].push_back(nodec,-1);
    dfs(1);fp(i,1,n)print(ans[i]);return Ot(),0;

p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)

传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情

p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)

传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情

p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)

传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情

[vani有约会]雨天的尾巴(代码片段)

我之前考试是遇到过这题，但是数据范围k<=20，状压就能过。结果原题范围k<=100000……果断线段树合并。普及线段树合并：比如两个相同大小的线段树,将b树各个区间上的值合并到a树上，从树根开始合并，然后递归合并左右... 查看详情

bzoj3307雨天的尾巴线段树合并

​​http://www.elijahqi.win/archives/3463​​​DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。Input第一行数字N，... 查看详情

bzoj3307雨天的尾巴（可持久化线段树合并）(代码片段)

题目大意：一颗树，想要在树链上添加同一物品，问最后每个点上哪个物品最多。解题思路：假如说物品数量少到可以暴力添加，且树点极少，我们怎么做。首先在一个树节点上标记出哪些物品有多少，寻找道路上的节点暴力添... 查看详情

luogu4556雨天的尾巴树上差分线段树合并(代码片段)

传送门 一个套路题……树上差分+线段树合并即可注意一个细节：$pushup$的时候如果最大值为$0$一定要把最大值对应的答案也设为$0$，否则会$WA$第二个点另外如果这道题空限变小了请不要交这份代码，因为这份代码没有卡空... 查看详情

luogu4556雨天的尾巴(线段树合并+差分)(代码片段)

题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮... 查看详情

bzoj3307雨天的尾巴

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3307【题解】这什么垃圾题啊卡空间卡时间卡栈然后我会了一种新姿势：人工栈（好像也不难啊喂）我们发现对于每种物品，只需要在u这地方的权值线段树上+1，v的权值线段树上+1，LC... 查看详情

bzoj3307雨天的尾巴

题目链接：传送门题目大意：中文题，略题目思路：网上有题解说是合并线段树的，但是太难蒟蒻不会，只能用树剖求解　　　　　如果不是树而是一维数组我们会怎么解？   　　　　　当然是利用前缀和思想标记（... 查看详情

bzoj-3307:雨天的尾巴

咱可以差分一下，把$u-v$这条路径上的$z$都加$1$变成$u$和$v$的$z$加$1$，$lca$和$fa_{lca}$的$z$减$1$。用线段树实现最大值的查询，最后$dfs$自底向上一路合并并查询即可。先开始线段树数组开小了，$RE$了一次。1#include<cassert>2#inclu... 查看详情

雨天的尾巴(代码片段)

考试的时候直接扎第一题上了这到题连暴力都没打出来T_T;心路历程：当时想到了离散化（很慌没打出来。。。），树上差分，lca倍增，当时觉滴倍增很难打，一看n<100000,于是选择用向上标记法，然而少了一行代码，，，，爆... 查看详情

例题线段树合并(代码片段)

雨天的尾巴这道题应该算是很板子了，不过需要稍微思考一下，对于每次发放，如果模拟发放过程，那么每次发放的时间复杂度是(O(n))的，这样显然会T，考虑如果每次只发放一种，用树上差分解决就可以，但是这个有很多种，... 查看详情

[luogu4556]雨天的尾巴(代码片段)

[luogu4556]雨天的尾巴luogu发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并但是...如果你只有35分...https://www.luogu.org/discuss/show/88259#include<bits/stdc++.h>usingnamespacestd;constint_=1e5+5;intre()intx=0,w=1;charch=get 查看详情

bzoj3307:雨天的尾巴(代码片段)

传送门树上差分+线段树合并+离散化对于修改的路径，树上差分就好了代码：#include<cstdio>#include<iostream>#include<cstring>#include<tr1/unordered_map>#include<algorithm>usingnamespacestd;voidread(int&x) 查看详情

线段树合并(代码片段)

3307:雨天的尾巴模板题。简单题调不过最好的方法是重构代码或者放一天然后重构代码。1//Achen2#include<algorithm>3#include<iostream>4#include<cstring>5#include<cstdlib>6#include<vector>7#include<cstdio>8#inc 查看详情

hdu4553约会安排(区间合并)线段树(代码片段)

<题目链接>　　寒假来了，又到了小明和女神们约会的季节。 　　小明虽为屌丝级码农，但非常活跃，女神们常常在小明网上的大段发言后热情回复“呵呵”，所以，小明的最爱就是和女神们约会。与此同时，也有很多... 查看详情

hdu4553约会安排（线段树区间合并+双重标记）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4553题目大意：就是有三种操作：　　　　　①DS x，安排一段长度为x的空闲时间跟屌丝一起，输出这段时间的起点，若没有则输出“flywithyourself”。　　　　　②NS x，安... 查看详情