|
|
思路： 每個(gè)節(jié)點(diǎn)記錄兩個(gè)值： 所有子節(jié)點(diǎn)的增量和 該節(jié)點(diǎn)的增量 代碼爛，1500+ms。 為了避免爆棧，實(shí)現(xiàn)計(jì)算好了左右邊界和中間值。
 #include <stdio.h>
#include <stdlib.h>
#define MAX_N 100032
int N;
  struct  {
 __int64 up, down;
int rl, rr, rm;
 } tree[MAX_N*4];
enum OP {
INSERT,
SUM,
} op;
__int64 val;
void tree_op(int idx, int l, int r)
{
  if (op == INSERT) {
if (tree[idx].rl == l && tree[idx].rr == r) {
tree[idx].up += val;
return ;
 }
tree[idx].down += val * (r - l + 1);
} else {
val += tree[idx].up * (r - l + 1);
if (tree[idx].rl == l && tree[idx].rr == r) {
val += tree[idx].down;
return ;
}
}
if (r <= tree[idx].rm) {
// all in left
tree_op(idx*2, l, r);
} else if (l > tree[idx].rm) {
// all in right
tree_op(idx*2+1, l, r);
} else {
// in left and right
tree_op(idx*2, l, tree[idx].rm);
tree_op(idx*2+1, tree[idx].rm + 1, r);
}
}
int main()
{
int i, j, q;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
tree[1].rl = 1;
tree[1].rm = (MAX_N + 1) / 2;
tree[1].rr = MAX_N;
for (i = 2; i < _countof(tree); i++) {
if (i & 1) {
tree[i].rl = tree[i/2].rm + 1;
tree[i].rr = tree[i/2].rr;
} else {
tree[i].rl = tree[i/2].rl;
tree[i].rr = tree[i/2].rm;
}
tree[i].rm = (tree[i].rl + tree[i].rr) / 2;
}
scanf("%d%d", &N, &q);
op = INSERT;
for (i = 1; i <= N; i++) {
scanf("%I64d", &val);
tree_op(1, i, i);
}
while (q--) {
scanf("%s%d%d", str, &i, &j);
if (str[0] == 'Q') {
val = 0;
op = SUM;
tree_op(1, i, j);
printf("%I64d\n", val);
} else {
scanf("%I64d", &val);
op = INSERT;
tree_op(1, i, j);
}
}
return 0;
}
|