当前位置:网站首页>Hdu3974 assign the task segment tree DFS order
Hdu3974 assign the task segment tree DFS order
2020-11-06 21:13:24 【itread01】
The theme is :
Disorderly numbered as 1-n The staff of our company arrange the superior and subordinate ,
Operation 1 : Give an employee a task C, Then the employee and his subordinate tasks are replaced by tasks C
Operation two : Ask an employee , Back to his mission
Explanation :
Give an employee a task , Then his group will change , Think of the interval modification of the line segment tree , But this is for one person , It's not an interval operation , If you can put the “ Point ” The operation becomes “ Interval ” The operation responsibility problem is transformed into interval modification and single point query , Here dfs The order maps the points of the original state to a line
dfs order :
Find a spot without a father
Find out his l and r, Add one every time you enter , Return without
No 1 2 3 4 5
Left end point 4 1 3 5 2
Right endpoint 4 5 5 5 2
namely 2 He went to the left at No 1, Right end to 5
Single point query :
Inquire about x, It can be understood as a query l[x] or r[x]( Subordinates are in line with their own work )
Interval modification :
For example, the picture above changes 2 That is to change 1,5
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+90; 4 const int inf=1e9+90; 5 #define eps 1e-10 6 #define forn(i,n) for(int i=0;i<n;i++) 7 #define form(i,n) for(int i=1;i<=n;i++) 8 typedef long long ll ; 9 typedef unsigned long long ull ; 10 #define ls l,mid,p<<1 11 #define rs mid+1,r,p<<1|1 12 int a[N]; 13 int n,m,root,rt; 14 int to[N],ver[N],h[N],tot; 15 char c[2]; 16 void add(int x,int y){ 17 to[++tot]=h[x]; 18 ver[tot]=y; 19 h[x]=tot; 20 } 21 struct Node{ 22 int l,r; 23 ll sum; 24 }t[N<<2]; 25 int ml[N],mr[N]; 26 void dfs(int x){ 27 // When I came in +1, 28 ml[x]=++rt; 29 for(int i=h[x];~i;i=to[i]){ 30 dfs(ver[i]); 31 } 32 mr[x]=rt;// You don't need to go back +1 33 } 34 void pd(int p){ 35 if(t[p].sum!=-1){ 36 t[p<<1].sum=t[p<<1|1].sum=t[p].sum; 37 t[p].sum=-1; 38 } 39 } 40 void build(int l,int r,int p){ 41 if(l==r){ 42 t[p].l=t[p].r=l; 43 t[p].sum=-1; 44 return; 45 } 46 t[p]={l,r,-1}; 47 int mid=l+r>>1; 48 build(l,mid,p<<1); 49 build(mid+1,r,p<<1|1); 50 } 51 void modify(int l,int r,int c,int p){ 52 if(l<=t[p].l&&t[p].r<=r){ 53 t[p].sum=c; 54 return; 55 } 56 pd(p); 57 int mid=t[p].l+t[p].r>>1; 58 if(l<=mid)modify(l,r,c,p<<1); 59 if(r>mid)modify(l,r,c,p<<1|1); 60 } 61 int query(int x,int p){ 62 if(t[p].l==t[p].r)return t[p].sum; 63 pd(p); 64 int mid=t[p].l+t[p].r>>1; 65 int ans=-1; 66 if(x<=mid)ans=query(x,p<<1); 67 else ans=query(x,p<<1|1); 68 return ans; 69 } 70 int main(){ 71 // freopen("in.txt","r",stdin); 72 // freopen("out.txt","w",stdout); 73 int T,x,y; 74 cin>>T; 75 form(k,T){ 76 printf("Case #%d:\n",k); 77 scanf("%d",&n); 78 memset(a,0,sizeof(a)); 79 memset(h,-1,sizeof(h)); 80 tot=0,rt=0; 81 forn(i,n-1) { 82 scanf("%d%d", &x, &y); 83 add(y,x); 84 a[x] = 1; 85 } 86 form(i,n){ 87 if(!a[i]){ 88 root=i; 89 break; 90 } 91 } 92 scanf("%d",&m); 93 dfs(root); 94 build(1,n,1); 95 forn(i,m){ 96 scanf("%s",c); 97 if(c[0]=='C'){ 98 scanf("%d",&x); 99 printf("%d\n",query(ml[x],1)); 100 }else{ 101 scanf("%d%d",&x,&y); 102 modify(ml[x],mr[x],y,1); 103 } 104 } 105 } 106 }
版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World