POJ 3468 A Simple Problem with Integers (伸展树区间更新求和操作 ， 模板) (二)
ug(NODE *x) {
if(x != null) {
printf("节点: %2d 左儿子: %2d 右儿子: %2d size = %2d val = %2d\n",
x->id, x->ch[0]->id, x->ch[1]->id, x->sz, x->val);
debug(x->ch[0]);
debug(x->ch[1]);
}
}
int a[maxn];
NODE *newnode(NODE* f, int c) {
NODE *x = &node[++top];
x->id = top;
x->val = x->sum = c;
x->ch[0] = x->ch[1] = null;
x->sz = 1;
x->add = 0;
x->pre = f;
return x;
}
void build(NODE* &x, int l, int r, NODE *f) {
if(l > r) return ;
int mid = (l+r)/2;
x = newnode(f, a[mid]);
build(lson, l, mid-1, x);
build(rson, mid+1, r, x);
x->push_up();
}
void init(int n) {
null->id = 0;
null->ch[0] = null->ch[1] = NULL;
null->sz = null->add = null->sum = null->val = 0;
// null->pre = NULL;
top = 0;
root = newnode(null, -1);
root->
ch[1] = newnode(root, -1);
for(int i = 0;i < n; i++) scanf("%d", &a[i]);
build(keytree, 0, n-1, root->ch[1]);
root->ch[1]->push_up(); root->push_up();
}
void update() {
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
RotateTo(l-1, null);
RotateTo(r+1, root);
keytree->add += c;
keytree->sum += (LL)c*keytree->sz;
}
void query() {
int l, r;
scanf("%d%d", &l, &r);
RotateTo(l-1, null);
RotateTo(r+1, root);
printf("%I64d\n", keytree->sum);
}
}spt;
int main() {
int n, m;
char s[2];
scanf("%d%d", &n, &m);
spt.init(n);
while(m--) {
scanf("%s", s);
if(s[0] == 'Q')
spt.query();
else
spt.update();
}
return 0;
}