hdu 3966(树链剖分+线段树区间更新)

时间:2022-02-08 03:09:54

传送门:Problem 3966

https://www.cnblogs.com/violet-acmer/p/9711441.html

学习资料:

  [1]线段树区间更新:https://blog.csdn.net/zhhe0101/article/details/53871453

           https://yq.aliyun.com/articles/252586

  [2]树链剖分:http://blog.sina.com.cn/s/blog_7a1746820100wp67.html

         https://wenku.baidu.com/view/7548d8706ad97f192279168884868762caaebbfc.html?from=search

题意:

  敌军有N个营地,这N个营地通过M条边连接;
  每个营地有且仅有一条边连接(意味着M=N-1,就是一颗含有N个节点的树)
  要求支持两种操作:
  1营地u与营地v以及其之间的所有营地增加或减少ai个士兵。
  2询问营地u当前含有的士兵个数

题解:

  树链剖分模板题。

  实质上树链剖分进行了点对点的一次映射,保证了重链上的点在线段树上的位置是连续的。

  树链剖分的两个性质(转):

    性质1:如果(v,u)为轻边,则siz[u] * 2 < siz[v];

    性质2:从根到某一点的路径上轻链、重链的个数都不大于logn。

  保证了一个区间的时间复杂度是log2(n)。

  要分清3种标号含义(易混) :树中节点标号,树中节点对应线段树中位置标号,线段树中区间标号。

树链剖分相关数组意义 :

  siz[i] : 以i为根的子树的大小

  fa[i] : i节点的父亲

  depth[i]  : i节点的深度

  son[i] : i节点的重儿子(所有儿子中size最大的)

  tid[i] : i节点在线段树中对应的位置    

  top[i] : i节点所在重链的顶端节点,若为轻链,则为自身。

  rid[i] : 线段树中所对应树中节点(作用和tid[ ] 正好相反)。

AC代码:

  摘抄自大佬博客:

  分析:典型的树链剖分题目,先进行剖分,然后用线段树去维护即可,注意HDU的OJ采用Windows系统,容易爆栈,所以在代码前面加上:

  #pragma comment(linker, "/STACK:1024000000,1024000000")进行手动扩栈。

  (但不加也可以AC)

 //#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ls(x)((x)<<1)
