Aoj 2450 Do use segment tree【树链剖分】

2024-08-24 11:32
文章标签 use tree 树链 剖分 segment aoj 2450

本文主要是介绍Aoj 2450 Do use segment tree【树链剖分】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树链剖分，个人因为姿势太丑就不发代码了。
维护四个域。
区间和，右端最大连续值，左端最大连续值，答案。

注意的是，2操作是一个有序的操作，因此需要求一个LCA，从某点更新到LCA，再从LCA更新到另一个点。当然也有不要LCA的方法，就是通过判断深度，不swap，直接旋转地找。

//      whn6325689
//      Mr.Phoebe
//      http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i<(n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define getidx(l,r) (l+r | l!=r)
#define ls getidx(l,mid)
#define rs getidx(mid+1,r)
#define lson l,mid
#define rson mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c<'0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n<0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN = 200020;struct Node
{ll sumv, suml, sumr, maxv;ll sett;Node(){sumv = 0;sett = INF;suml = sumr = maxv = -INF;}void setv(ll x, ll num){sett = x;sumv = x*num;if(x >= 0)suml = sumr = maxv = sumv;elsesuml = sumr = maxv = x;}Node operator + (const Node &rhs) const{Node c;c.sett = INF;c.sumv = sumv + rhs.sumv;c.suml = max(suml, sumv+rhs.suml);c.sumr = max(sumr+rhs.sumv, rhs.sumr);c.maxv = max(maxv, rhs.maxv);c.maxv = max(c.maxv, sumr+rhs.suml);return c;}
} p[MAXN<<1];vector<int> G[MAXN];
int num[MAXN], top[MAXN], dep[MAXN];
int dfn[MAXN], b[MAXN], fa[MAXN], dfs_clock;
int que[MAXN], iii[MAXN], a[MAXN];
int n, q, ql, qr, _v;void gao()
{int ft = 0, rear = 0;que[rear++] = 1;fa[1] = 0;dep[1] = 1;while(ft < rear){int u = que[ft++];for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(v == fa[u]) continue;fa[v] = u;que[rear++] = v;dep[v] = dep[u]+1;}}memset(num, 0, sizeof num);for(int i = n-1; i >= 0; i--){int u = que[i];num[u]++;num[fa[u]] += num[u];}for(int i = 1; i <= n; i++){for(int j = 1; j < G[i].size(); j++) if(G[i][j] != fa[i])if(G[i][0] == fa[i] || num[G[i][j]] > num[G[i][0]])swap(G[i][0], G[i][j]);}top[1] = 1;for(int i = 1; i < n; i++){int u = que[i];if(G[fa[u]][0] == u) top[u] = top[fa[u]];else top[u] = u;}memset(iii, 0, sizeof iii);ft = 0;dfs_clock = 0;que[++ft] = 1;dfn[1] = ++dfs_clock;b[1] = a[1];while(ft){int u = que[ft];if(iii[u] >= G[u].size()) ft--;else if(G[u][iii[u]] == fa[u]) iii[u]++;else{int v = G[u][iii[u]];que[++ft] = v;dfn[v] = ++dfs_clock;b[dfn[v]] = a[v];iii[u]++;}}
}void print(int a[])
{for(int i = 1; i <= n; i++)printf("%d ", a[i]);puts("");
}void test()
{print(fa);print(top);print(dep);print(dfn);print(b);print(num);
}void build(int l, int r)
{int idx=getidx(l,r),mid=MID(l,r);p[idx].sett=INF;if(l==r){p[idx].setv(b[l], 1);return;}build(lson);build(rson);p[idx]=p[ls]+p[rs];
}void push_down(int l, int r)
{int idx=getidx(l,r),mid=MID(l,r);if(p[idx].sett!=INF){p[ls].setv(p[idx].sett,mid-l+1);p[rs].setv(p[idx].sett,r-mid);p[idx].sett=INF;}
}void update(int l,int r,int L,int R)
{int idx=getidx(l,r),mid=MID(l,r);if(L<=l && r<=R){p[idx].setv(_v, r-l+1);return;}push_down(l,r);if(L<=mid) update(lson,L,R);if(R>mid) update(rson,L,R);p[idx]=p[ls]+p[rs];
}Node query(int l, int r,int L,int R)
{int idx=getidx(l,r),mid=MID(l,r);if(L==l && r==R)return p[idx];push_down(l,r);if(R<=mid) return query(lson,L,R);if(L>mid)  return query(rson,L,R);return query(lson,L,mid)+query(rson,mid+1,R);
}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] ? v : u;
}void change(int u, int v, int c)
{int t=lca(u, v);_v=c;while(top[u] != top[t]){update(1,n,dfn[top[u]],dfn[u]);u=fa[top[u]];}update(1,n,dfn[t],dfn[u]);while(top[v] != top[t]){update(1,n,dfn[top[v]],dfn[v]);v=fa[top[v]];}if(v != t)update(1,n,dfn[t]+1,dfn[v]);
}ll outputquery(int u, int v)
{if(dfn[u] > dfn[v]) swap(u, v);int t=lca(u, v);if(t==u) swap(u, v);Node L,R;while(top[u] != top[t]){L=query(1,n,dfn[top[u]],dfn[u])+L;u=fa[top[u]];}L=query(1,n,dfn[t],dfn[u])+L;while(top[v] != top[t]){R=query(1,n,dfn[top[v]],dfn[v])+R;v=fa[top[v]];}if(v!=t)R=R+query(1,n,dfn[t]+1,dfn[v]);return max(max(L.maxv, R.maxv), L.suml+R.suml);
}int main()
{//freopen("data.txt","r",stdin);int op, u, v, c;while(~scanf("%d %d",&n,&q)){for(int i=1; i<=n; i++){read(a[i]);G[i].clear();}for(int i=1; i < n; i++){read(u),read(v);G[u].push_back(v);G[v].push_back(u);}gao();build(1,n);while(q--){read(op),read(u),read(v),read(c);if(op==1)change(u,v,c);elsewrite(outputquery(u,v)),putchar('\n');}}return 0;
}

