c/c++语言开发共享Luogu P2590 [ZJOI2008]树的统计

最近在学树剖,看到了这题就做了 [ZJOI2008]树的统计 思路 从题面可以知道,这题是树剖题(要求的和模板没什么区别呀喂 就是在普通的树剖上加了一个最大值 所以可以知道就是树剖+特殊的线段树 线段树要可以求区间最大值和区间和 那么就很好做了,基本上就是到树剖模板题 只需要给线段树加个最大值就行了 …

最近在学树剖,看到了这题就做了

[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("%dn",qmax(u,v));         }         if(op=="qsum")         {             int u,v;             cin>>u>>v;             printf("%dn",qsum(u,v));         }     }     system("pause");//上交oj时记得注释或删除     return 0; }

  附带luogu评测结果

Luogu P2590 [ZJOI2008]树的统计

  不知道为什么除了对于操作符使用了cin其他都是scanf和printf的在一本通oj上tle了……

  于是就换成了取消同步的cin cout

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/605149.html

(0)
上一篇 2021年5月13日
下一篇 2021年5月13日

精彩推荐