当前位置:网站首页>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
边栏推荐
- Python Jieba segmentation (stuttering segmentation), extracting words, loading words, modifying word frequency, defining thesaurus
- Arrangement of basic knowledge points
- 一篇文章带你了解SVG 渐变知识
- 開源一套極簡的前後端分離專案腳手架
- 一篇文章带你了解CSS 分页实例
- Windows 10 tensorflow (2) regression analysis of principles, deep learning framework (gradient descent method to solve regression parameters)
- Pollard's Rho algorithm
- 文件过多时ls命令为什么会卡住?
- Solve the problem of database insert data garbled in PL / SQL developer
- Interface pressure test: installation, use and instruction of siege pressure test
猜你喜欢
C#和C/C++混合编程系列5-内存管理之GC协同
Natural language processing - BM25 commonly used in search
每个大火的“线上狼人杀”平台,都离不开这个新功能
NLP model Bert: from introduction to mastery (1)
前端工程师需要懂的前端面试题(c s s方面)总结(二)
Construction of encoder decoder model with keras LSTM
Named entity recognition in natural language processing: tanford core LP ner (1)
Summary of common string algorithms
只有1个字节的文件实际占用多少磁盘空间
Summary of common algorithms of linked list
随机推荐
It's easy to operate. ThreadLocal can also be used as a cache
Interface pressure test: installation, use and instruction of siege pressure test
electron 實現檔案下載管理器
Three Python tips for reading, creating and running multiple files
Python基础数据类型——tuple浅析
I think it is necessary to write a general idempotent component
Introduction to quantitative investment and Trading (Python introduction to financial analysis)
keras model.compile Loss function and optimizer
Music generation through deep neural network
Shh! Is this really good for asynchronous events?
理解格式化原理
[Xinge education] poor learning host computer series -- building step 7 Simulation Environment
Uncle Bob: the software architecture is similar to a house. Object oriented is the structure of the house, and the water pipe is functional programming
Python saves the list data
6.1.2 handlermapping mapping processor (2) (in-depth analysis of SSM and project practice)
It is really necessary to build a distributed ID generation service
The road of C + + Learning: from introduction to mastery
DRF JWT authentication module and self customization
文件过多时ls命令为什么会卡住?
6.1.1 handlermapping mapping processor (1) (in-depth analysis of SSM and project practice)