2019牛客暑期多校训练营（第八场）I Inner World —— 线段树

本文主要是介绍2019牛客暑期多校训练营（第八场）I Inner World —— 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你n棵树，每个树一开始只有节点1，接下来会添加m条边
u v l r 表示在l-r这么多树上添加一条u连到v的边
接下来有q个询问
x l r表示第l到第r棵树的节点x的子树大小的和是多少。

题解：

第一次遇到这种题目，
很明显我们不能开这么多树，用主席树的话也不好查询，树链剖分会T。。
它只需要开一棵线段树，由与所有的树长得都一样，不过是有些地方没有节点而已，那么我们可以将其看成一棵树，处理出它的dfs序，并且记录每一个点的起始点和终点，那么这棵树的子树也就是终点的和-起点的和。那么我们线段树维护的就是每个节点的所存在的树的区间，然后查询的时候也是按照dfs序查询，直接+这个查询区间所在的dfs序的终点的l-r的和-（起始点-1）位置所在的l-r的和。这样就是这棵树的所有状态了。
有点难懂，看代码应该能理解一点

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
ll sum[N*4],flag[N*4];
int dfn[N],sta[N],en[N];
struct node
{int to,next;
}e[N];
int cnt,head[N],tot,le[N],rig[N];
void add(int x,int y)
{e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt++;
}
struct que
{int id,l,r,f;
};
void push_down(int l,int r,int root)
{if(!flag[root])return ;int mid=l+r>>1;sum[root<<1]+=(ll)(mid-l+1)*flag[root];sum[root<<1|1]+=(ll)(r-mid)*flag[root];flag[root<<1]+=flag[root];flag[root<<1|1]+=flag[root];flag[root]=0;
}
void update(int l,int r,int root,int ql,int qr)
{if(l>=ql&&r<=qr){sum[root]+=(ll)r-l+1;flag[root]++;return ;}push_down(l,r,root);int mid=l+r>>1;if(mid>=ql)update(l,mid,root<<1,ql,qr);if(mid<qr)update(mid+1,r,root<<1|1,ql,qr);sum[root]=sum[root<<1]+sum[root<<1|1];
}
ll query(int l,int r,int root,int ql,int qr)
{if(l>=ql&&r<=qr)return sum[root];push_down(l,r,root);int mid=l+r>>1;ll ans=0;if(mid>=ql)ans+=query(l,mid,root<<1,ql,qr);if(mid<qr)ans+=query(mid+1,r,root<<1|1,ql,qr);return ans;
}
void dfs(int x)
{dfn[sta[x]=++tot]=x;for(int i=head[x];~i;i=e[i].next)dfs(e[i].to);en[x]=tot;
}
vector<que>qq[N];
ll ans[N];
int main()
{memset(head,-1,sizeof(head));int n,m,u,v,l,r;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d%d",&u,&v,&l,&r),add(u,v),le[v]=l,rig[v]=r;le[1]=1,rig[1]=n;dfs(1);int q;scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%d%d%d",&u,&l,&r);qq[sta[u]-1].push_back({i,l,r,-1});qq[en[u]].push_back({i,l,r,1});}for(int i=1;i<=tot;i++){update(1,n,1,le[dfn[i]],rig[dfn[i]]);for(auto j:qq[i])ans[j.id]+=query(1,n,1,j.l,j.r)*j.f;}for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);return 0;
}

这篇关于2019牛客暑期多校训练营（第八场）I Inner World —— 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---