Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
Hint
The sums may exceed the range of 32-bit integers.
Source
POJ Monthly--2007.11.25, Yang Yi
【分析】
这个其实是个水题。我只是拿来fhq treap的...
Orzzzzzz范大爷
这种数据结构真是...能保证treap的性质同时也能保证合并后的树还能原封不动的切出来...
说它是treap，我觉得就一个fix像treap而已。
这个数据结构的精髓在合并和分裂(和打标记？)。有注释.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#define LOCAL
const int MAXN = + ;
const int INF = 0x3f3f3f3f;
const int SIZE = ;
const int maxnode = ;
using namespace std;
typedef long long ll;
ll n, m;
struct fhqTreap{
struct Node{
Node *l, *r;
ll delta, sum;
ll size, fix, val;
}*root, *null, mem[];
ll tot; ll BIG_RAND(){return (ll)rand()*RAND_MAX + (ll)rand();}
void init(){
tot = ;
NEW(null, );
null->size = ;
root = null;
insert(, n);//插入
}
void update(Node *t){
if (t == null) return;
t->size = t->l->size + t->r->size + ;
t->sum = t->val;
if (t->l != null) t->sum += t->l->sum;
if (t->r != null) t->sum += t->r->sum;
}
//标记下传=-=
void push_down(Node *t){
if (t->delta){
t->val += t->delta; if (t->l != null) {t->l->delta += t->delta, t->l->sum += t->l->size * t->delta;}
if (t->r != null) {t->r->delta += t->delta, t->r->sum += t->r->size * t->delta;} t->delta = ;
}
} void NEW(Node *&t, ll val){
t = &mem[tot++];
t->size = ;
t->fix = BIG_RAND();
t->sum = t->val = val;
t->delta = ;
t->l = t->r = null;
}
//将t分裂为大小p和t->size - p的两个子树
void split(Node *t, Node *&a, Node *&b, int p){
if (t->size <= p) a = t, b = null;
else if (p == ) a = null, b = t;
else {
push_down(t);
if (t->l->size >= p){
b = t;
split(t->l, a , b->l, p);
update(b);
}else{
a = t;
split(t->r, a->r, b, p - t->l->size - );
update(a);
}
}
}
//将a,b树合并为t
void merge(Node *&t, Node *a, Node *b){
if (a == null) t = b;
else if (b == null) t = a;
else {
if (a->fix > b->fix){//按fix值排序
push_down(a);
t = a;
merge(t->r, a->r, b);
}else{
push_down(b);
t = b;
merge(t->l, a, b->l);
}
update(t);
}
}
void add(ll l, ll r, ll val){
Node *a, *b, *c;
split(root, a, b, l - );
split(b, b, c, r - l + );
b->delta += val;
b->sum += val * b->size;
merge(a, a, b);
merge(root, a, c);
}
ll query(ll l, ll r){
Node *a, *b, *c;
split(root, a, b, l - );
split(b, b, c, r - l + );
ll ans = b->sum;
merge(b, b, c);
merge(root, a, b);
return ans;
}
//把b挤出去
void Delete(ll p){
Node *a, *b, *c;
split(root, a, b, p - );
split(b, b, c, );
merge(root, a, c);
}
Node *Insert(ll x){//不可思议的插入方式
if (x == ) return null;
if (x == ){
ll tmp;
scanf("%lld", &tmp);
Node *a;
NEW(a, tmp);
return a;
}
Node *a, *b;
int mid = x / ;
a = Insert(mid);
b = Insert(x - mid);
merge(a, a, b);
return a;
} //在pos处插入x个数字
void insert(ll pos, ll x){
Node *a, *b, *c, *t;
//跟块状链表的有点像，分裂再合并
split(root, a, b, pos);
c = Insert(x);//插入一个值为x的树
merge(a, a, c);
merge(root, a, b);
}
}A; void work(){
char str[];
while (m--){
scanf("%s", str);
if (str[] == 'Q'){
ll l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", A.query(l, r));
}else{
ll l, r, k;
scanf("%lld%lld%lld", &l, &r, &k);
A.add(l, r, k);
}
}
} int main(){ while( scanf("%lld%lld", &n, &m) != EOF){
A.init();
work();
}
return ;
}