首页 > 代码库 > HDU 4973 A simple simulation problem 线段树
HDU 4973 A simple simulation problem 线段树
比赛的时候写跪了……赛后拿数据对比才发现,一个地方的判断条件的顺序写反了…… 真是结结实实的坑了队友一把。当时我可以全程都在想这个题,并且有十足的把握想法是对的。
题意:
最开始有n种不同细胞各一个排成一排。有两种操作:
1. 使区间[l, r]里面的细胞加倍,并相应往后移动。
2. 求区间[l, r]中相同细胞数量的最大值。
对于每次2操作,输出相应的值。
思路:
因为无论怎么加倍,相同的细胞总是在连续的一段。所以我们可以维护每一种细胞的数量,然后通过前缀和来知道这种细胞所在位置的开始点和结束点。这样,我们就可以很快的维护1操作了。然后前缀和可以用线段树来维护。本来树状数组来维护前缀和更简单的。但是因为查询前缀和与其他操作是一起的。所以2操作不太好实现。
对于每个操作,我们可以用类似二分前缀和的方法求出区间的两个端点在哪段。中间的段也就必然在其中了。另外,两段的段可能区间不是完全在段中,所以要特殊处理。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cstdlib> 5 #include <string> 6 #include <algorithm> 7 #include <vector> 8 #include <map> 9 #include <set> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <ctime> 14 #include <functional> 15 #include <cctype> 16 17 using namespace std; 18 19 #define LS p<<1, l, m 20 #define RS p<<1|1, m+1, r 21 22 typedef __int64 ll; 23 24 const int MAXN = (int) 5e4+55; 25 26 ll sum[MAXN<<2], MAX[MAXN<<2]; 27 int lazy[MAXN<<2]; 28 29 inline void pushUp(int p) { 30 sum[p] = sum[p<<1]+sum[p<<1|1]; 31 MAX[p] = max(MAX[p<<1], MAX[p<<1|1]); 32 } 33 34 inline void pushDown(int p) { 35 if (lazy[p]>0) { 36 sum[p<<1] <<= lazy[p]; 37 sum[p<<1|1] <<= lazy[p]; 38 MAX[p<<1] <<= lazy[p]; 39 MAX[p<<1|1] <<= lazy[p]; 40 lazy[p<<1] += lazy[p]; 41 lazy[p<<1|1] += lazy[p]; 42 lazy[p] = 0; 43 } 44 } 45 46 void build(int p, int l, int r) { 47 if (l==r) { 48 sum[p] = 1; 49 MAX[p] = 1; 50 return ; 51 } 52 int m = (l+r)>>1; 53 build(LS); 54 build(RS); 55 lazy[p] = 0; 56 pushUp(p); 57 } 58 59 void update(int p, int l, int r, ll x, ll L, ll R) { //x是当前点的起始坐标 60 //这个区间是 [x, x+sum[p]-1] 61 if (L<=x&&(x+sum[p]-1)<=R) { 62 sum[p] <<= 1; 63 MAX[p] <<= 1; 64 lazy[p]++; 65 return ; 66 } 67 if (l==r) { 68 if (x<=L) { //左端点在这里 69 sum[p] += min(x+sum[p]-1, R)-L+1; 70 } else { 71 sum[p] += R-x+1; 72 } 73 MAX[p] = sum[p]; 74 return ; 75 } 76 77 pushDown(p); 78 int m = (l+r)>>1; 79 ll M = x+sum[p<<1]-1; 80 if (L<=M) update(LS, x, L, R); 81 if (M< R) update(RS, M+1, L, R); 82 pushUp(p); 83 } 84 85 ll query(int p, int l, int r, ll x, ll L, ll R) { 86 if (L<=x&&(x+sum[p]-1)<=R) { 87 return MAX[p]; 88 } 89 if (l==r) { 90 if (x<=L) { 91 return min(R, x+sum[p]-1)-L+1; 92 } else { 93 return R-x+1; 94 } 95 } 96 97 pushDown(p); 98 int m = (l+r)>>1; 99 ll M = x+sum[p<<1]-1;100 ll res = 0;101 if (L<=M) res = max(res, query(LS, x, L, R));102 if (M <R) res = max(res, query(RS, M+1, L, R));103 return res;104 }105 106 int N, Q;107 char str[10];108 109 void solve() {110 ll L, R;111 scanf("%d%d", &N, &Q);112 build(1, 1, N);113 for (int i = 0; i < Q; i++) {114 scanf("%s%I64d%I64d", str, &L, &R);115 if (‘D‘==str[0]) {116 update(1, 1, N, 1, L, R);117 } else {118 printf("%I64d\n", query(1, 1, N, 1, L, R));119 }120 }121 }122 123 int main() {124 #ifdef Phantom01125 freopen("HDU4973.in", "r", stdin);126 freopen("my4973.out", "w", stdout);127 #endif // Phantom01128 129 int T;130 scanf("%d", &T);131 132 for (int i = 1; i<= T; i++) {133 printf("Case #%d:\n", i);134 solve();135 }136 137 return 0;138 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。