首页 > 代码库 > hdu1540-Tunnel Warfare （线段树区间合并）
hdu1540-Tunnel Warfare （线段树区间合并）
题意：n个村庄，有三种操作，D x 破坏位置为x的村庄，R 修复上一次被破坏的村庄，Q x 输出含有x村庄的连续村庄的最大个数。线段树搞之，区间合并。
ls[maxn]为当前节点左面的连续区间，rs[maxn]为当前节点左面的连续区间,ms[maxn]当前节点的最大连续区间。
1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cctype> 8 #include <cstdio> 9 #include <string> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 typedef unsigned long long ull; 17 typedef long long ll; 18 const int inf = 0x3f3f3f3f; 19 const double eps = 1e-8; 20 const int maxn = 5e4+10; 21 int ls[maxn<<2],ms[maxn<<2],rs[maxn<<2]; 22 stack<int>S; 23 void build(int l,int r,int pos) 24 { 25 ls[pos] = rs[pos] = ms[pos] = r - l + 1; 26 if (l == r) 27 return; 28 int mid = (l + r) >> 1; 29 build(l,mid,pos<<1); 30 build(mid+1,r,pos<<1|1); 31 } 32 void update(int l,int r,int pos,int x,int val) 33 { 34 if (l == r) 35 { 36 ls[pos] = rs[pos] = ms[pos] = val; 37 return; 38 } 39 int mid = (l + r) >> 1; 40 if (x <= mid) 41 update(l,mid,pos<<1,x,val); 42 if (x > mid) 43 update(mid+1,r,pos<<1|1,x,val); 44 ms[pos] = max(rs[pos<<1]+ls[pos<<1|1],max(ms[pos<<1],ms[pos<<1|1])); 45 ls[pos] = ls[pos<<1]; 46 rs[pos] = rs[pos<<1|1]; 47 if (mid-l+1==rs[pos<<1]) 48 ls[pos] += ls[pos<<1|1]; 49 if (r-mid==ls[pos<<1|1]) 50 rs[pos] += rs[pos<<1]; 51 } 52 int query(int l,int r,int pos,int x) 53 { 54 if (ms[pos] == r - l + 1 || !ms[pos] || l == r) 55 { 56 return ms[pos]; 57 } 58 int mid = (l + r) >> 1; 59 if (x <= mid) 60 { 61 if (x >= mid - rs[pos<<1] + 1) 62 return query(l,mid,pos<<1,x) + query(mid+1,r,pos<<1|1,mid+1); 63 else 64 return query(l,mid,pos<<1,x); 65 } 66 else 67 { 68 if (x <= mid+ls[pos<<1|1]) 69 return query(mid+1,r,pos<<1|1,x) + query(l,mid,pos<<1,mid); 70 else 71 return query(mid+1,r,pos<<1|1,x); 72 } 73 } 74 int main(void) 75 { 76 #ifndef ONLINE_JUDGE 77 freopen("in.txt","r",stdin); 78 #endif 79 int n,m; 80 while (~scanf ("%d%d",&n,&m)) 81 { 82 build(1,n,1); 83 char op[10]; 84 for (int i = 0; i < m; i++) 85 { 86 int x; 87 scanf ("%s",op); 88 if (op[0] == ‘D‘) 89 { 90 scanf ("%d",&x); 91 update(1,n,1,x,0); 92 S.push(x); 93 } 94 if (op[0] == ‘Q‘) 95 { 96 scanf ("%d",&x); 97 printf("%d\n",query(1,n,1,x)); 98 } 99 if (op[0] == ‘R‘)100 {101 if (!S.empty())102 {103 int tmp = S.top();104 S.pop();105 update(1,n,1,tmp,1);106 }107 }108 }109 while (!S.empty())110 S.pop();111 }112 return 0;113 }
hdu1540-Tunnel Warfare （线段树区间合并）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。