不要求LCA的方法。

#include <bits/stdc++.h>
#define MAXN 300500
#define lson getidx(l, mid)
#define rson getidx(mid + 1, r)using namespace std;
typedef long long LL;
const LL inf = 0x3f3f3f3f3f3f;
struct edge
{int to,next;
} E[MAXN*2];
int head[MAXN],si,sz[MAXN],top[MAXN],son[MAXN],fa[MAXN],w[MAXN],dep[MAXN], add[MAXN<<1], isupdate[MAXN<<1], N, Q, A[MAXN], idx, mp[MAXN], que[MAXN];
struct node
{LL sum,ls,rs,ans;node(LL _ans = 0, LL _sum = 0, LL _ls = 0, LL _rs = 0 ){ans = _ans;sum = _sum;ls = _ls;rs = _rs;}
} tree[MAXN<<1];
void add_edge(int u,int v)
{E[si].to = v;E[si].next = head[u];head[u] = si ++;
}
void bfs(int v)
{
//printf("fa[%d]=%d\n",v,fa[v]);int l = 0, r = 0;for(que[r ++] = v; l < r; l ++){int now = que[l];for(int i =head[now]; ~i; i = E[i].next){int u =E[i].to;if( u == fa[now] )continue;fa[u] = now;dep[u] = dep[now] + 1;que[r ++] = u;}}for(; r; r --){int now = que[r - 1];sz[now] = 1;son[now] = 0;for(int i =head[now]; ~i; i = E[i].next){int u =E[i].to;if( u == fa[now] )continue;sz[now] += sz[u];if( sz[son[now]] < sz[u] ){son[now] = u;}}}
}
void rdfs(int v,int root)
{w[v] = ++ idx;mp[idx] = v;top[v] = root;if( son[v] ) rdfs(son[v], root);for(int i =head[v]; ~i; i = E[i].next){int u = E[i].to;if( u == fa[v] || u == son[v] )continue;rdfs(u,u);}
}
int getidx(int l,int r)
{return l + r | l != r;
}
void updatenode(node &p, int x, int l, int r)
{p = node( x, x * (r - l + 1), x, x );if( x >= 0){p = node(x * (r - l + 1), x * (r - l + 1), x * (r - l + 1), x * (r - l + 1));}
}
void push_down(int l, int r)
{int p =getidx(l, r), mid = l + r >> 1;if( l == r || !isupdate[p] )return;updatenode(tree[lson], add[p], l, mid);updatenode(tree[rson], add[p], mid + 1, r);isupdate[p] = false;isupdate[lson] = true;isupdate[rson] = true;add[lson] = add[rson] = add[p];
}
node unite(node a, node b)
{node p;p.ans = max(a.ans, b.ans);p.ans = max(p.ans, a.rs + b.ls);p.sum = a.sum + b.sum;p.ls = max(a.ls, a.sum + b.ls);p.rs = max(b.rs, b.sum + a.rs);return p;
}
void put_up(int l, int r)
{int p =getidx(l, r), mid = l + r >> 1;if( l == r ) return;tree[p] = unite(tree[lson], tree[rson]);
}void build(int l,int r)
{int p =getidx(l, r);isupdate[p] = false;add[p] = 0;if( l == r ){updatenode(tree[p], A[mp[l]], l, r);//  printf("[%d,%d]:%lld, %lld ,%lld, %lld\n",l, r,tree[p].ans, tree[p].sum, tree[p].ls, tree[p].rs);return;}int mid = l + r >> 1;build(l, mid);build(mid + 1, r);put_up(l, r);//printf("[%d,%d]:%lld, %lld ,%lld, %lld\n",l, r,tree[p].ans, tree[p].sum, tree[p].ls, tree[p].rs);
}
void update(int l, int r, int _l, int _r, int x)
{if( l > _r || r < _l )return;if( _l <= l && r <= _r ){int p = getidx(l, r);updatenode(tree[p], x, l, r);add[p] = x;isupdate[p] = true;return;}int mid = l + r >> 1;push_down(l, r);update(l, mid, _l, _r, x);update(mid + 1, r, _l, _r, x);put_up(l, r);
}
void update(int u,int v,int x)
{int a = top[u], b = top[v];while(a != b){if( dep[a] < dep[b] ){swap(a, b);swap(u, v);}update(1, N, w[a], w[u], x);u = fa[a];a = top[u];}if( dep[u] < dep[v] ){swap(u, v);}update(1, N, w[v], w[u], x);
}
node query(int l, int r, int _l, int _r)
{if( _l <= l && r <= _r ){return tree[getidx(l, r)];}int mid = l + r >> 1;push_down(l, r);if( _r <= mid ) return query(l, mid, _l, _r);else if( _l > mid ) return  query(mid + 1, r, _l, _r);else{return unite(query(l, mid, _l, _r), query(mid + 1, r, _l, _r));}
}LL query(int u, int v)
{int a = top[u], b = top[v];node lpath = node(-inf , 0, -inf, -inf), rpath = node(-inf, 0, -inf, -inf);while(a != b){if( dep[a] > dep[b]){node res = query(1, N, w[a], w[u]);swap(res.ls, res.rs);lpath = unite(lpath, res);//  printf("lpath:%d->%d: %lld %lld %lld %lld\n", a, u, lpath.ans,lpath.sum, lpath.ls, lpath.rs);u = fa[a];a = top[u];}else{node res = query(1, N, w[b], w[v]);rpath = unite(res, rpath);//printf("rpath:%d->%d: %lld %lld %lld %lld\n", b, v, rpath.ans,rpath.sum, rpath.ls, rpath.rs);v = fa[b];b = top[v];}}node ans;if( dep[u] < dep[v] ){ans = query(1, N, w[u], w[v]);}else{ans = query(1, N, w[v], w[u]);swap(ans.ls,ans.rs);}// printf("%d->%d: %lld %lld %lld %lld\n", v, u, ans.ans,ans.sum, ans.ls, ans.rs);ans = unite(lpath, ans);//  printf(": %lld %lld %lld %lld\n",  ans.ans,ans.sum, ans.ls, ans.rs);ans = unite(ans, rpath);return ans.ans;
}
int main()
{//  freopen("in", "r", stdin);scanf("%d %d", &N, &Q);for(int i = 1; i <= N; i ++){scanf("%d", &A[i]);}memset(head, -1, sizeof head);si = 0;idx = 0;for(int i = 1, u, v; i < N; i ++){scanf("%d%d", &u, &v);add_edge(u, v);add_edge(v, u);}fa[1] = dep[1] = 0;bfs(1);rdfs(1, 1);build(1, N);for(int i = 1, t, u, v, x; i <= Q; i ++){scanf("%d%d%d%d", &t, &u, &v, &x);if( t == 1 ){update(u, v, x);}else{long long ans = query(u, v);printf("%lld\n", ans);}}return 0;
}

这篇关于Aoj 2450 Do use segment tree【树链剖分】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1102352。

相关文章

论文阅读笔记: Segment Anything

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear
阅读更多...
树（Tree）——《啊哈！算法》

树（Tree）——《啊哈！算法》

树 什么是树？树是一种特殊的图，不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点，那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点（祖先）。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶
阅读更多...
226 Invert Binary Tree

226 Invert Binary Tree

//226 Invert Binary Tree//算法思路：主要使用递归算法public class Solution {public TreeNode invertTree(TreeNode root) {//1 出口 空节点if (root==null)return null;//2 递归 调用自己TreeNode left = root.left;TreeNode right = ro
阅读更多...
Tomcat启动报错：transport error 202: bind failed: Address already in use

Tomcat启动报错：transport error 202: bind failed: Address already in use

Tomcat启动报错：transport error 202: bind failed: Address already in use 了，上网查找了下面这篇文章。也是一种解决办法。 下文来自：http://blog.csdn.net/sam031503/article/details/7037033 tomcat 启动日志报出以下错误：  ERROR: transport err
阅读更多...
Unity Adressables 使用说明（五）在运行时使用 Addressables（Use Addressables at Runtime）

Unity Adressables 使用说明（五）在运行时使用 Addressables（Use Addressables at Runtime）

一旦你将 Addressable assets 组织到 groups 并构建到 AssetBundles 中，就需要在运行时加载、实例化和释放它们。 Addressables 使用引用计数系统来确保 assets 只在需要时保留在内存中。 Addressables 初始化 Addressables 系统在运行时第一次加载 Addressable 或进行其他 Addressable API 调
阅读更多...
Sorry！Hbase的LSM Tree就是可以为所欲为！

Sorry！Hbase的LSM Tree就是可以为所欲为！

我们先抛出一个问题： LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中，数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中，则是使用日志结构合并树（Log-structured Merge Tree，LSM Tr
阅读更多...
torch.backends.cudnn.benchmark和torch.use_deterministic_algorithms总结学习记录

torch.backends.cudnn.benchmark和torch.use_deterministic_algorithms总结学习记录

经常使用PyTorch框架的应该对于torch.backends.cudnn.benchmark和torch.use_deterministic_algorithms这两个语句并不陌生，在以往开发项目的时候可能专门化花时间去了解过，也可能只是浅尝辄止简单有关注过，正好今天再次遇到了就想着总结梳理一下。 torch.backends.cudnn.benchmark 是 PyTorch 中的一个设置
阅读更多...
【spring】does not have member field ‘com.sun.tools.javac.tree.JCTree qualid

【spring】does not have member field ‘com.sun.tools.javac.tree.JCTree qualid

spring-in-action-6-samples 的JDK版本 最小是11，我使用 了22： jdk21 jdk22 都与lombok 不兼容，必须使用兼容版本， 否则报错： thingsboard 的大神解释了： java: java.lang.NoSuchFieldError: Class com
阅读更多...
编译时出现错误 -- clang: error: linker command failed with exit code 1 (use -v to see invocation)

编译时出现错误 -- clang: error: linker command failed with exit code 1 (use -v to see invocation)

出现这个错误的原因有多种，常见的是因为某些文件的缺失或者是文件的重复导致的。 这类错误查看的关键在于其上一行的文字。 对于文件缺少而导致错误的情况： 例如上图中的示例，其上一行文字为 ld：library not found for -lrxl，可以看出是缺失了某一文件而导致的错误，这行文字中的最后“ -lrxl ”：-l 代表着其前缀是“lib”，连着后面的 rxl，其名称为 libr
阅读更多...
Address localhost:1099 is already in use：tomcat频繁重启端口占用问题

Address localhost:1099 is already in use：tomcat频繁重启端口占用问题

错误提示 Unable to open debugger port (127.0.0.1:58198): java.net.SocketException "Socket closed" Address localhost:1099 is already in use 端口被占用 报错原因 由于短时间内频繁运行tomcat服务器。 为了避免出现这一错误。可以点击刷新uodate
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2