首页 > 其他 > 详细

I - Tunnel Warfare HDU - 1540 线段树最大连续区间

时间:2019-01-24 10:26:09      阅读:190      评论:0      收藏:0      [点我收藏+]

题意  :一段区间  操作1 切断点 操作2 恢复最近切断的一个点 操作3 单点查询该点所在最大连续区间

思路:  主要是push_up :  设区间x 为母区间  x<<1 ,x<<1|1分别为两个子区间  

  x的左端连续子段和 :当x<<1区间没有断开 也就是 x<<1 的最大连续子段ml ==tree[x<<1].r-tree[x<<1].l+1 等于区间长度时 x左端连续字段和tree[x].ll=tree[x<<1].ll+tree[x<<1|1].ll如果断开了直接就等于左子区间

最大子段和 

x的右端连续子区间同理

x的最大连续子区间   x的最大连续子区间只可能在  1. 以x的Mid为分界   左子区最大连续和  2.右子区最大连续和 3.横跨mid  前两个分别直接区子区间的就能 第三个长度等于tree[x<<1].rl+tree[x<<1|1].ll 取三个里面最大即可

 

查询: 如果查询的点t 当前所查询的区间tree[x].ml最大连续子段和直接等于0 或者 tree[x].l==tree[x].r时 或者  区间是完整的 也就是tree[x].ml=tree[x].r-tree[x].l+1 时都可以直接返回

不然  令mid=l+r>>1  如果要查询的点t 在mid左边(包括Mid)那么当t 位于区间tree[x<<1]的从右开始的最长连续区间时  还可以把与其相邻的子区间tree[x<<1|1].ll接上  如果不位于 直接往下面查即可  

如果要查询的点t 在mid右边(不包括Mid)同理

记得循环输入

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=50000;
 4 struct Node{
 5     int l,r;
 6     long long  ll,rl,ml;
 7 }tree[maxn*4];
 8 void build(int x,int l,int r){
 9     tree[x].l=l,tree[x].r=r;
10     tree[x].ll=tree[x].rl=tree[x].ml=r-l+1;
11     if(l==r)return ;
12     else {
13         int mid=l+r>>1;
14         build(x<<1,l,mid);
15         build(x<<1|1,mid+1,r);
16     }
17 }
18 void push_up(int x){
19         tree[x].ll=tree[x<<1].ll;
20         tree[x].rl=tree[x<<1|1].rl;
21         tree[x].ml=max(tree[x<<1].ml,tree[x<<1|1].ml);
22         tree[x].ml=max(tree[x].ml,tree[x<<1].rl+tree[x<<1|1].ll);
23         if(tree[x<<1].ll==tree[x<<1].r-tree[x<<1].l+1)tree[x].ll+=tree[x<<1|1].ll;
24         if(tree[x<<1|1].rl==tree[x<<1|1].r-tree[x<<1|1].l+1)tree[x].rl+=tree[x<<1].rl;
25 }
26 void update(int x,int t,int val){
27     if(tree[x].l==tree[x].r){
28         if(val==1)tree[x].ll=tree[x].rl=tree[x].ml=1;
29         else tree[x].ll=tree[x].rl=tree[x].ml=0;
30         return ;
31     }
32     else {
33         int mid=tree[x].l+tree[x].r>>1;
34         if(t<=mid)update(x<<1,t,val);
35         else update(x<<1|1,t,val);
36         push_up(x);
37     }
38 }
39 long long  query(int x,int t){
40     if(tree[x].l==tree[x].r||tree[x].ml==0||tree[x].ml==tree[x].r-tree[x].l+1){
41         return tree[x].ml;
42     }
43     else {
44         int mid=tree[x].l+tree[x].r>>1;
45         if(t<=mid){
46             if(t>=tree[x<<1].r-tree[x<<1].rl+1){
47                 return query(x<<1,t)+query(x<<1|1,mid+1);
48             }
49             else return query(x<<1,t);
50         }
51         else {
52             if(t<=tree[x<<1|1].l+tree[x<<1|1].ll-1){
53                 return query(x<<1|1,t)+query(x<<1,mid);
54             }
55             else return query(x<<1|1,t);
56         }    
57     }
58 
59 }
60 int Q[maxn];
61 int main(){
62     int n,q;
63     while(scanf("%d%d",&n,&q)==2){
64     build(1,1,n);
65     int t=1;
66     //int last=0;
67     int top=0;
68     for(int i=1;i<=q;i++){
69         char s[10];
70         scanf("%s",s);
71         if(s[0]==D){
72             scanf("%d",&t);
73             Q[top++]=t;
74             update(1,t,0);
75         }
76         if(s[0]==Q){
77             scanf("%d",&t);
78             printf("%lld\n",query(1,t));
79         }
80         if(s[0]==R){
81             update(1,Q[--top],1);
82         }
83     }
84     }
85     return 0;
86 }

 

I - Tunnel Warfare HDU - 1540 线段树最大连续区间

原文:https://www.cnblogs.com/ttttttttrx/p/10312237.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!