POJ 3468_PUSHDOWN
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
#include <cctype>
#define C(x) (x = getchar())
#define L(x) ((x) << 1)
#define R(x) ((x) << 1 | 1)
#define avg(x, y) (((x) + (y)) >> 1)
inline void read(int &x)
{
int ch = x = 0, flag = 1;
while (!isdigit(C(ch))) if (ch == '-') flag = -1;
for (; isdigit(ch); C(ch))
x = x * 10 + ch - '0';
x *= flag;
}
const int N = int(1e5 + 5);
typedef long long i64;
int a[N];
i64 A[N << 2], S[N << 2];
inline void add(int k, int l, int r, i64 v)
{
A[k] += v;
S[k] += (r - l) * v;
}
inline void pushdown(int k, int l, int r)
{
if (A[k] == 0) return;
int m = avg(l, r);
add(L(k), l, m, A[k]);
add(R(k), m, r, A[k]);
A[k] = 0;
}
void build(int k, int l, int r)
{
if (l == r - 1) return void(S[k] = a[l]);
int m = avg(l, r);
build(L(k), l, m);
build(R(k), m, r);
S[k] = S[L(k)] + S[R(k)];
}
i64 query(int k, int l, int r, int x, int y)
{
if (x <= l && r <= y) return S[k];
pushdown(k, l, r);
int m = avg(l, r);
i64 res = 0;
if (x < m) res += query(L(k), l, m, x, y);
if (y > m) res += query(R(k), m, r, x, y);
return res;
}
void modify(int k, int l, int r, int x, int y, int v)
{
if (x <= l && r <= y) return add(k, l, r, v);
int m = avg(l, r);
pushdown(k, l, r);
if (x < m) modify(L(k), l, m, x, y, v);
if (y > m) modify(R(k), m, r, x, y, v);
S[k] = S[L(k)] + S[R(k)];
}
int main()
{
int n, m;
read(n), read(m);
for (int i = 0; i < n; i++) read(a[i]);
build(1, 0, n);
while (m--)
{
int op = 0, x, y, z;
while (op != 'Q' && op != 'C') C(op);
if (op == 'Q')
{
read(x), read(y);
printf("%lld\n", query(1, 0, n, x - 1, y));
}
else
{
read(x), read(y), read(z);
modify(1, 0, n, x - 1, y, z);
}
}
return 0;
}