首页 > 代码库 > 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 }
View Code