include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 200010;

typedef long long LL;

// 本题使用树状数组动态记录出现数字的个数，进而根据数组的递增属性，
// 快速计算满足条件的数的个数

int n;
int a[N];
int tr[N];
// 记录大于小于当前数字的个数
int Greater[N], Lower[N];

// 树状数组有三个函数

// 使用二进制展开的特性进行区间记录
int lowbit(int x)
{
return x & (-x);
}

// 将序列中第x个数加上k
void add(int x, int c)
{
// 修改相当于分割的逆过程，依旧使用lowbite
for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

// 按序求和
int ask(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}

// 主要理解树状数组的使用方式
int main()
{
scanf(“%d”, &n);
for(int i = 1; i <= n; i++) scanf(“%d”, &a[i]);

// 一共要扫描两遍（左到右、右到左）
// 首先从左到右、依次计算每个位置比a[i]小的个数以及比a[i]大的数字的个数（专管左边）
for(int i = 1; i <= n; i++)
{
    int y = a[i];

    // 注意这里判断的是已经加入的数字
    Lower[i] = ask(y - 1);
    Greater[i] = ask(n) - ask(y);

    // 将y加入树状数组
    add(y, 1); // 数组维护的是数字出现的次数
}

// 清空树状数组，进行第二次计算
memset(tr, 0, sizeof(tr));

LL resA = 0, resV = 0;
// 从右到左遍历
for(int i = n; i >= 1; i--)
{
    // 遍历同时计算结果
    int y = a[i];
    resA += (LL)Lower[i] * ask(y - 1);
    resV += (LL)Greater[i] * (ask(n) - ask(y));

    //将y加入树状数组，即数字y出现1次
    add(y, 1);
}

printf("%lld %lld\n", resV, resA);

return 0;

}

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef long long LL;

const int N = 100010;

// 理解两个前缀和（树状数组）的组织方式
// 树状数组最基本的功能就是单点修改，区间求和。
// 再根据树状数组，可以实现区间修改，单点求和。
// 本题则是进一步的升级，维护两个树状数组，完成区间修改、区间求和
int n, m;
int a[N]; // 原数组
LL tr1[N]; // 维护b[i]的前缀和
LL tr2[N]; // 维护b[i] * i的前缀和

int lowbit(int x)
{
return x & -x;
}

// 因为需要修改两个数组，所以修改和add函数都需要多加一个参数
void add(LL tr[], int x, LL c)
{
for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

// 计算（查询）前缀和
LL sum(LL tr[], int x)
{
LL res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}

// 按照公式计算区间的前缀和
LL prefix_sum(int x)
{
return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main()
{
cin >> n >> m;
for(int i = 1;i <= n; i) scanf(“%d”, &a[i]);
for(int i = 1; i <= n; i)
{
int b = a[i] - a[i - 1];

    // 初始化树状数组
    add(tr1, i, b);
    add(tr2, i, (LL)b * i);
}

while(m--)
{
    char op[2];
    int l, r, d;
    scanf("%s%d%d", op, &l, &r);
    if(*op == 'Q')
    {
        printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
    }
    else
    {
        scanf("%d", &d);
        // a[l] += d
        add(tr1, l, d), add(tr2, l, l * d);

        // s[r + 1] -= b
        add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * (-d));
    }
}

return 0;

}