1 #include<cstdio>  2 #define mid(a,b) ((a+b)>>1) //宏定义中用到移位需要注意！  3   4 using namespace std;  5   6 struct Node{  7   8      int left, right;  9      Node* pL, *pR; 10      long long sum; 11      long long increase; 12 }Tree[400020]; 13  14 int Count = 0; 15  16 void build(Node *pRoot, int l, int r){ 17  18    pRoot->left = l; 19    pRoot->right = r; 20    pRoot->sum = 0; 21    pRoot->increase = 0; 22  23    if( l == r )//结束条件 24        return; 25    Count ++; 26    pRoot->pL = Tree + Count; 27    Count ++; 28    pRoot->pR = Tree + Count; 29  30    build(pRoot->pL, l, mid(l,r)); 31    build(pRoot->pR, mid(l,r)+1, r); 32 } 33  34 void minsert(Node *pRoot, int pose, int value){ 35  36      if(pRoot->left == pose && pRoot->right == pose){ 37           pRoot->sum = value; 38           return; 39      } 40      pRoot->sum += value;//important!? 41      if(pose <= mid(pRoot->left,pRoot->right)) 42         minsert(pRoot->pL, pose, value); 43      else if(pose > mid(pRoot->left,pRoot->right)) 44         minsert(pRoot->pR,pose,value); 45 } 46  47 void add(Node *pRoot, int l, int r, long long value){ 48  49      if(pRoot->left == l && pRoot->right == r){ 50         pRoot->increase += value; 51         return; 52      } 53  54      pRoot->sum += value*(r - l + 1);//右减左！此时增值为value！ 55      if(r <= mid(pRoot->left, pRoot->right)) 56         add(pRoot->pL, l, r, value); 57      else if(l > mid(pRoot->left, pRoot->right)) 58         add(pRoot->pR, l, r, value); 59      else{ 60         add(pRoot->pL, l, mid(pRoot->left, pRoot->right),value); 61         add(pRoot->pR, mid(pRoot->left, pRoot->right) + 1, r, value); 62      } 63 } 64  65 long long query(Node* pRoot, int s, int e){ 66  67     if(pRoot->left == s && pRoot->right == e){ 68         return pRoot->sum + pRoot->increase*(pRoot->right - pRoot->left + 1); 69     } 70  71     pRoot->sum += pRoot->increase*(pRoot->right - pRoot->left + 1); 72     add(pRoot->pL, pRoot->left, mid(pRoot->left, pRoot->right), pRoot->increase);// 73     add(pRoot->pR, mid(pRoot->left, pRoot->right) + 1, pRoot->right, pRoot->increase);//????????????? 74     pRoot->increase = 0; 75     if(e <= mid(pRoot->left, pRoot->right)) 76         return query(pRoot->pL, s, e); 77     else if(s > mid(pRoot->left, pRoot->right)) 78         return query(pRoot->pR, s, e);// 79     else{ 80         return query(pRoot->pL, s, mid(pRoot->left, pRoot->right)) + 81                query(pRoot->pR, mid(pRoot->left, pRoot->right) + 1, e); 82     } 83 } 84  85 int main(){ 86  87   int n, q, num, l, r, value; 88   char op; 89   scanf("%d %d", &n, &q); 90  91   build(Tree, 1, n); 92  93   for(int i = 1; i <= n; i++){ 94     scanf("%d", &num); 95     minsert(Tree, i, num); 96   } 97   while(q --){ 98  99     getchar();100     scanf("%c",&op);101     if(op == ‘C‘){102         scanf("%d %d %d", &l, &r, &value);103         add(Tree, l, r, value);104     }105     if(op == ‘Q‘){106         scanf("%d %d", &l, &r);107         printf("%I64d\n",query(Tree,l,r));108     }109   }110 111   return 0;112 113 }