当前位置:网站首页>hdu3974 Assign the task線段樹 dfs序
hdu3974 Assign the task線段樹 dfs序
2020-11-06 21:13:00 【itread01】
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 //進來的時候+1, 28 ml[x]=++rt; 29 for(int i=h[x];~i;i=to[i]){ 30 dfs(ver[i]); 31 } 32 mr[x]=rt;//返回的時候不需要+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]所创,转载请带上原文链接,感谢
https://www.itread01.com/content/1604668082.html
边栏推荐
- Free patent download tutorial (HowNet, Espacenet)
- Classical dynamic programming: complete knapsack problem
- Unity性能优化整理
- It's easy to operate. ThreadLocal can also be used as a cache
- Analysis of etcd core mechanism
- Brief introduction of TF flags
- Summary of common string algorithms
- [actual combat of flutter] pubspec.yaml Configuration file details
- ES6学习笔记(五):轻松了解ES6的内置扩展对象
- 仅用六种字符来完成Hello World,你能做到吗?
猜你喜欢
Word segmentation, naming subject recognition, part of speech and grammatical analysis in natural language processing
Unity性能优化整理
一篇文章带你了解CSS3 背景知识
快速排序为什么这么快?
一篇文章带你了解CSS3图片边框
Linked blocking Queue Analysis of blocking queue
C + + and C + + programmers are about to be eliminated from the market
百万年薪,国内工作6年的前辈想和你分享这四点
FastThreadLocal 是什么鬼?吊打 ThreadLocal 的存在!!
ES6学习笔记(四):教你轻松搞懂ES6的新增语法
随机推荐
一篇文章带你了解CSS对齐方式
Three Python tips for reading, creating and running multiple files
Natural language processing - wrong word recognition (based on Python) kenlm, pycorrector
It is really necessary to build a distributed ID generation service
带你学习ES5中新增的方法
Introduction to Google software testing
【转发】查看lua中userdata的方法
一篇文章带你了解SVG 渐变知识
6.3 handlerexceptionresolver exception handling (in-depth analysis of SSM and project practice)
electron 實現檔案下載管理器
Arrangement of basic knowledge points
What if the front end doesn't use spa? - Hacker News
Mongodb (from 0 to 1), 11 days mongodb primary to intermediate advanced secret
游戏主题音乐对游戏的作用
NLP model Bert: from introduction to mastery (2)
Using NLP and ml to extract and construct web data
用一个例子理解JS函数的底层处理机制
Basic usage of GDB debugging
vue-codemirror基本用法:实现搜索功能、代码折叠功能、获取编辑器值及时验证
I think it is necessary to write a general idempotent component