题目链接：poj 3468
namespace std;template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != ‘-‘ && (c<‘0′ || c>’9’)) c = getchar();sgn = (c == ‘-‘) ? -1 : 1;ret = (c == ‘-‘) ? 0 : (c – ‘0’);while (c = getchar(), c >= ‘0’&&c <= ‘9’) ret = ret * 10 + (c – ‘0’);ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar(‘-‘);x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + ‘0’);}typedef long long ll;lkey (ch[0]->key)rsiz (ch[1]->size)llazy (ch[0]->lazy)N = 1e5 + 10;const int MAXN = 50010;struct Node *null;struct Node{Node *ch[2], *fa;int size, cnt;//cnt表示当前这个点有一个节点,虚拟节点是0ll lazy, sum, key;inline void setc(Node *p, int d){//p是this的d儿子ch[d] = p;p->fa = this;}inline bool d(){//这个节点是右儿子return fa->ch[1] == this;}inline void push_up(){size = lsiz + rsiz + cnt;sum = lsum + rsum + key;}inline void push_down(){if (!lazy)return;if (lson != null){ lkey += lazy; lsum += lsiz * lazy; llazy += lazy; }if (rson != null){ rkey += lazy; rsum += rsiz * lazy; rlazy += lazy; }lazy = 0;}void clear(int _key){size = cnt = 1;sum = key = _key;ch[0] = ch[1] = fa = null;lazy = 0;}inline bool isroot(){return fa == null || this != fa->ch[0] && this != fa->ch[1];}};Node pool[MAXN * 15], *tail;Node *bc[MAXN];int bc_top;//内存回收void init(){tail = pool;bc_top = 0;null = tail++;null->size = null->cnt = 0;null->ch[0] = null->ch[1] = null->fa = null;}inline void rotate(Node *x){Node *f = x->fa, *ff = x->fa->fa;f->push_down(); x->push_down();int c = x->d(), cc = f->d();f->setc(x->ch[!c], c);x->setc(f, !c);if (ff->ch[cc] == f)ff->setc(x, cc);else x->fa = ff;f->push_up();}inline void splay(Node* &root, Node* x, Node* goal){x->push_down();while (x->fa != goal){if (x->fa->fa == goal)rotate(x);else {bool f = x->fa->d();x->d() == f ? rotate(x->fa) : rotate(x);rotate(x);}}x->push_up();if (goal == null)root = x;}//找到r子树里面的最左边那个Node* get_left(Node* r){Node* x = r;while (x->ch[0] != null)x = x->ch[0];return x;}//在root的树中删掉xvoid erase(Node* &root, Node* x){splay(root, x, null);Node* t = root;if (t->ch[1] != null){root = t->ch[1];splay(root, get_left(t->ch[1]), null);root->setc(t->ch[0], 0);}else root = root->ch[0];bc[bc_top++] = x;root->fa = null;if (root != null)root->push_up();}Node* newNode(int key){Node* p;if (bc_top)p = bc[–bc_top];else p = tail++;p->clear(key);return p;}Node* get_kth(Node* x, int k){//寻找x后面的第k个x->push_down();Node*u = x;while (u->ch[0]->size+1 != k){if (u->ch[0]->size >= k)u = u->ch[0];else {k -= u->ch[0]->size + 1;u = u->ch[1];}u->push_down();}return u;}//插入一个值keyvoid insert(Node* &root, int key){if (root == null){root = newNode(key);return;}Node* now = root;Node* pre = root->fa;while (now != null){if (now->key == key){now->cnt++;splay(root, now, null);return;}pre = now;now = now->ch[key >= now->key];}Node *x = newNode(key);pre->setc(x, key >= pre->key);splay(root, x, null);}//删除一个值keyvoid erase(Node* &root, int key){Node* now = root;while (now->key != key){now = now->ch[key >= now->key];}now->cnt–;if (now->cnt == 0)erase(root, now);else splay(root, now, null);}void Travel(Node* r){if (r == null)return;Travel(r->ch[0]);bc[bc_top++] = r;Travel(r->ch[1]);}void CLEAR(Node* &root){Travel(root);root = null;}//查询小于等于val的个数int query(Node *root, int val){int ans = 0;Node *x = root;while (x != null){if (val < x->key)x = x->ch[0];else{ans += x->ch[0]->size + x->cnt;x = x->ch[1];}}return ans;}Node* build(int l, int r, int *a){if (l > r)return null;int mid = (l + r) >> 1;Node* u = newNode(a[mid]);u->setc(build(l, mid – 1, a), 0);u->setc(build(mid + 1, r, a), 1);u->push_up();return u;}void debug(Node* r){if (r == null)return;printf(“key:%I64d lson:%I64d rson:%I64d\n”, r->key, r->ch[0]->key, r->ch[1]->key);debug(r->ch[0]);debug(r->ch[1]);}int n, q;int a[N];int main(){while (cin >> n >> q){for (int i = 1; i <= n; i++)rd(a[i]);init();Node* root = build(0, n + 1, a);Node* lnode,* rnode, *tmp;char str[2];while (q–){int l, r; ll val;scanf(“%s”, str); rd(l); rd(r);splay(root, get_left(root), null);lnode = get_kth(root, l);rnode = get_kth(root, r+2);splay(root, lnode, null);//debug(root);splay(root, rnode, lnode);//debug(root);if (str[0] == ‘Q’){pt(root->ch[1]->ch[0]->sum); putchar(‘\n’);}else {rd(val);tmp = root->ch[1]->ch[0];tmp->sum += val * (r – l + 1);tmp->lazy += val;tmp->key += val;root->ch[1]->push_up();root->push_up();//debug(root);}}}return 0;}/**/
，抱最大的希望，为最大的努力，做最坏的打算
