此题的数据范围有误导性啊……
不管怎么样反正考虑莫队（
设莫队当前转移到的区间为 \([l,r]\)，转移时新加入一个位置 \(k\)。
则除了本身的贡献以外，它会导致所有比它大的数排名升一位，即贡献加一。
于是其影响为 \[
a_k(1+\sum\limits_{i=l}^r [a_i < a_k]) + \sum\limits_{i=l}^r [a_i > a_k]a_i
\]
计算贡献时将两边差分成前缀相减的形式即可，然后套用二次离线的套路。
注注注注注意里面那个 \(+1\)，它不能乱差分的，别把 \(+1\) 算成了 \(-1\) 啊……
（我才不会说我就是这样子调了半天的）
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x);
}
const int N = 5e5;
const int V = 1e5;
const int BLK = 318;
const int CNT = 318;
int n,m,block,a[N + 5],pos[N + 5];
int vblock = BLK,vpos[V + 5];
struct s_query
{
int l,r,id;
long long ans;
inline bool operator<(const s_query &o) const
{
return pos[l] ^ pos[o.l] ? pos[l] < pos[o.l] : pos[l] & 1 ? r < o.r : r > o.r;
}
} qry[N + 5];
struct s_contrib
{
int l,r,id,w;
};
long long c[2][V + 5];
inline void update(int op,int x,int k)
{
if(!op)
for(;x <= V;x += lowbit(x))
c[op][x] += k;
else
for(;x;x -= lowbit(x))
c[op][x] += k;
}
inline long long query(int op,int x)
{
long long ret = 0;
if(!op)
for(;x;x -= lowbit(x))
ret += c[op][x];
else
for(;x <= V;x += lowbit(x))
ret += c[op][x];
return ret;
}
long long cnt[2][CNT + 5],pre[2][V + 5];
inline void add(int op,int x,int k)
{
if(!op)
{
for(register int i = vpos[x] + 1;i <= vpos[V];++i)
cnt[op][i] += k;
for(register int i = x;i <= min(vpos[x] * vblock,V);++i)
pre[op][i] += k;
}
else
{
for(register int i = vpos[x] - 1;i;--i)
cnt[op][i] += k;
for(register int i = x;i > (vpos[x] - 1) * vblock;--i)
pre[op][i] += k;
}
}
inline long long ask(int op,int x)
{
return cnt[op][vpos[x]] + pre[op][x];
}
vector<s_contrib> vec[N + 5];
long long sum[2][N + 5],ans[N + 5];
int main()
{
for(register int i = 1;i <= V;++i)
vpos[i] = (i - 1) / vblock + 1;
read(n),read(m),block = sqrt(n);
for(register int i = 1;i <= n;++i)
read(a[i]),pos[i] = (i - 1) / block + 1;
for(register int i = 1;i <= n;++i)
{
int c = query(0,a[i] - 1);
long long s = query(1,a[i] + 1);
sum[0][i] = sum[0][i - 1] + (long long)a[i] * (c + 1) + s,
sum[1][i] = sum[1][i - 1] + (long long)a[i] * (c - 1) + s,
update(0,a[i],1),update(1,a[i],a[i]);
}
for(register int i = 1;i <= m;++i)
read(qry[i].l),read(qry[i].r),qry[i].id = i;
sort(qry + 1,qry + m + 1);
for(register int i = 1,l = 1,r = 0;i <= m;++i)
{
qry[i].ans = sum[0][qry[i].r] - sum[0][r] + sum[1][qry[i].l - 1] - sum[1][l - 1];
l < qry[i].l && (vec[r].push_back((s_contrib){l,qry[i].l - 1,i,-1}),1);
l > qry[i].l && (vec[r].push_back((s_contrib){qry[i].l,l - 1,i,1}),1);
l = qry[i].l;
r < qry[i].r && (vec[l - 1].push_back((s_contrib){r + 1,qry[i].r,i,-1}),1);
r > qry[i].r && (vec[l - 1].push_back((s_contrib){qry[i].r + 1,r,i,1}),1);
r = qry[i].r;
}
for(register int i = 1;i <= n;++i)
{
add(0,a[i],1),add(1,a[i],a[i]);
for(register vector<s_contrib>::iterator it = vec[i].begin();it != vec[i].end();++it)
for(register int j = it->l;j <= it->r;++j)
qry[it->id].ans += it->w * (a[j] * ask(0,a[j] - 1) + ask(1,a[j] + 1));
}
for(register int i = 1;i <= m;++i)
ans[qry[i].id] = (qry[i].ans += qry[i - 1].ans);
for(register int i = 1;i <= m;++i)
printf("%lld\n",ans[i]);
}