#define rs(x)((x)<<1 | 1)
const int maxn=5e4+; int A[maxn];
//========链式前向星========
struct Node1
{
int to;
int next;
}edge[maxn<<];
int head[maxn];
int cnt;
void addEdge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
//==========================
//=========树链剖分=========
int fa[maxn];
int son[maxn];
int tid[maxn];
int rid[maxn];
int siz[maxn];
int top[maxn];
int depth[maxn];
int label; void dfs1(int u,int f,int d)
{
fa[u]=f;
siz[u]=;
depth[u]=d;
for(int i=head[u];~i;i=edge[i].next)
{
int to=edge[i].to;
if(to != f)
{
dfs1(to,u,d+);
siz[u] += siz[to];
if(son[u] == - || siz[to] > siz[son[u]])
son[u]=to;
}
}
}
void dfs2(int u,int newTop)
{
top[u]=newTop;
tid[u]=++label;
rid[tid[u]]=u;
if(son[u] == -)
return ;
dfs2(son[u],newTop);
for(int i=head[u];~i;i=edge[i].next)
{
int to=edge[i].to;
if(to != son[u] && to != fa[u])
dfs2(to,to);
}
}
//==========================
//==========线段树==========
struct Node2
{
int l,r;
int val;
int lazy;
int mid(){
return l+((r-l)>>);
}
}segTree[maxn<<];
void buildTree(int l,int r,int pos)
{
segTree[pos].l=l,segTree[pos].r=r;
segTree[pos].lazy=;
if(l == r)
{
segTree[pos].val=A[rid[l]];
return ;
}
int mid=l+((r-l)>>);
buildTree(l,mid,ls(pos));
buildTree(mid+,r,rs(pos));
}
void pushDown(int pos)
{ if(segTree[pos].lazy != )
{
segTree[ls(pos)].lazy += segTree[pos].lazy;
segTree[rs(pos)].lazy += segTree[pos].lazy; //segTree[ls(pos)].val += segTree[pos].lazy;
//segTree[rs(pos)].val += segTree[pos].lazy; segTree[pos].lazy=;
}
}
void update(int a,int b,int val,int pos)
{
if(a <= segTree[pos].l && b >= segTree[pos].r)
{
segTree[pos].lazy += val;
//segTree[pos].val += val;
return ;
}
pushDown(pos); int mid=segTree[pos].mid();
if(b <= mid)
update(a,b,val,ls(pos));
else if(a > mid)
update(a,b,val,rs(pos));
else
{
update(a,mid,val,ls(pos));
update(mid+,b,val,rs(pos));
}
}
int query(int k,int pos)
{
if(segTree[pos].l == segTree[pos].r)
return segTree[pos].val+segTree[pos].lazy; pushDown(pos);
int mid=segTree[pos].mid(); if(k <= mid)
return query(k,ls(pos));
else
return query(k,rs(pos));
}
//==========================
void Find(int a,int b,int val)
{
while(top[a] != top[b])
{
if(depth[top[a]] > depth[top[b]])
{
update(tid[top[a]],tid[a],val,);
a=fa[top[a]];
}
else
{
update(tid[top[b]],tid[b],val,);
b=fa[top[b]];
}
}
if(tid[a] > tid[b])
swap(a,b);
update(tid[a],tid[b],val,);
} void init()
{
cnt=;
memset(head,-,sizeof(head));
label=;
memset(son,-,sizeof(son));
}
int main()
{
int n,m,q;
while(~scanf("%d%d%d",&n,&m,&q))
{
init();
for(int i=;i <= n;++i)
scanf("%d",A+i);
for(int i=;i <= m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
addEdge(u,v);
addEdge(v,u);
}
dfs1(,,);
dfs2(,);
buildTree(,label,);
char op[];
for(int i=;i <= q;++i)
{
scanf("%s",op);
if(op[] == 'Q')
{
int c;
scanf("%d",&c);
printf("%d\n",query(tid[c],));
}
else
{
int c1,c2,k;
scanf("%d%d%d",&c1,&c2,&k);
if(op[] == 'D')
k = -k;
Find(c1,c2,k);
}
}
}
return ;
}

分割线:2019.5.10

省赛倒计时2天;

