设为首页 加入收藏

TOP

ZOJ 3324 Machine
2015-07-20 18:07:23 来源: 作者: 【大 中 小】 浏览:5次
Tags：ZOJ 3324 Machine

题意：

一段区间最开始元素都是0 每次操作可以令一段连续区间+1或-1（在加过的前提下才能减） 每次操作输出整段区间有多少段连续的0


思路：

一看区间操作首先考虑线段树 本题n比较大 但是操作数很小 而且每次操作最多影响一段区间（可用两个数字表示区间头尾） 那么就想到了离散化

我和网上题解的离散方式不同 我的更暴力更无脑- -b

为了保证区间连续性 不能只在线段树节点上记录 1 2 4 7 10 等这样类似的离散值 应该这样表示：

1（0-0） 2（1-1） 3（2-2） 4（3-3） 5（4-4） 6（5-6） 7（7-7） 8（8-9） 9（10-10） 10（11-（n-1））

为了构成这样的序列 我在离散化的时候每次不仅考虑x这个值 还考虑了x-1和x+1 这样就保证了连续（见代码）

然后建树 树上节点中cnt表示区间连续0的段数 val描述该区间被移动的操作 lflag表示区间左边的高度 同理rflag

这里lflag的定义比较奇怪 不能单单用bool表示是否被移动 这里就需要加深理解线段树的“延迟更新”！

因为区间操作[l,r]一旦找到对应位置就不再向叶子节点递归了 也可以这样理解 更新操作在这里被截断了！

这时我们可以说val表示该区间所有截断的更新操作在此区间的影响 那么 lflag = lson.lflag + val 了

这样做可以避免down引起的问题 比如：

0-3（+1） 3-3（+1） 这时0-3的操作就被down下去了 那么0-3（-1）就会使区间的val变成-1而不是一部分为0

这也是定义lflag表示高度的原因


PS：

说说可能不太清晰 自己写几次WA就能体验了… 话说这还是小学弟给我指出的错误 后生可畏啊！


代码：

#include
  
   
#include
   
     #include
    
      #include
      #include
      
        using namespace std; #define N 209010 #define L(x) (x<<1) #define R(x) ((x<<1)|1) #define Mid(x,y) ((x+y)>>1) struct input { char p[4]; int l, r; } in[N]; struct node { int l, r, val, cnt, lflag, rflag; } tree[N * 4]; map
       
         hash; int a[N]; int n, m, T, t; void init(int l, int r, int i) { tree[i].l = l; tree[i].r = r; tree[i].val = tree[i].lflag = tree[i].rflag = 0; tree[i].cnt = 1; if (l == r) return; int mid = Mid(l,r); init(l, mid, L(i)); init(mid + 1, r, R(i)); } void up(int i) { if (tree[i].val == 0) { if (tree[i].l == tree[i].r) tree[i].cnt = 1; else { tree[i].cnt = tree[L(i)].cnt + tree[R(i)].cnt; if (!tree[L(i)].rflag && !tree[R(i)].lflag) tree[i].cnt--; } } else tree[i].cnt = 0; } void update(int l, int r, int i, int key) { if (l == tree[i].l && r == tree[i].r) { tree[i].val += key; tree[i].lflag += key; tree[i].rflag += key; up(i); return; } int mid = Mid(tree[i].l,tree[i].r); if (r <= mid) update(l, r, L(i), key); else if (l > mid) update(l, r, R(i), key); else { update(l, mid, L(i), key); update(mid + 1, r, R(i), key); } tree[i].lflag = tree[L(i)].lflag + tree[i].val; tree[i].rflag = tree[R(i)].rflag + tree[i].val; up(i); } int main() { int i, len, key, l, r, f; scanf("%d", &T); for (t = 1; t <= T; t++) { scanf("%d%d", &n, &m); len = 0; for (i = 1; i <= m; i++) { scanf("%s %d %d", in[i].p, &in[i].l, &in[i].r); a[len++] = in[i].l; a[len++] = max(0, in[i].l - 1); a[len++] = min(n - 1, in[i].l + 1); a[len++] = in[i].r; a[len++] = max(0, in[i].r - 1); a[len++] = min(n - 1, in[i].r + 1); } sort(a, a + len); hash.clear(); for (i = 0, f = 1; i < len; i++) if (i == 0 || a[i] != a[i - 1]) hash[a[i]] = f++; init(1, f - 1, 1); printf("Case #%d:\n", t); for (i = 1; i <= m; i++) { if (in[i].p[0] == 'p') key = 1; else key = -1; l = hash[in[i].l]; r = hash[in[i].r]; update(l, r, 1, key); cout << tree[1].cnt << endl; } } return 0; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：POJ3264――Balanced Lineup（线.. 下一篇：HDU4570 Multi-bit Trie 区间DP

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: