数据结构--线段树--维护等差数列--uva12436 Rip Van Winkle's Code

本文主要是介绍数据结构--线段树--维护等差数列--uva12436 Rip Van Winkle's Code，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

N=250000

op1. 区间[ql,qr] ql的位置+1,ql+1的位置+2。。。

op2. 区间[ql,qr] qr的位置+1,qr-1的位置+2。。。

op3.区间[ql,qr] 区间修改为x

op4.求区间和

大佬博客 https://blog.csdn.net/hei_nero/article/details/9798723

将梯形划分为左右区间的时候，相当于左区间维护小梯形，右区间维护区间add更新和小梯形

//uva12436
//线段树维护等差数列#include <cstdio>
#include <iostream>
using namespace std;
#define lc (rt << 1)
#define rc (rt << 1 | 1)
#define mid (l + r) / 2const int maxn = 250000 + 5;
typedef long long ll;int N = maxn;
ll add[maxn << 2],opa[maxn << 2],opb[maxn << 2];
ll sum[maxn << 2];
int cover[maxn << 2];
ll cal(ll n) {return (1 + n) * n / 2;}void pushdown(int l,int r,int rt)
{if(cover[rt] == 1){opa[lc] = opb[lc] = add[lc] = sum[lc] = 0;opa[rc] = opb[rc] = add[rc] = sum[rc] = 0;cover[lc] = cover[rc] = 1;cover[rt] = 0;}//addadd[lc] += add[rt];add[rc] += add[rt];sum[lc] += 1ll * (mid - l + 1) * add[rt];sum[rc] += 1ll * (r - mid) * add[rt];add[rt] = 0;//opaopa[lc] += opa[rt];opa[rc] += opa[rt];sum[lc] += cal(mid - l + 1) * opa[rt];sum[rc] += cal(r - mid) * opa[rt];add[rc] += (mid - l + 1) * opa[rt];sum[rc] += (mid - l + 1) * opa[rt] * (r - mid);opa[rt] = 0;//opbopb[lc] += opb[rt];opb[rc] += opb[rt];sum[lc] += cal(mid - l + 1) * opb[rt];sum[rc] += cal(r - mid) * opb[rt];add[lc] += (r - mid) * opb[rt];sum[lc] += (r - mid) * opb[rt] * (mid - l + 1);opb[rt] = 0;
}void updatea(int ql,int qr,int l,int r,int rt)
{if(ql <= l && r <= qr){sum[rt] += 1ll * (l - ql) * (r - l + 1);sum[rt] += cal(r - l + 1);add[rt] += (l - ql);opa[rt] ++;return;}pushdown(l,r,rt);if(ql <= mid) updatea(ql,qr,l,mid,lc);if(mid < qr) updatea(ql,qr,mid + 1,r,rc);sum[rt] = sum[lc] + sum[rc];
}
void updateb(int ql,int qr,int l,int r,int rt)
{if(ql <= l && r <= qr){sum[rt] += 1ll * (qr - r) * (r - l + 1);sum[rt] += cal(r - l + 1);add[rt] += (qr - r);opb[rt] ++;return;}pushdown(l,r,rt);if(ql <= mid) updateb(ql,qr,l,mid,lc);if(mid < qr) updateb(ql,qr,mid + 1,r,rc);sum[rt] = sum[lc] + sum[rc];
}
void updatec(int ql,int qr,int l,int r,int rt,int x)
{if(ql <= l && r <= qr){cover[rt] = 1;sum[rt] = 1ll * (r - l + 1) * x;opa[rt] = opb[rt] = 0;add[rt] = x;return;}pushdown(l,r,rt);if(ql <= mid) updatec(ql,qr,l,mid,lc,x);if(mid < qr) updatec(ql,qr,mid + 1,r,rc,x);sum[rt] = sum[lc] + sum[rc];
}
ll query(int ql,int qr,int l,int r,int rt)
{if(ql <= l && r <= qr) return sum[rt];pushdown(l,r,rt);ll ans = 0;if(ql <= mid) ans += query(ql,qr,l,mid,lc);if(mid < qr) ans += query(ql,qr,mid + 1,r,rc);return ans;
}
int main()
{int m;scanf("%d",&m);getchar();char op;int l,r,x;while(m --){scanf("%c%d%d",&op,&l,&r);//printf("%c %d %d \n",op,l,r);if(op == 'A'){updatea(l,r,1,N,1);}else if(op == 'B'){updateb(l,r,1,N,1);}else if(op == 'C'){scanf("%d",&x);updatec(l,r,1,N,1,x);}else if(op == 'S'){ll ans = query(l,r,1,N,1);printf("%lld\n",ans);}getchar();}return 0;
}

 

这篇关于数据结构--线段树--维护等差数列--uva12436 Rip Van Winkle's Code的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---