首页 > 其他分享 >树链剖分模板

树链剖分模板

时间：2023-07-13 15:23:34浏览次数：40  
标签：剖分 idx int top mid 树链 seg dep 模板

  • 区间，边权

描述

松鼠爸爸为了让松鼠宝宝更熟悉地熟悉采松果的流程，为其定制了一颗“树”，树上有n个点，n-1条边（无环），每条边上都有一定数量的松果。松鼠爸爸为了让松鼠宝宝得到更多的松果，有m次操作，每次操作给定两个点x，y和一个add，在x点到y点的简单路径上所有的边都增加add个松果。然后松鼠宝宝会去采集q次松果（每次采集后边上的松果数量不会减少），q次采集会给定x，y两个点，采集x点到y点路径上的边上的所有松果，现询问q次采集每次采集会获得多少松果。

输入描述:

第一行读入三个数n，m，q（分别代表树上的点数，操作次数，询问次数）

接下来n-1行读入x，y， z（代表x点和y点之间有边且有z个松果）

接下来m行读入x，y，z（分别代表x点，y点，和增加的松果数量）

接下来q行读入x，y（分别代表x点，y点）

n <=1e5

m <=1e5

q <=1e5

1 <= x, y <= n

0 <= z <= 1e5

输出描述:

输出q行代表每次采集所采集到的松果的数量和

示例1

输入

复制 
7 3 3
1 2 1
1 3 2
2 4 1
2 5 2
3 6 1
3 7 2
2 3 1
1 2 1
2 3 0
2 3
4 7
1 1

输出

复制 
6
9
0
#include<bits/stdc++.h>
#define int long long
const int N = 1e6 + 10;
using namespace std;
int cnt,fst[N],nxt[N],to[N],w[N<<1],fr[N<<1];
int n,a[N],t[N<<2],tag[N<<2],cov[N<<2];
int siz[N],son[N],dfn[N],Index,top[N],rk[N],dep[N],faz[N];
struct now{
    int xx;
    int dd;
};
vector<now>e[N];
map<pair<int,int>,int>mp;
void Dfs1(int u,int f)
{
    siz[u]=1;
    son[u]=0;
    for(auto v:e[u])
    {
        if(v.xx==f) continue;
        faz[v.xx]=u;
        dep[v.xx]=dep[u]+1;
        rk[v.xx]=v.dd;
        Dfs1(v.xx,u);
        siz[u]+=siz[v.xx];
        if(siz[son[u]]<siz[v.xx]) son[u]=v.xx;
    }
}
void Dfs2(int u,int rt)
{
    dfn[u]=++Index;
    top[u]=rt;
    a[Index]=mp[{faz[u],u}];
   // a[Index] = rk[u];
    if(son[u]) Dfs2(son[u],rt);
    for(auto v:e[u])
    {
        if(v.xx==faz[u]||v.xx==son[u])
            continue;
        Dfs2(v.xx,v.xx);
    }
}
void PushUp(int rt)
{
    t[rt]=t[rt<<1]+t[rt<<1|1];
}
void PushDown(int rt, int l, int r)
{
    int mid = l + r >> 1;
    t[rt<<1]+=tag[rt] * (mid - l + 1);
    t[rt<<1|1]+=tag[rt] * (r - mid);
    tag[rt<<1]+=tag[rt];
    tag[rt<<1|1]+=tag[rt];
    tag[rt]=0;
}
void BuildSegmentTree(int rt,int l,int r)
{
    if(l==r)
    {
        t[rt]=a[l];
        return;
    }
    int mid=l+r>>1;
    BuildSegmentTree(rt<<1,l,mid);
    BuildSegmentTree(rt<<1|1,mid+1,r);
    PushUp(rt);
}
void ModifyAdd(int rt,int l,int r,int tl,int tr,int val)
{
    if(tl<=l && r<=tr)
    {
        t[rt]+=val * (r - l + 1);
        tag[rt]+=val;
        return;
    }
    PushDown(rt, l, r);
    int mid=l+r>>1;
    if(tl<=mid) ModifyAdd(rt<<1,l,mid,tl,tr,val);
    if(tr>mid) ModifyAdd(rt<<1|1,mid+1,r,tl,tr,val);
    PushUp(rt);
}
int Query(int rt,int l,int r,int tl,int tr)
{
    if(tl<=l && r<=tr) return t[rt];
    PushDown(rt, l, r);
    int mid=l+r>>1,res=0;
    if(tl<=mid) res+=Query(rt<<1,l,mid,tl,tr);
    if(tr>mid) res+=Query(rt<<1|1,mid+1,r,tl,tr);
    return res;
}
void ModifyAddOnTree(int u,int v,int val)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        ModifyAdd(1,1,n,dfn[top[u]],dfn[u],val);
        u=faz[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    ModifyAdd(1,1,n,dfn[u]+1,dfn[v],val);
}
int QueryMaxnOnTree(int u,int v)
{
    int res=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res+=Query(1,1,n,dfn[top[u]],dfn[u]);
        u=faz[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    res+=Query(1,1,n,dfn[u]+1,dfn[v]);
    return res;
}
int m, k;
signed main()
{
    scanf("%lld %lld %lld",&n, &m, &k);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%lld %lld %lld",&x,&y,&z);
        e[x].push_back({y,z});
        e[y].push_back({x,z});
        mp[{x,y}] = z;
        mp[{y,x}] = z;
    }
    mp[{1,0}] = 0;
    mp[{0,1}] = 0;
    Dfs1(1,0);
    Dfs2(1,1);
    BuildSegmentTree(1,1,n);
    for(int i = 0; i < m; i ++ )
    {
        int x,y,z;
        cin >> x >> y >> z;
        ModifyAddOnTree(x,y,z);
    }
    for(int i = 0; i < k; i ++ ){
        int x, y;
        cin >> x >> y;
        printf("%lld\n",QueryMaxnOnTree(x,y));
    }
    return 0;
}
  • 点权

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：

  1. CHANGE u t，把结点u的权值改为t。
  2. QMAX u v，询问从点u到点v的路径上的节点的最大权值
  3. QSUM u v， 询问从点u到点v的路径上的节点的权值和。注意：从点u到点v的路径上的节点包括u和v本身。

