脚本宝典收集整理的这篇文章主要介绍了HDU-1540 Tunnel Warfare(区间连续点长度),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
http://acm.hdu.edu.cn/showproblem.php?pid=1540
Time LimIT: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
7 9 D 3 D 6 D 5 Q 4 Q 5 R Q 4 R Q 4
1 0 2 4
题意:
一条线上有n个点,一共有m个操作,D x是破坏这个点,Q x是表示查询以x所在的最长的连续的点的个数,R是恢复上一次破坏的点。
这题有点坑,注意是多样例输入
解法一(421ms、4.3MB):
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <stack> 11 #include <map> 12 #include <math.h> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 const int maxn=1e5+10; 17 using namespace std; 18 19 struct node 20 { 21 int l; 22 int r; 23 int ls;//ls为左端最大连续区间 24 int rs;//rs为右端最大连续区间 25 int ms;//ms区间内最大连续区间 26 }SegTree[50005<<2]; 27 28 int n,m,x; 29 stack<int> sk; 30 31 void PushUp(int rt) 32 { 33 SegTree[rt].ls=SegTree[rt<<1].ls;//左区间 34 SegTree[rt].rs=SegTree[rt<<1|1].rs;//右区间 35 //父亲区间内的最大区间必定是,左子树最大区间,右子树最大区间,左右子树合并的中间区间,三者中最大的区间值 36 SegTree[rt].ms=max(max(SegTree[rt<<1].ms,SegTree[rt<<1|1].ms),SegTree[rt<<1].rs+SegTree[rt<<1|1].ls); 37 if(SegTree[rt<<1].ms==SegTree[rt<<1].r-segTree[rt<<1].l+1)//左子树区间满了的话,父亲左区间要加上右孩子的左区间 38 SegTree[rt].ls+=SegTree[rt<<1|1].ls; 39 if(SegTree[rt<<1|1].ms==SegTree[rt<<1|1].r-SegTree[rt<<1|1].l+1)//同理 40 SegTree[rt].rs+=SegTree[rt<<1].rs; 41 } 42 43 void Build(int l,int r,int rt) 44 { 45 SegTree[rt].l=l; 46 SegTree[rt].r=r; 47 SegTree[rt].ls=SegTree[rt].rs=SegTree[rt].ms=r-l+1; 48 if(l==r) 49 return ; 50 int mid=(l+r)>>1; 51 Build(l,mid,rt<<1); 52 Build(mid+1,r,rt<<1|1); 53 } 54 55 void Update(int L,int f,int rt) 56 { 57 int l=SegTree[rt].l; 58 int r=SegTree[rt].r; 59 if(l==r) 60 { 61 if(f==1) 62 SegTree[rt].ls=SegTree[rt].rs=SegTree[rt].ms=1;//修复 63 else if(f==0) 64 SegTree[rt].ls=SegTree[rt].rs=SegTree[rt].ms=0;//破坏 65 return ; 66 } 67 int mid=(l+r)>>1; 68 if(L<=mid) 69 Update(L,f,rt<<1); 70 else if(L>mid) 71 Update(L,rt<<1|1); 72 PushUp(rt); 73 } 74 75 int Query(int L,int rt) 76 { 77 int l=SegTree[rt].l; 78 int r=SegTree[rt].r; 79 if(l==r||SegTree[rt].ms==0||SegTree[rt].ms==r-l+1)//到了叶子节点或者该访问区间为空或者已满都不必要往下走了 80 return SegTree[rt].ms; 81 int mid=(l+r)>>1; 82 if(L<=mid) 83 { 84 //因为L<=mid,看左子树,SegTree[rt<<1].r-SegTree[rt<<1].rs+1代表左子树右边连续区间的左边界值,如果t在左子树的右区间内,则要看右子树的左区间有多长并返回 85 if(L>=SegTree[rt<<1].r-SegTree[rt<<1].rs+1) 86 return Query(L,rt<<1)+Query(mid+1,rt<<1|1); 87 else 88 return Query(L,rt<<1);//如果不在左子树的右边界区间内,则只需要看左子树 89 } 90 else 91 { 92 if(L<=SegTree[rt<<1|1].l+SegTree[rt<<1|1].ls-1)//同理 93 return Query(L,rt<<1|1)+Query(mid,rt<<1); 94 else 95 return Query(L,rt<<1|1); 96 } 97 } 98 int main() 99 { 100 while(~scanf("%d %d",&n,&m)) 101 { 102 Build(1,n,1); 103 char c[5]; 104 while(!sk.empty()) 105 sk.pop(); 106 while(m--) 107 { 108 scanf("%s",c); 109 if(c[0]==‘D‘) 110 { 111 scanf("%d",&x); 112 sk.push(x); 113 Update(x,0,1); 114 } 115 else if(c[0]==‘Q‘) 116 { 117 scanf("%d",&x); 118 printf("%d\n",Query(x,1)); 119 } 120 else if(c[0]==‘R‘) 121 { 122 if(!sk.empty()) 123 { 124 x=sk.top(); 125 sk.pop(); 126 Update(x,1,1); 127 } 128 } 129 } 130 } 131 return 0; 132 }
解法二(483ms、3.8MB):
原文地址:https://blog.csdn.net/chudongfang2015/article/details/52133243
只不过每个点最初的最大最小值不是他们自身,村子如果没有被摧毁,最大、最小值是分别用0(求最大值时)和n+1(求最小值时)代替的(下方会有所解释)。
当村子被摧毁时,更新该结点最大最小值为该村子本身编号。
我们求的区间最大值时就是在区间[1,x]中查找被摧毁的村子中编号最大的一个,求区间最小值时就是在区间[x,n]中查找被摧毁的村子中编号最小的一个。
下面给出一些例子(红色代表被摧毁)
这里假设其为 1 2 3 4 5 6 7
则如果 其中有若干个村子被毁了,如果要求第4个村子
只需求出来 1->4区间中被毁村子的最大值(2),
和 4->7 区间中被毁村子的最小值(5),
根据两者求出村子的连续区间,即 2->5 所以其村子连续个数 为 5-2-1 = 2
即mmin - mmax -1(正常求区间长度为r-l+1,因为这个区间内左右端点均为被摧毁的点,故长度-2,最终为r-l+1-2即r-l-1)
特殊情况: 如果1 2 3 4 5 6 7 求2的连续区间 ,其最大为2,最小也为2(2-2-1=-1,应为零,故当成特殊情况对待,则其连续个数为 0 )
这里注意,对于没有被摧毁的村子,不加入到线段数节点,而是分别用0(求最大值时)和n+1(求最小值时)代替,
代表被摧毁的村子最小值为0,最大值为n+1,而不存在这两个编号的村子,故相当于这段区间无被摧毁的村子。
这样能保证,其不影响加入村子的求极值,而且最其在没有村子被摧毁的情况下,也能正确的求出解。
例子: 1 2 3 4 5 6 7
求村子3的连续区间,这里1->3 maxx为0 ; 3->n minn为4
所以其连续空间为4-0-1 =3 为正解
可以自己再试其他例子
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <stack> 11 #include <map> 12 #include <math.h> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 //const double PI=acos(-1); 17 const int maxn=1e5+10; 18 using namespace std; 19 //ios::sync_with_stdio(false); 20 // cin.tie(NULL); 21 22 struct node 23 { 24 int l; 25 int r; 26 int MAX; 27 int MIN; 28 }SegTree[50005<<2]; 29 30 int n,x; 31 stack<int> sk; 32 33 void PushUp(int rt) 34 { 35 SegTree[rt].MAX=max(SegTree[rt<<1].MAX,SegTree[rt<<1|1].MAX); 36 SegTree[rt].MIN=min(SegTree[rt<<1].MIN,SegTree[rt<<1|1].MIN); 37 } 38 39 void Build(int l,int rt)//建树 40 { 41 SegTree[rt].l=l; 42 SegTree[rt].r=r; 43 if(l==r) 44 { 45 SegTree[rt].MAX=0; 46 SegTree[rt].MIN=n+1; 47 return ; 48 } 49 int mid=(l+r)>>1; 50 Build(l,rt<<1); 51 Build(mid+1,rt<<1|1); 52 PushUp(rt); 53 } 54 55 void Update(int L,int T,int rt)//更新 56 { 57 int l=SegTree[rt].l; 58 int r=SegTree[rt].r; 59 if(l==r) 60 { 61 if(T==-1)//-1表示恢复,如果恢复,就把对应的值改为0或n+1 62 { 63 SegTree[rt].MAX=0; 64 SegTree[rt].MIN=n+1; 65 } 66 else 67 SegTree[rt].MAX=SegTree[rt].MIN=T; 68 return ; 69 } 70 int mid=(l+r)>>1; 71 if(L<=mid) 72 Update(L,T,rt<<1); 73 else 74 Update(L,rt<<1|1); 75 PushUp(rt); 76 } 77 78 int Query_MAX(int L,int R,int rt)//查找区间最大值 79 { 80 int l=SegTree[rt].l; 81 int r=SegTree[rt].r; 82 if(L<=l&&R>=r) 83 { 84 return SegTree[rt].MAX; 85 } 86 int MAX=0; 87 int mid=(l+r)>>1; 88 if(L<=mid) 89 MAX=max(MAX,Query_MAX(L,R,rt<<1)); 90 if(R>mid) 91 MAX=max(MAX,rt<<1|1)); 92 return MAX; 93 } 94 95 int Query_MIN(int L,int rt)//查找区间最小值 96 { 97 int l=SegTree[rt].l; 98 int r=SegTree[rt].r; 99 if(L<=l&&R>=r) 100 { 101 return SegTree[rt].MIN; 102 } 103 int MIN=INF; 104 int mid=(l+r)>>1; 105 if(L<=mid) 106 MIN=min(MIN,Query_MIN(L,rt<<1)); 107 if(R>mid) 108 MIN=min(MIN,rt<<1|1)); 109 return MIN; 110 } 111 112 int main() 113 { 114 while(~scanf("%d %d",&m)) 115 { 116 Build(1,1); 117 char c[5]; 118 while(!sk.empty()) 119 sk.pop(); 120 while(m--) 121 { 122 scanf("%s",c); 123 if(c[0]==‘D‘) 124 { 125 scanf("%d",&x); 126 sk.push(x); 127 Update(x,x,1);//更新线段数的值,把x对应的值更新成x 128 } 129 else if(c[0]==‘Q‘) 130 { 131 scanf("%d",&x); 132 int mmax,mmin; 133 mmax=Query_MAX(1,1); 134 mmin=Query_MIN(x,1); 135 if(mmax==mmin)//考虑特殊情况 136 printf("%d\n",0); 137 else 138 printf("%d\n",mmin-mmax-1); 139 } 140 else if(c[0]==‘R‘) 141 { 142 if(!sk.empty()) 143 { 144 x=sk.top(); 145 sk.pop(); 146 Update(x,-1,1);//如果恢复,就把对应的值改为0或n+1 147 } 148 } 149 } 150 } 151 return 0; 152 }
以上是脚本宝典为你收集整理的HDU-1540 Tunnel Warfare(区间连续点长度)全部内容,希望文章能够帮你解决HDU-1540 Tunnel Warfare(区间连续点长度)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。