首页 > 代码库 > Light OJ 1411 Rip Van Winkle`s Code 线段树成段更新
Light OJ 1411 Rip Van Winkle`s Code 线段树成段更新
题目来源:Light OJ 1411 Rip Van Winkle`s Code
题意:3中操作 1种查询 求区间和 其中每次可以把一段区间从左到右加上1,2,3,。。。或者从右到左加上。。。3,2,1 或者把某个区间的数都置为v
思路:我是加了6个域
add是这段区间每个数都要加上add add是这么来的 对与123456。。。这个等差数列 可能要分为2个区间 那么我就分成123和123 两个右边的等差数列每个数还应该加上3 所以右区间add加3
v是这个区间都要置为v 他的优先级最高
b是代表这个区间有多少个递增的等差数列
c是代表这个区间有多少个递减的等差数列
sum是区间和
f为真说明要执行C 因为v可以是正和负还可以是0
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 250010; typedef long long LL; struct node { LL sum, add, v, b, c; bool f; }a[maxn<<2]; void build(int l, int r, int rt) { a[rt].sum = 0; a[rt].add = 0; a[rt].b = 0; a[rt].c = 0; a[rt].f = false; if(l == r) return; int m = (l + r) >> 1; build(l, m, rt<<1); build(m+1, r, rt<<1|1); } void pushdown(int rt, int l, int r) { LL k = (LL)(r-l+1); //printf("%d %d %lld\n", l, r, a[rt].v); if(a[rt].f) { a[rt<<1].sum = (LL)a[rt].v*(k-(k>>1)); a[rt<<1|1].sum = (LL)a[rt].v*(k>>1); a[rt<<1].v = a[rt<<1|1].v = a[rt].v; a[rt<<1].f = a[rt<<1|1].f = true; a[rt].f = false; a[rt<<1].b = a[rt<<1|1].b = 0; a[rt<<1].c = a[rt<<1|1].c = 0; a[rt<<1].add = a[rt<<1|1].add = 0; } LL s1 = (k-(k>>1)); LL s2 = (k>>1); if(a[rt].b) { a[rt<<1].sum += (LL)a[rt].b*(1+s1)*s1/2; a[rt<<1|1].sum += (LL)a[rt].b*(1+s2)*s2/2+(LL)s2*s1*a[rt].b; a[rt<<1].b += a[rt].b; a[rt<<1|1].b += a[rt].b; a[rt<<1|1].add += (LL)s1*a[rt].b; a[rt].b = 0; } if(a[rt].c) { a[rt<<1].sum += (LL)a[rt].c*(1+s1)*s1/2+(LL)s2*s1*a[rt].c; a[rt<<1|1].sum += (LL)a[rt].c*(1+s2)*s2/2; a[rt<<1].c += a[rt].c; a[rt<<1|1].c += a[rt].c; a[rt<<1].add += (LL)s2*a[rt].c; a[rt].c = 0; } if(a[rt].add) { a[rt<<1].sum += (LL)a[rt].add*(k-(k>>1)); a[rt<<1|1].sum += (LL)a[rt].add*(k>>1); a[rt<<1].add += a[rt].add; a[rt<<1|1].add += a[rt].add; a[rt].add = 0; } } void update(int x, int y, int l, int r, int rt, LL add, LL v, char c) { //puts("we"); if(l == x && r == y) { if(c == 'A') { /*if(a[rt].f) { a[rt].sum = (LL)(r-l+1)*v; //a[rt].f = false; }*/ a[rt].sum += (LL)(r-l+1)*(r-l+1+1)/2; a[rt].b++; a[rt].sum += (LL)add*(r-l+1); a[rt].add += add; //printf("%d %d %d %lld\n", l, r, a[rt].b, a[rt].sum); } else if(c == 'B') { /*if(a[rt].f) { a[rt].sum = (LL)(r-l+1)*v; //a[rt].f = false; }*/ a[rt].sum += (LL)(r-l+1)*(r-l+1+1)/2; a[rt].c++; a[rt].sum += (LL)add*(r-l+1); a[rt].add += add; } else if(c == 'C') { a[rt].f = true; a[rt].add = 0; a[rt].sum = (LL)(r-l+1)*v; a[rt].b = 0; a[rt].c = 0; a[rt].v = v; } return; } int m = (l + r) >> 1; pushdown(rt, l, r); if(y <= m) { update(x, y, l, m, rt<<1, add, v, c); } else if(x > m) { update(x, y, m+1, r, rt<<1|1, add, v, c); } else { if(c == 'A') { update(x, m, l, m, rt<<1, add, v, c); update(m+1, y, m+1, r, rt<<1|1, add+(m-x+1), v, c); } else if(c == 'B') { update(x, m, l, m, rt<<1, add+(y-m), v, c); update(m+1, y, m+1, r, rt<<1|1, add, v, c); } else if(c == 'C') { //puts("as"); update(x, m, l, m, rt<<1, add, v, c); update(m+1, y, m+1, r, rt<<1|1, add, v, c); } } a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum; } LL query(int x, int y, int l, int r, int rt) { if(x == l && y == r) { //printf("**%d %d %lld\n", l, r, a[rt].sum); return a[rt].sum; } pushdown(rt, l, r); int m = (l + r) >> 1; LL ans = 0; if(y <= m) ans += query(x, y, l, m, rt<<1); else if(x > m) ans += query(x, y, m+1, r, rt<<1|1); else ans = query(x, m, l, m, rt<<1) + query(m+1, y, m+1, r, rt<<1|1); a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum; return ans; } int main() { int cas = 1; int T; scanf("%d", &T); while(T--) { int n = 250000; int q; scanf("%d", &q); printf("Case %d:\n", cas++); build(1, n, 1); while(q--) { char s[10]; scanf("%s", s); if(s[0] == 'A') { int x, y; scanf("%d %d", &x, &y); update(x, y, 1, n, 1, 0, 0, 'A'); } else if(s[0] == 'B') { int x, y; scanf("%d %d", &x, &y); update(x, y, 1, n, 1, 0, 0, 'B'); } else if(s[0] == 'C') { int x, y; LL w; scanf("%d %d %lld", &x, &y, &w); update(x, y, 1, n, 1, 0, w, 'C'); } else { int x, y; scanf("%d %d", &x, &y); printf("%lld\n", query(x, y, 1, n, 1)); } } } return 0; } /* 10 B 1 4 A 1 4 S 2 2 B 1 3 C 1 4 1 B 1 4 C 3 3 3 A 2 3 S 2 3 B 3 3 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。