输入格式

输入的第一行为一个整数n，表示节点的个数。接下来n–1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。

接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来一行，为一个整数q，表示操作的总数。

接下来q行，每行一个操作，以CHANGE u t或者QMAX u v或者QSUM u v的形式给出。

保证1≤n≤3×104,0≤q≤2×104，中途操作中保证每个节点的权值w在−3×104到3×104之间。

输出格式

对于每个QMAX或者QSUM的操作，每行输出一个整数表示要求输出的结果。

样例输入

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

样例输出

4
1
2
2
10
6
5
6
5
16

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 1e6 + 10;
int n,m,tot;
int sz[N],hs[N],fa[N],dep[N],top[N],l1[N],id[N],a[N];
vector<int>e[N];

void dfs1(int u,int f)
{
	sz[u] = 1;
	hs[u] = -1;
	fa[u] = f;
	dep[u] = dep[f] + 1;
	for(auto v:e[u])
	{
		if(v == f)
		continue;
		dfs1(v,u);
		sz[u] += sz[v];
		if(sz[v] > sz[hs[u]])
		hs[u] = v;
	}
}
void dfs2(int u,int t)
{
	top[u] = t;
	l1[u] = ++tot;
	id[tot] = u;
	if(hs[u] != -1)
	{
		dfs2(hs[u],t);
	}
	for(auto v:e[u])
	{
		if(v != fa[u] && v != hs[u])
			dfs2(v,v);
	}
}
struct NOW{
	int mx;
	int sum;
}seg[N*4];

void update(int idx)
{
	seg[idx].mx = max(seg[idx*2].mx,seg[idx*2+1].mx);
	seg[idx].sum = seg[idx*2].sum + seg[idx*2+1].sum;
}
void build(int idx,int l,int r)
{
	if(l == r)
	{
		seg[idx].mx = seg[idx].sum = a[id[l]];
	}
	else
	{
		int mid = (l + r)/2;
		build(idx*2,l,mid);
		build(idx*2+1,mid+1,r);
		update(idx);
	}
}
void modify(int idx,int l,int r,int pos,int val)
{
	if(l == r)
	{
		seg[idx].mx = val;
		seg[idx].sum = val;
	}
	else
	{
		int mid = (l + r)/2;
		if(pos <= mid)
		modify(idx*2,l,mid,pos,val);
		else
		modify(idx*2+1,mid+1,r,pos,val);
		update(idx);
	}
}
int querysum1(int idx,int l,int r,int ql,int qr)
{
	if(l == ql && r == qr)
	{
		return seg[idx].sum;
	}
	int mid = (l + r)/2;
	if(qr <= mid)
	return querysum1(idx*2,l,mid,ql,qr);
	else if(ql > mid)
	return querysum1(idx*2+1,mid+1,r,ql,qr);
	else
	{
		return querysum1(idx*2,l,mid,ql,mid) + 
		querysum1(idx*2+1,mid+1,r,mid+1,qr);
	}
}
int querymx1(int idx,int l,int r,int ql,int qr)
{
	if(l == ql && r == qr)
	{
		return seg[idx].mx;
	}
	int mid = (l + r)/2;
	if(qr <= mid)
	return querymx1(idx*2,l,mid,ql,qr);
	else if(ql > mid)
	return querymx1(idx*2+1,mid+1,r,ql,qr);
	else
	{
		return max(querymx1(idx*2,l,mid,ql,mid) ,
		querymx1(idx*2+1,mid+1,r,mid+1,qr));
	}
}


