当前位置:网站首页>Hdu3974 assign the task segment tree DFS order
Hdu3974 assign the task segment tree DFS order
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 // 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]所创,转载请带上原文链接,感谢
边栏推荐
- File download manager realized by electron
- 【字节跳动 秋招岗位开放啦】Ohayoo!放学别走,我想约你做游戏!!!
- An article taught you to download cool dog music using Python web crawler
- git远程库回退指定版本
- 2020-09-09:裸写算法:两个线程轮流打印数字1-100。
- 消息队列(MessageQueue)-分析
- Python basic variable type -- list analysis
- Open source a set of minimalist front and rear end separation project scaffold
- 2020-08-19:TCP是通过什么机制保障可靠性的?
- Top 5 Chinese cloud manufacturers in 2018: Alibaba cloud, Tencent cloud, AWS, telecom, Unicom
猜你喜欢
C# 调用SendMessage刷新任务栏图标(强制结束时图标未消失)
Swagger 3.0 brushes the screen every day. Does it really smell good?
What are PLC Analog input and digital input
统计项目代码行数
The AI method put forward by China has more and more influence. Tianda et al. Mined the development law of AI from a large number of literatures
面试官: ShardingSphere 学一下吧
事务的隔离级别与所带来的问题
华为Mate 40 系列搭载HMS有什么亮点?
How does filecoin's economic model and future value support the price of fil currency breaking through thousands
mongo 用户权限 登录指令
随机推荐
What are manufacturing and new automation technologies?
How does cglib implement multiple agents?
Application of restful API based on MVC
Using an example to understand the underlying processing mechanism of JS function
2020年第四届中国 BIM (数字建造)经理高峰论坛即将在杭举办
Share with Lianyun: is IPFs / filecoin worth investing in?
Contract trading system development | construction of smart contract trading platform
【学习】接口测试用例编写和测试关注点
Flink's datasource Trilogy 2: built in connector
事务的隔离级别与所带来的问题
python100例項
2020-09-04:函数调用约定了解么?
StickEngine-架构12-通信协议
How does filecoin's economic model and future value support the price of fil currency breaking through thousands
华为Mate 40 系列搭载HMS有什么亮点?
Zero basis to build a web search engine of its own
Those who have worked in China for six years and a million annual salary want to share these four points with you
行为型模式之备忘录模式
Ronglian completed US $125 million f round financing
Multi robot market share solution