Luogu P2590 [ZJOI2008]树的统计
2019-02-20 00:43:34来源:博客园 阅读 ()
最近在学树剖,看到了这题就做了
[ZJOI2008]树的统计
思路
从题面可以知道,这题是树剖题(要求的和模板没什么区别呀喂
就是在普通的树剖上加了一个最大值
所以可以知道就是树剖+特殊的线段树
线段树要可以求区间最大值和区间和
那么就很好做了,基本上就是到树剖模板题
只需要给线段树加个最大值就行了
实现
给线段树添加一个max,记录区间最大值
可以得到线段树结构体如下
struct Tree { int max; int l,r; int lazy; int val; }t[MAXN<<2];
每次更改时更新max,val
由于只有单点修改,因此lazy tag可以不要
对于最大值,每次访问取两个区间的最大值
对于和,就和一般线段树一样了
求和代码如下
int query_sum(int x,int y,int p) { if(x<=t[p].l&&t[p].r<=y) return t[p].val; int mid=(t[p].l+t[p].r)>>1; int ans=0; if(x<=mid) ans+=query_sum(x,y,p<<1); if(y>mid) ans+=query_sum(x,y,p<<1|1); return ans; }
求最大值代码如下
int query_max(int x,int y,int p) { if(x<=t[p].l&&t[p].r<=y) return t[p].max; int mid=(t[p].l+t[p].r)>>1; int ans=-1e9; if(x<=mid) ans=std::max(ans,query_max(x,y,p<<1)); if(y>mid) ans=std::max(ans,query_max(x,y,p<<1|1)); return ans; }
最后就是结合树剖了
代码
#include<bits/stdc++.h> #define ll long long using std::cin; using std::cout; using std::endl; const int MAXN=3e4+5; struct Edge { int to,next; }e[MAXN<<1]; struct Tree { int max; int l,r; int lazy; int val; }t[MAXN<<2]; int son[MAXN],depth[MAXN],id[MAXN],num[MAXN],head[MAXN],pri[MAXN],size[MAXN],fa[MAXN],top[MAXN]; int cnt=0; void dfs1(int p,int f) { depth[p]=depth[f]+1; fa[p]=f; size[p]=1; int now=head[p]; while(now!=-1) { if(e[now].to==f) { now=e[now].next; continue; } dfs1(e[now].to,p); size[p]+=size[e[now].to]; if(son[p]==-1||size[son[p]]<size[e[now].to]) son[p]=e[now].to; now=e[now].next; } } void dfs2(int p,int t) { top[p]=t; num[++cnt]=p; id[p]=cnt; if(son[p]==-1) return; dfs2(son[p],t); int now=head[p]; while(now!=-1) { if(e[now].to==son[p]||e[now].to==fa[p]) { now=e[now].next; continue; } dfs2(e[now].to,e[now].to); now=e[now].next; } } void build(int x,int y,int p) { t[p].l=x; t[p].r=y; if(x==y) { t[p].val=pri[num[x]]; t[p].max=pri[num[x]]; return; } int mid=(x+y)>>1; build(x,mid,p<<1); build(mid+1,y,p<<1|1); t[p].max=std::max(t[p<<1].max,t[p<<1|1].max); t[p].val=t[p<<1].val+t[p<<1|1].val; } void change(int u,int p,int w) { if(t[p].l==u&&t[p].r==u) { t[p].val=w; t[p].max=w; return; } int mid=(t[p].l+t[p].r)>>1; if(u<=mid) change(u,p<<1,w); else change(u,p<<1|1,w); t[p].val=t[p<<1].val+t[p<<1|1].val; t[p].max=std::max(t[p<<1].max,t[p<<1|1].max); } int query_max(int x,int y,int p) { if(x<=t[p].l&&t[p].r<=y) return t[p].max; int mid=(t[p].l+t[p].r)>>1; int ans=-1e9; if(x<=mid) ans=std::max(ans,query_max(x,y,p<<1)); if(y>mid) ans=std::max(ans,query_max(x,y,p<<1|1)); return ans; } int query_sum(int x,int y,int p) { if(x<=t[p].l&&t[p].r<=y) return t[p].val; int mid=(t[p].l+t[p].r)>>1; int ans=0; if(x<=mid) ans+=query_sum(x,y,p<<1); if(y>mid) ans+=query_sum(x,y,p<<1|1); return ans; } int qmax(int x,int y) { int ans=-1e9; while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) std::swap(x,y); ans=std::max(ans,query_max(id[top[x]],id[x],1)); x=fa[top[x]]; } if(id[x]>id[y]) std::swap(x,y); ans=std::max(ans,query_max(id[x],id[y],1)); return ans; } int qsum(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) std::swap(x,y); ans+=query_sum(id[top[x]],id[x],1); x=fa[top[x]]; } if(id[x]>id[y]) std::swap(x,y); ans+=query_sum(id[x],id[y],1); return ans; } int main() { std::ios::sync_with_stdio(false); memset(head,-1,sizeof(head)); memset(son,-1,sizeof(son)); int n; cin>>n; for(int i=0;i<2*(n-1);i++) { int a,b; cin>>a>>b; e[i].to=b; e[i].next=head[a]; head[a]=i++; e[i].to=a; e[i].next=head[b]; head[b]=i; } for(int i=1;i<=n;i++) cin>>pri[i]; int q; cin>>q; dfs1(1,0); cnt=0; dfs2(1,1); build(1,n,1); for(int i=0;i<q;i++) { std::string op; cin>>op; if(op=="CHANGE") { int u,v; cin>>u>>v; change(id[u],1,v); } if(op=="QMAX") { int u,v; cin>>u>>v; printf("%d\n",qmax(u,v)); } if(op=="QSUM") { int u,v; cin>>u>>v; printf("%d\n",qsum(u,v)); } } system("pause");//上交oj时记得注释或删除 return 0; }
附带Luogu评测结果
不知道为什么除了对于操作符使用了cin其他都是scanf和printf的在一本通oj上TLE了……
于是就换成了取消同步的cin cout
原文链接:https://www.cnblogs.com/Cattttttttt/p/10403509.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:图的存储
下一篇:L1-050 倒数第N个字符串
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 不一样的LCA——luoguP1852跳跳棋 2019-11-13
- LuoguP3069 【[USACO13JAN]牛的阵容Cow Lineup 2019-10-30
- 题解 Luogu P3959 【宝藏】 2019-09-23
- bozj1040: [ZJOI2008]骑士(奇环树,DP) 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash