首页 > 代码库 > uva 12436 - Rip Van Winkle's Code(线段树)
uva 12436 - Rip Van Winkle's Code(线段树)
题目链接:uva 12436 - Rip Van Winkle‘s Code
题目大意:四种操作,操作见题目。
解题思路:即用线段树维护一个等差数列,因为一个等差加上一个等差还是一个等差数列,所以对于每个节点记录区
间左端的值,也就是首项,以及公差即可。因为还有一个S操作,所以要开一个标记记录区间值是否相同。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 250100;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], v[maxn << 2];
ll nd[maxn << 2], ad[maxn << 2], s[maxn << 2];
void pushup(int u);
void pushdown (int u);
inline int length(int u) {
return rc[u] - lc[u] + 1;
}
inline void change (int u, ll a) {
v[u] = 1;
ad[u] = 0;
nd[u] = a;
s[u] = a * length(u);
}
inline void maintain (int u, ll a, ll d) {
if (v[u] && lc[u] != rc[u]) {
pushdown(u);
pushup(u);
}
v[u] = 0;
nd[u] += a;
ad[u] += d;
ll n = length(u);
s[u] += a * n + (((n-1) * n) / 2) * d;
}
inline void pushup (int u) {
s[u] = s[lson(u)] + s[rson(u)];
}
inline void pushdown (int u) {
if (v[u]) {
change(lson(u), nd[u]);
change(rson(u), nd[u]);
v[u] = nd[u] = 0;
} else if (nd[u] || ad[u]) {
maintain(lson(u), nd[u], ad[u]);
maintain(rson(u), nd[u] + length(lson(u)) * ad[u], ad[u]);
nd[u] = ad[u] = 0;
}
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
nd[u] = ad[u] = s[u] = 0;
if (l == r)
return;
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, ll a, ll d) {
if (l <= lc[u] && rc[u] <= r) {
maintain(u, a + d * (lc[u] - l), d);
return;
}
pushdown(u);
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
modify(lson(u), l, r, a, d);
if (r > mid)
modify(rson(u), l, r, a, d);
pushup(u);
}
void set(int u, int l, int r, ll a) {
if (l <= lc[u] && rc[u] <= r) {
change(u, a);
return;
}
pushdown(u);
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
set(lson(u), l, r, a);
if (r > mid)
set(rson(u), l, r, a);
pushup(u);
}
ll query (int u, int l, int r) {
if (l <= lc[u] && rc[u] <= r)
return s[u];
pushdown(u);
ll ret = 0;
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
ret += query(lson(u), l, r);
if (r > mid)
ret += query(rson(u), l, r);
pushdown(u);
return ret;
}
int N;
int main () {
while (~scanf("%d", &N)) {
char op[5];
int l, r, x;
build(1, 1, 250000);
while (N--) {
scanf("%s%d%d", op, &l, &r);
if (op[0] == ‘A‘)
modify(1, l, r, 1, 1);
else if (op[0] == ‘B‘)
modify(1, l, r, r - l + 1, -1);
else if (op[0] == ‘C‘) {
scanf("%d", &x);
set(1, l, r, x);
} else
printf("%lld\n", query(1, l, r));
}
}
return 0;
}
uva 12436 - Rip Van Winkle's Code(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。