int querysum(int u,int v)
{
	int ans = 0;
	while(top[u]!=top[v])
	{
		if(dep[top[u]] < dep[top[v]])
		swap(u,v);
		ans += querysum1(1,1,n,l1[top[u]],l1[u]);
		u = fa[top[u]];
	}
	if(dep[u] < dep[v])
		swap(u,v);
	ans += querysum1(1,1,n,l1[v],l1[u]);
	return ans;
}
int querymx(int u,int v)
{
	int ans = -1e18;
	while(top[u]!=top[v])
	{
		if(dep[top[u]] < dep[top[v]])
		swap(u,v);
		ans = max(ans,querymx1(1,1,n,l1[top[u]],l1[u]));
		u = fa[top[u]];
	}
	if(dep[u] < dep[v])
		swap(u,v);
	ans = max(ans,querymx1(1,1,n,l1[v],l1[u]));
	return ans;
}
void solve()
{
	cin >> n;
	for(int i = 1;i < n;i ++)
	{
		int x,y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for(int i = 1;i <= n;i ++)
	cin >> a[i];
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	cin >> m;
	for(int i = 1;i <= m;i ++)
	{
		string s;
		int x,y;
		cin >> s;
		//cout << s << '\n';
		cin >> x >> y;
		if(s == "CHANGE")
		 modify(1,1,n,l1[x],y);
		 else if(s == "QMAX") 
		 cout <<querymx(x,y)<<'\n';
		 else
		 cout << querysum(x,y) << '\n';
	}
}
signed main()
{
	solve();
}

　　

 

标签：剖分,idx,int,top,mid,树链,seg,dep,模板
From： https://www.cnblogs.com/ljmxmu/p/17550691.html

相关文章

  • 现代C++（Modern C++）基本用法实践：四、模板
    概述C++的模板是泛型编程思想的一种实现。C++是强类型语言，处处强调类型。同样的加法运算，int和float的加法运算需定义两个函数（重载），而使用模板则可以只用一个函数（见下面示例）。这类似我们面向对象所说的多态（定义加法运算，各个类型有不同的实现），所以是所谓静多态的一种实现方式，不同的......
  • C# 使用Windows服务项目模板快速创建Windows服务程序
    之前写了一篇使用Topshelf创建Windows服务程序的文章：https://www.cnblogs.com/log9527blog/p/17325795.html还可以直接使用VS自带的Windows服务项目模板快速创建Windows服务程序 Service1.cs里面的OnStart和OnStop方法分别代表服务开始，服务停止时执行的逻辑 配置服务Serv......
  • 线段树模板 洛谷P3374 【模板】树状数组 1
    题目传送门题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某一个数加上x2.求出某区间每一个数的和输入格式第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3......
  • 堆(模板)
    题目描述初始小根堆为空，我们需要支持以下3种操作：操作1：1x表示将x插入到堆中操作2：2输出该小根堆内的最小数操作3：3删除该小根堆内的最小数Input第一行包含一个整数N，表示操作的个数接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：操作1：1x操作2：2操作3：3Outp......
  • 老杜 JavaWeb 讲解（九） ——模板方法设计模式、HttpServlet源码分析
    (十一)模板方法设计模式、HttpServlet源码分析对应视频：20-HttpServlet源码分析及web欢迎页11.1模板方法设计模式不用使用在上面右侧表格中，Person就是模板方法设计模式当中的模板类，通常是抽象类。day()方法就是模板方法设计模式当中的模板方法。模......
  • 「模板」树状数组
    引入题目描述给定\(n\)个数\(a[1],a[2],a[3]...a[n]\),现在又下面两种操作：1.询问区间\([x,y]\)的和，并输出。2.将下标为\(x\)的数增加\(val\)。一共\(x\)此操作\(1\len,m\le100000\)，保证在\(int\)范围内。方法一：暴力枚举定义数组\(a\)储存\(n\)个元素。求区间和的时间复......
  • 自用模板
    #pragmaGCCoptimize(2)#include<bits/stdc++.h>#include<iostream>#include<vector>#include<algorithm>#include<set>#include<utility>#include<string.h>#include<ext/rope>#include<queue>#include&l......
  • 业务系统常规部署交接模板
    1总体情况ip应用192.168.1.1前端1192.168.1.2后端1......1.1前端1#1.进程查看#2.服务路径以及启停#3.版本更新#4.日志查看#5.配置文件说明1.2后端1#1.进程查看#2.服务路径以及启停#3.版本更新#4.日志查看......
  • 【模板】并查集
    简介并查集是什么并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。并查集其实就是一个树，如果要合并的话就将其中一个的根节点连接到另外一个的根......
  • 微信小程序(三)列表渲染&数据绑定&事件绑定&路由跳转&生命周期&本地存储&模板使用
    这里新建个页面log，然后用这个页面进行测试。同时修改app.json，将log页面设置为首页"pages":["pages/index/index","pages/log/log"],"entryPagePath":"pages/log/log",0.数据绑定0.简单的绑定wxml用{{val}}取变量<!--pages/log/lo......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99