重新温习了一下树链剖分,改了改代码风格:

 #pragma comment(linker,"/STACK:1024000000,1024000000")///手动扩栈
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=5e4+; int n,m,q;///n个点 ,m条边(m=n-1),q次询问
int a[maxn];///a[i]:初始i营地有a[i]个士兵
int num;
int head[maxn];
struct Edge
{
int to;
int next;
}G[maxn<<];
void addEdge(int u,int v)
{
G[num]=Edge{v,head[u]};
head[u]=num++;
}
int fa[maxn];
int tid[maxn];
int rid[maxn];
int siz[maxn];
int son[maxn];
int top[maxn];
int dep[maxn];
struct Seg
{
int l,r;
int val;
int lazy;
int mid(){return l+((r-l)>>);}
int len(){return r-l+;};
}seg[maxn<<]; void pushDown(int pos)
{
int &lazy=seg[pos].lazy;
if(lazy)
{
seg[ls(pos)].lazy += lazy;
seg[rs(pos)].lazy += lazy;
}
lazy=;
}
void buildSegTree(int l,int r,int pos)
{
seg[pos].l=l;
seg[pos].r=r;
seg[pos].lazy=;
seg[pos].val=;
if(l == r)
{
seg[pos].val=a[rid[l]];///l点在树中对应的编号rid[l]
return ;
}
int mid=l+((r-l)>>);
buildSegTree(l,mid,ls(pos));
buildSegTree(mid+,r,rs(pos));
}
int Query(int l,int pos)
{
if(seg[pos].l == seg[pos].r)
return seg[pos].val+seg[pos].lazy; pushDown(pos); int mid=seg[pos].mid();
if(l <= mid)
return Query(l,ls(pos));
else
return Query(l,rs(pos));
}
void Update(int l,int r,int pos,int val)
{
if(seg[pos].l == l && seg[pos].r == r)
{
seg[pos].lazy += val;
return ;
}
pushDown(pos); int mid=seg[pos].mid();
if(r <= mid)
Update(l,r,ls(pos),val);
else if(l > mid)
Update(l,r,rs(pos),val);
else
{
Update(l,mid,ls(pos),val);
Update(mid+,r,rs(pos),val);
}
}
void Find(int u,int v,int val)
{
while(top[u] != top[v])///u,v不在同一条重链上
{
if(dep[top[u]] > dep[top[v]])
swap(u,v); Update(tid[top[v]],tid[v],,val);///让u,v一步一步靠到同一条重链上
v=fa[top[v]];
}
///return 语句根据题意而定
///再此题中,u==v时就是单点更新
// if(u == v)
// return ;
if(dep[u] > dep[v])
swap(u,v);
///这次不是tid[son[u]],因为上次是边权存在了儿子节点里
Update(tid[u],tid[v],,val);
}
void DFS1(int u,int f,int depth)
{
fa[u]=f;
siz[u]=;
dep[u]=depth;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(v == f)
continue; DFS1(v,u,depth+); siz[u] += siz[v];
if(son[u] == - || siz[v] > siz[son[u]])
son[u]=v;
}
}
void DFS2(int u,int anc,int &k)
{
tid[u]=++k;
rid[k]=u;
top[u]=anc;
if(son[u] == -)
return ;
DFS2(son[u],anc,k); for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(v != fa[u] && v != son[u])
DFS2(v,v,k);
}
}
void Solve()
{
DFS1(,,);
int k=;
DFS2(,,k);
buildSegTree(,k,); char order[];
while(q--)
{
scanf("%s",order);
if(order[] == 'Q')
{
int u;
scanf("%d",&u);
printf("%d\n",Query(tid[u],));///单点查询,查询u营地当前的人数
}
else
{
int u,v,val;
scanf("%d%d%d",&u,&v,&val);///区间更新,更新营地[u,v]人数 +val
if(order[] == 'D')
val=-val;///人数减少
Find(u,v,val);
}
}
}
void Init()
{
num=;
mem(head,-);
mem(son,-);
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&q))
{
Init();
for(int i=;i <= n;++i)
scanf("%d",a+i);
for(int i=;i <= m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
addEdge(u,v);
addEdge(v,u);
}
Solve();
}
return ;
}

