当前位置:网站首页>P1505 [国家集训队]旅游 树链剖分
P1505 [国家集训队]旅游 树链剖分
2022-08-09 07:01:00 【swust_fang】
题目链接
题意:树上更新某一点权值,更新两点简单路径权值,查询最大,最小,和
思路:思路应该比较简单,就是树链剖分后用线段树维护区间最大最小以及区间和。
但是本题比较特殊的是给的边权,转化为点权即可。但是查询或者更新两点x,y之间路径的时候,x,y的lca点的点权对应的边是
fathar[lca]--->lca这条边,不属于x->y的简单路径。
所以在更新或者查询的时候,当处理到x,y属于同一条链的时候
这个过程说的是查询x->y,x,y一直往上跳,直到有一个跳到lca时(若dep[x]<dep[y],x就是lca)
这时x,y属于一个连续区间,又因x点的权值不算,就是更新(dfn[x]+1,y),dfn为时间戳
所以算是一道比较基础的树链剖分吧。
但是,这该死的码量,也太恶心了,我就写了一个bug,找了整两个小时?,wc
一个update1写成update我就真找不到。。。我太难了
//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
//freopen("E://1.in","r",stdin);
//freopen("E://1.out","w",stdout);
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
//const int mod=1e9+7;
const int maxn=2e5+5;
int d[maxn],f[maxn],dfn[maxn],tim[maxn],top[maxn],size[maxn],son[maxn],a[maxn];
int head[maxn],sign;
char s[3];
struct node
{
int to,p,val;
}edge[maxn<<1];
struct nod
{
int mx,mi,sum;
}tree[maxn<<2];
int lazy[maxn<<2];
int n,t;
void init()
{
for(int i=0;i<=n;i++) head[i]=-1;
sign=t=0;
}
void add(int u,int v,int val)
{
edge[sign]=node{v,head[u],val};
head[u]=sign++;
}
void dfs1(int u,int pre,int step)
{
d[u]=step;
f[u]=pre;
size[u]=1;
for(int i=head[u];~i;i=edge[i].p)
{
int v=edge[i].to;
if(v==pre) continue;
a[v]=edge[i].val;
dfs1(v,u,step+1);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp)
{
dfn[u]=++t;
tim[t]=u;
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(int i=head[u];~i;i=edge[i].p)
{
int v=edge[i].to;
if(v!=f[u]&&v!=son[u]) dfs2(v,v);
}
}
void pushup(int i,int l,int r)
{
tree[i].sum=tree[lson].sum+tree[rson].sum;
tree[i].mx=max(tree[lson].mx,tree[rson].mx);
tree[i].mi=min(tree[lson].mi,tree[rson].mi);
}
void pushdown(int i,int l,int r)
{
if(lazy[i])
{
tree[lson].sum=-tree[lson].sum;
tree[rson].sum=-tree[rson].sum;
int t1=tree[lson].mx,t2=tree[rson].mx,s1=tree[lson].mi,s2=tree[rson].mi;
tree[lson].mx=-s1,tree[rson].mx=-s2,tree[lson].mi=-t1,tree[rson].mi=-t2;
lazy[lson]^=1;
lazy[rson]^=1;
lazy[i]=0;
}
}
void build(int i,int l,int r)
{
if(l==r)
{
tree[i].sum=tree[i].mi=tree[i].mx=a[tim[l]];
return ;
}
int mid=half;
build(Lson);
build(Rson);
pushup(myself);
}
void update(int i,int l,int r,int x,int val)//单点更新
{
if(l==r)
{
tree[i].sum=tree[i].mi=tree[i].mx=val;
return;
}
int mid=half;
pushdown(myself);
if(x<=mid) update(Lson,x,val);
else update(Rson,x,val);
pushup(myself);
}
void update1(int i,int l,int r,int ql,int qr)//区间取反
{
if(ql>qr) return;
if(ql<=l&&qr>=r)
{
tree[i].sum=-tree[i].sum;
lazy[i]=1-lazy[i];
int x=tree[i].mi;
tree[i].mi=-tree[i].mx;
tree[i].mx=-x;
return;
}
pushdown(myself);
int mid=half;
if(qr<=mid) update1(Lson,ql,qr);
else if(ql>mid) update1(Rson,ql,qr);
else update1(Lson,ql,mid),update1(Rson,mid+1,qr);
pushup(myself);
}
int find_sum(int i,int l,int r,int ql,int qr)
{
if(ql>qr) return 0;
if(ql<=l&&qr>=r) return tree[i].sum;
pushdown(myself);
int mid=half;
if(qr<=mid) return find_sum(Lson,ql,qr);
else if(ql>mid) return find_sum(Rson,ql,qr);
else return find_sum(Lson,ql,mid)+find_sum(Rson,mid+1,qr);
}
int find_max(int i,int l,int r,int ql,int qr)
{
if(ql>qr) return -inff;
if(ql<=l&&qr>=r) return tree[i].mx;
pushdown(myself);
int mid=half;
if(qr<=mid) return find_max(Lson,ql,qr);
else if(ql>mid) return find_max(Rson,ql,qr);
else return max(find_max(Lson,ql,mid),find_max(Rson,mid+1,qr));
}
int find_min(int i,int l,int r,int ql,int qr)
{
if(ql>qr) return inff;
if(ql<=l&&qr>=r) return tree[i].mi;
pushdown(myself);
int mid=half;
if(qr<=mid) return find_min(Lson,ql,qr);
else if(ql>mid) return find_min(Rson,ql,qr);
else return min(find_min(Lson,ql,mid),find_min(Rson,mid+1,qr));
}
void solve(int x,int y)//区间更新pre处理
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
update1(1,1,n,dfn[top[x]],dfn[x]);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
update1(1,1,t,dfn[x]+1,dfn[y]);
}
int get_max(int x,int y)
{
int ans=-inff;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=max(ans,find_max(1,1,t,dfn[top[x]],dfn[x]));
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans=max(ans,find_max(1,1,t,dfn[x]+1,dfn[y]));
return ans;
}
int get_min(int x,int y)
{
int ans=inff;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=min(ans,find_min(1,1,t,dfn[top[x]],dfn[x]));
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans=min(ans,find_min(1,1,t,dfn[x]+1,dfn[y]));
return ans;
}
int get_sum(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans+=find_sum(1,1,t,dfn[top[x]],dfn[x]);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans+=find_sum(1,1,t,dfn[x]+1,dfn[y]);
return ans;
}
int main()
{
// freopen("E://2.in","r",stdin);
// freopen("E://1.out","w",stdout);
cin>>n;
int x,y,val;
init();
for(int i=1;i<n;i++)
{
scanf("%d %d %d",&x,&y,&val);
x++,y++;
add(x,y,val),add(y,x,val);
}
dfs1(1,1,1);dfs2(1,1);build(1,1,n);
int r;cin>>r;
while(r--)
{
scanf("%s",s);
scanf("%d %d",&x,&y);
x++,y++;
if(s[0]=='C') update(1,1,n,dfn[x],y-1);
else if(s[0]=='N') solve(x,y);
else if(s[2]=='M') printf("%d\n",get_sum(x,y));
else if(s[2]=='X') printf("%d\n",get_max(x,y));
else printf("%d\n",get_min(x,y));
}
return 0;
}
边栏推荐
- SIGINT, SIGKILL, SIGTERM signal difference, summary of various signals
- 排序第三节——交换排序(冒泡排序+快速排序+快排的优化)(5个视频讲解)
- 按图搜索1688商品接口(item_search_img-按图搜索1688商品(拍立淘接口)代码对接教程
- 多米诺骨牌
- 单例 DCL(double check lock) 饱汉模式和饿汉模式
- 【烂笔头】各厂商手机手动抓log
- 2022 年全球十大最佳自动化测试工具
- car-price-deeplearning-0411
- 【MySQL】update mysql.user set authentication_string=password(“123456“) where User=‘root‘; 报错
- The division principle summary within the collection
猜你喜欢
【nuxt】服务器部署步骤
DSP+ARM+FPGA高速PCIE/千兆网口信号仿真介绍
字节跳动笔试题2020 (抖音电商)
Leetcode 70 stairs issues (Fibonacci number)
leetcode 之 70 爬楼梯问题 (斐波那契数)
【报错】Root Cause com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: Communications link failure
Distributed id generator implementation
长沙学院2022暑假训练赛(一)六级阅读
细谈VR全景:数字营销时代的宠儿
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道
随机推荐
【Shell】查找进程的pid并根据pid获取该进程所占用的端口号以及该进程在系统中所下达的指令名称
vlucas/phpdotenv phpdotenv获取变量内容偶尔出现返回false
Use of PlantUML plugin in idea
Example of using the cut command
Altium designer software commonly used the most complete package library, including schematic library, PCB library and 3D model library
db.sqlite3 has no "as Data Source" workaround
字节也开始缩招了...
Explain the wait() function and waitpid() function in C language in detail
Error jinja2.exceptions.UndefinedError: 'form' is undefined
【修电脑】系统重装但IP不变后VScode Remote SSH连接失败解决
Reverse Engineering
Thread Pool Summary
Zero shift of leetcode
事务总结
Simple to use Lambda expressions
浅识微服务架构
longest substring without repeating characters
unity第一课
如何 认识与学习BASH
2017.10.26模拟 b energy