当前位置: 首页 > news >正文

P3605解题报告

前言

毕竟是解题报告,自然只是个报告了
最近再刷树状数组的题,但是线段树很多时候也能维护这个东西
当然,有些题目还可以使用主席树解决,看个人习惯了

题目意思

给出一颗带点权树,对于每一个节点求出他的子孙节点中有多少个点的点权大于他的点权
传送门

想法

这个题目我是使用的线段树做法,但是自然也是可以使用树状数组代替线段树的

首先既然一个树不好做,我们先考虑链怎么做
我们可以对于一个链直接找他的逆序对数量,用树状数组维护
考虑为什么一个链会这么好做
发现一个链的特殊性质就是他的子孙节点就是 \(\ge i\) 的节点,他的子孙节点都是一个连续的区间,所以非常好做
现在考虑我们树怎么做,我们既然想要想链一样做,那么我们必然是让一个结点的子孙节点都变成一个连续的区间,考虑什么东西可以满足让一个结点的子孙节点是一个区间,发现只有 dfn 序满足要求
那么假设一个节点在 dfn 序出现的位置为 \(in_x\),他的子树大小为 \(siz_x\) 那么他的子孙节点的 dfn 位置区间就是 \([in_x,in_x+siz_x-1]\),然后类比链的做法,我们将 \(a_i\) 大的数字先插入,这样如果 \([in_x,in_x+siz_x-1]\) 里面有数,那么就一定是 \(\ge a_i\) 的数字,所以用线段树维护这个区间的和即可

做法

找到这个树的 dfn 序,找到他的子树所在 dfn 区间后,从大到小插入 \(a_i\)\(i\) 的答案就是字数所在 dfn 区间的和,可以用线段树维护单点加区间求和。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<vector>
#include<cmath>
#define ll long longusing namespace std;
const int N=1e5+9;
int n,dfn[N],cnt,in[N],out[N],ans[N];
vector<int>e[N];
struct number{int x,id;}num[N];
inline bool cmp(number x,number y){return x.x>y.x;
}inline void dfs(int x){dfn[++cnt]=x;in[x]=cnt;for(int to:e[x])dfs(to);out[x]=cnt;
}struct node{int lt,rt,sum;};
struct segment{#define lson(x) x<<1#define rson(x) x<<1|1node tr[N<<2];inline node pushup(node x,node y){return {x.lt,y.rt,x.sum+y.sum};}inline void build(int id,int l,int r){tr[id].lt=l;tr[id].rt=r;if(l==r) return void();int mid=l+r>>1;build(lson(id),l,mid);build(rson(id),mid+1,r);}inline void change(int id,int pos){if(tr[id].lt==tr[id].rt){tr[id].sum++;return void();}int mid=tr[id].lt+tr[id].rt>>1;if(pos<=mid) change(lson(id),pos);else change(rson(id),pos);tr[id]=pushup(tr[lson(id)],tr[rson(id)]);}inline int query(int id,int l,int r){if(l<=tr[id].lt && tr[id].rt<=r)return tr[id].sum;int mid=tr[id].lt+tr[id].rt>>1;if(r<=mid) return query(lson(id),l,r);if(l>mid) return query(rson(id),l,r);return query(lson(id),l,r)+query(rson(id),l,r);}#undef lson#undef rson
}seg;int main(){cin>>n;for(int i=1;i<=n;i++){cin>>num[i].x;num[i].id=i;}for(int i=2;i<=n;i++){int fa;cin>>fa;e[fa].push_back(i);}dfs(1);seg.build(1,1,n);sort(num+1,num+n+1,cmp);for(int i=1;i<=n;i++){ans[num[i].id]=seg.query(1,in[num[i].id],out[num[i].id]);seg.change(1,in[num[i].id]);}for(int i=1;i<=n;i++)cout<<ans[i]<<endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=28693

相关文章:

  • P13763 解题报告
  • CF1082E 解题报告
  • 国标GB28181算法算力平台EasyGBS具备哪些核心流媒体技术?
  • 2025 年净化车间源头厂家最新推荐排行榜:精选实力企业,助力企业精准选择优质净化车间服务商无尘/gmp/新能源/锂电池净化车间厂家推荐
  • C语言的“动态数组”
  • 背包 dp 历年真题:做题记录
  • 【触想智能】什么是工业平板电脑以及工业平板电脑对制造业具有什么意义
  • 2025 年国内无尘车间源头厂家最新推荐排行榜:聚焦无菌洁净领域优选企业助力企业精准选型万级/十万级/洁净/食品厂/千级无尘车间厂家推荐
  • 新手小白安装Typroa遇到的问题 - I
  • 怎么能跑得快,怎么突破瓶颈
  • (Sigcomm25) Stellar: 阿里新一代云AI RDMA网络
  • 高效工作,五步工作法
  • 虚树学习笔记
  • 市场营销:
  • Python3开发敏感词过滤程序底层逻辑记录
  • OUC《软件工程原理与实践》- 实验2:深度学习基础 - OUC
  • 类型转化
  • 【IEEE出版】第五届电子信息工程与计算机技术国际学术会议(EIECT 2025)
  • 【AP出版】第七届文学、艺术与人文发展国际学术会议(ICLAHD 2025)
  • 事件驱动重塑 AI 数据链路:阿里云 EventBridge 发布 AI ETL 新范式
  • 我把Excel变成了像素画板!用Python实现图片到单元格的映射
  • 如何通过内核版本检查判断FreeBSD是否需要重启
  • 2025 年山东染井吉野樱 / 高杆染井吉野樱花 / 染井吉野樱花小苗厂家推荐:绿影园林的培育技术与全规格供应解析
  • C#中关于InvokeRequired 属性 与Invoke方法
  • 云存储成本自动优化技术解析
  • MZOI 20251011【CSP-】模拟 T2 序列区间
  • SAP 中CONCATENATE 空格的时候,空格不生效
  • Java的各类定时任务实现
  • 03:运算符
  • JavaScript内存泄露原因及解决方案