hdu 3966(树链剖分+线段树区间更新)的更多相关文章

  1. HDU 2460 Network(双连通&plus;树链剖分&plus;线段树)

    HDU 2460 Network 题目链接 题意:给定一个无向图,问每次增加一条边,问个图中还剩多少桥 思路:先双连通缩点,然后形成一棵树,每次增加一条边,相当于询问这两点路径上有多少条边,这个用树链 ...

  2. POJ&period;2763 Housewife Wind &lpar; 边权树链剖分 线段树维护区间和 &rpar;

    POJ.2763 Housewife Wind ( 边权树链剖分 线段树维护区间和 ) 题意分析 给出n个点,m个询问,和当前位置pos. 先给出n-1条边,u->v以及边权w. 然后有m个询问 ...

  3. 【bzoj2325】&lbrack;ZJOI2011&rsqb;道馆之战 树链剖分&plus;线段树区间合并

    题目描述 给定一棵树,每个节点有上下两个格子,每个格子的状态为能走或不能走.m次操作,每次修改一个节点的状态,或询问:把一条路径上的所有格子拼起来形成一个宽度为2的长方形,从起点端两个格子的任意一个开 ...

  4. Aragorn&&num;39&semi;s Story 树链剖分&plus;线段树 &amp&semi;&amp&semi; 树链剖分&plus;树状数组

    Aragorn's Story 来源:http://www.fjutacm.com/Problem.jsp?pid=2710来源:http://acm.hdu.edu.cn/showproblem.p ...

  5. 【BZOJ-2325】道馆之战 树链剖分 &plus; 线段树

    2325: [ZJOI2011]道馆之战 Time Limit: 40 Sec  Memory Limit: 256 MBSubmit: 1153  Solved: 421[Submit][Statu ...

  6. 【BZOJ2243】&lbrack;SDOI2011&rsqb;染色 树链剖分&plus;线段树

    [BZOJ2243][SDOI2011]染色 Description 给定一棵有n个节点的无根树和m个操作,操作有2类: 1.将节点a到节点b路径上所有点都染成颜色c: 2.询问节点a到节点b路径上的 ...

  7. BZOJ2243 &lpar;树链剖分&plus;线段树)

    Problem 染色(BZOJ2243) 题目大意 给定一颗树,每个节点上有一种颜色. 要求支持两种操作: 操作1:将a->b上所有点染成一种颜色. 操作2:询问a->b上的颜色段数量. ...

  8. POJ3237 &lpar;树链剖分&plus;线段树)

    Problem Tree (POJ3237) 题目大意 给定一颗树,有边权. 要求支持三种操作: 操作一:更改某条边的权值. 操作二:将某条路径上的边权取反. 操作三:询问某条路径上的最大权值. 解题 ...

  9. Aizu&Tab;2450 Do use segment tree 树链剖分&plus;线段树

    Do use segment tree Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.bnuoj.com/v3/problem_show ...

  10. bzoj2243&lbrack;SDOI2011&rsqb;染色 树链剖分&plus;线段树

    2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 9012  Solved: 3375[Submit][Status ...

随机推荐

  1. 杂项之图像处理pillow

    杂项之图像处理pillow 本节内容 参考文献 生成验证码源码 一些小例子 1. 参考文献 http://pillow-cn.readthedocs.io/zh_CN/latest/ pillow中文 ...

  2. jQuery静态方法type使用和源码分析

    jQuery.type方法是检测数据类型的工具方法,在分析其用法之前先总结下js给我们提供了那些监测数据类型的方法: 一.typeof 操作符 下面是测试代码 var data=[],a='123', ...

  3. 之一:CABasicAnimation - 基本动画

    嗷呜嗷呜嗷呜 // 将视图作为属性方便后面执行多个不同动画 _myView = [[UIView alloc] init]; _myView.layer.position = CGPointMake( ...

  4. thinkphp在为图片添加png水印不足的处理

    thinkphp在为图片加水印的时候.如果水印图片是png图片,透明度处理很不理想,与是做以下处理 在Image.class.php中新增 static function imagecopymerge ...

  5. 解决maven-dependency-plugin &lpar;goals &quot&semi;copy-dependencies&quot&semi;&comma; &quot&semi;unpack&quot&semi;&rpar; is not supported by m2e&period;错误

    POM文件报错maven-dependency-plugin (goals "copy-dependencies", "unpack") is not supp ...

  6. Chapter 8&colon; Exceptional Control Flow

    概述: 我们可以用一种“流”的概念来理解处理器的工作流程,PC(Program Counter)依次为a0,a1,a2,...,an-1,这个序列可以称作control flow.当然我们并不总是按顺 ...

  7. RMQ问题--范围最小值问题

    范围最小值问题(Range Minium Query,RMQ)---RMQ问题 一.一维问题 给出一个n个元素的数组A1,A2,...,An, 设计一个数据结构, 支持查询操作Query(L,R):计 ...

  8. 学习用Node&period;js和Elasticsearch构建搜索引擎(2):一些检索命令

    1.Elasticsearch搜索数据有两种方式. 一种方式是通过REST请求URI,发送搜索参数: 另一种是通过REST请求体,发送搜索参数.而请求体允许你包含更容易表达和可阅读的JSON格式.这个 ...

  9. couchdb

    http://docs.couchdb.org/en/2.0.0/api/database/find.html#find-selectors

  10. UITableViewCell在非Nib及Cell重用下设置CellStyle

    在UITableViewController(实现了UITableViewDataSource)下需要实现 - (UITableViewCell *)tableView:(UITableView *) ...