12436 - Rip Van Winkle's Code

本文主要是介绍12436 - Rip Van Winkle's Code，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/********************* Author:fisty* Data:2014-11-5* uva12436* 线段树 成段更新* ****************/#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_N 250000
typedef long long ll;struct node{int l, r;bool flag;ll sum, add1, add2, valu, step;ll mid(){return l+(r - l) / 2;}ll len(){return r - l + 1;}void changeAB(ll a, ll b, ll k){add1 += a;add2 += b;step += k;sum += (a + b)*len()/2;}void changeC(ll a){valu = a; flag = 1;add1 = 0, add2 = 0;step = 0;sum = valu * len();}
}tree[250001 << 2];struct segtree{void down(ll k){if(tree[k].flag){tree[k<<1].changeC(tree[k].valu);tree[k<<1|1].changeC(tree[k].valu);tree[k].flag = 0;}if(tree[k].add1 || tree[k].add2 || tree[k].step){ll add1 = tree[k].add1, add2 = tree[k].add2;ll i = tree[k].step;ll mid = add1 + i * (tree[k<<1].len()-1);tree[k<<1].changeAB(add1, mid, i);tree[k<<1|1].changeAB(mid+i, add2, i);tree[k].add1 = 0;tree[k].add2 = 0;tree[k].step = 0;}}void build(ll l, ll r, ll k){tree[k].l = l; tree[k].r = r;tree[k].add1 = 0; tree[k].add2 = 0;tree[k].sum = 0; tree[k].valu = 0;tree[k].step = 0;if(l != r){ll  mid = tree[k].mid();build(l, mid, k<<1);build(mid+1 , r, k<<1|1);}}void update_AB(ll l, ll r, ll k, ll step){if(l <= tree[k].l && tree[k].r <= r){//所能更新的区域是[tree[k].l, tree[k].r];//但是需要更新的区域是[l,r];//在l上加1,故在tree[k].l这点加上的是tree[k].l-l+1，在tree[k].r加上的是tree[k].r-l+1int st, ed;if(step >= 0){st = tree[k].l - l + 1, ed = tree[k].r - l + 1;}else{st = r - tree[k].l + 1, ed = r - tree[k].r + 1;}tree[k].changeAB(st, ed, step);}else{down(k);       ll mid = tree[k].mid();if(l <= mid) update_AB(l, r, k<<1, step);if(r > mid) update_AB(l, r, k<<1|1, step);tree[k].sum = tree[k<<1].sum + tree[k<<1|1].sum;}}void update_C(ll l, ll r, ll k, ll valu){if(l <= tree[k].l && tree[k].r <= r){tree[k].changeC(valu);}else{down(k);ll mid = tree[k].mid();if(l <= mid) update_C(l, r, k<<1, valu);if(r > mid) update_C(l ,r, k<<1|1, valu);tree[k].sum = tree[k<<1].sum + tree[k<<1|1].sum;}}ll query(ll l, ll r, ll k){if(l <=tree[k].l && tree[k].r <= r){return tree[k].sum;}else{down(k);ll mid = tree[k].mid();ll sum1 = 0, sum2 = 0;if(l <= mid) sum1 = query(l, r, k<<1);if(r > mid) sum2 = query(l , r, k<<1|1);return sum1 + sum2;}}
}seg;
int main(){int t;while(scanf("%d", &t) != EOF){seg.build(1, MAX_N, 1);while(t--){char str[10];ll a, b;scanf("%s", str);if(str[0] == 'A'){scanf("%lld%lld", &a, &b);seg.update_AB(a, b, 1, 1);}else if(str[0] == 'B'){scanf("%lld%lld", &a, &b);seg.update_AB(a, b, 1, -1);}else if(str[0] == 'C'){ll val;scanf("%lld%lld%lld", &a, &b, &val);seg.update_C(a, b, 1, val);}else{scanf("%lld%lld", &a, &b);printf("%lld\n",seg.query(a, b, 1));}}}return 0;
}

这篇关于12436 - Rip Van Winkle's Code的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---