1 #include <set>  2 #include <map>  3 #include <cmath>  4 #include <ctime>  5 #include <queue>  6 #include <stack>  7 #include <cstdio>  8 #include <string>  9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 typedef unsigned long long ull; 16 typedef long long ll; 17 const int inf = 0x3f3f3f3f; 18 const double eps = 1e-8; 19 const int maxn = 1e5+100; 20 ll add[maxn],sum[maxn]; 21 int ch[maxn][2],siz[maxn],key[maxn],a[maxn]; 22 int pre[maxn]; 23 int tot1,root; 24 void new_node(int &r,int father,int k) 25 { 26     r = ++tot1; 27     pre[r] = father; 28     siz[r] = 1; 29     add[r] = 0; 30     key[r] = k; 31     sum[r] = k; 32     ch[r][0] = ch[r][1] = 0; 33 } 34  35 void update(int r,int val) 36 { 37     if (r == 0) 38         return ; 39     add[r] += val; 40     key[r] += val; 41     sum[r] += (ll)val * siz[r]; 42 } 43  44 void push_down(int x) 45 { 46     if (add[x]) 47     { 48         update(ch[x][0],add[x]); 49         update(ch[x][1],add[x]); 50         add[x] = 0; 51     } 52 } 53 void push_up(int x) 54 { 55     siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1; 56     sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + key[x]; 57 } 58 void build(int &x,int l,int r,int father) 59 { 60     if (l > r) 61         return; 62     int mid = (l + r) >> 1; 63     new_node(x,father,a[mid-1]); 64     build(ch[x][0],l,mid-1,x); 65     build(ch[x][1],mid+1,r,x); 66     push_up(x); 67 } 68 void init(int n) 69 { 70     tot1 = 0; 71     root = 0; 72     new_node(root,0,-1); 73     new_node(ch[root][1],root,-1); 74     for (int i = 0; i < n; i++) 75         scanf ("%d",a+i); 76     build(ch[ch[root][1]][0],1,n,ch[root][1]); 77     push_up(ch[root][1]); 78     push_up(root); 79 } 80 void Rotate(int x,int kind) 81 { 82     int y = pre[x]; 83     push_down(y); 84     push_down(x);              // 标记下传 85  86     ch[y][!kind] = ch[x][kind]; 87     pre[ch[x][kind]] = y; 88     ch[x][kind] = y; 89     if (pre[y]) 90         ch[pre[y]][ch[pre[y]][1] == y] = x; 91     pre[x] = pre[y]; 92     pre[y] = x; 93     push_up(y);               //     ??? 94 } 95 void Splay(int r,int goal) 96 { 97     push_down(r); 98     while (pre[r] != goal) 99     {100         if (pre[pre[r]] == goal)101             Rotate(r,ch[pre[r]][0] == r);102         else103         {104             int y = pre[r];105             int kind = (ch[pre[y]][0] == y);106             if (ch[y][kind] == r)107             {108                 Rotate(r,!kind);109                 Rotate(r,kind);110             }111             else112             {113                 Rotate(y,kind);114                 Rotate(r,kind);115             }116         }117     }118     push_up(r);119     if (goal == 0)120         root = r;121 }122 int Get_kth(int r,int k)123 {124     push_down(r);125     int t = siz[ch[r][0]] + 1;126     if (k == t)127         return r;128     if (t > k)129         Get_kth(ch[r][0],k);130     else131         Get_kth(ch[r][1],k-t);132 }133 void ADD(int l,int r,int val)134 {135     Splay(Get_kth(root,l),0);136     Splay(Get_kth(root,r+2),root);137     update(ch[ch[root][1]][0],val);138     push_up(ch[root][1]);139     push_up(root);140 }141 ll query(int l,int r)142 {143     Splay(Get_kth(root,l),0);144     Splay(Get_kth(root,r+2),root);145     return sum[ch[ch[root][1]][0]];146 }147 int main(void)148 {149     #ifndef ONLINE_JUDGE150         freopen("in.txt","r",stdin);151     #endif152     int n,q;153     while (~scanf ("%d%d",&n,&q))154     {155         init(n);156         char op[8];157         while (q--)158         {159             scanf ("%s",op);160             if (op[0] == ‘C‘)161             {162                 int x,y,v;163                 scanf ("%d%d%d",&x,&y,&v);164                 ADD(x,y,v);165             }166             if (op[0] == ‘Q‘)167             {168                 int x,y;169                 scanf ("%d%d",&x,&y);170                 printf("%lld\n",query(x,y));171             }172         }173     }174     return 0;175 }