首先，显然集合后与集合前学生的相对位置不变。
第二，可以找到一个位置，使得在这个位置左边的学生都往右跑，右边的都往左跑。（因为往左往右往左往右太沙雕了……）
假设我们把 \(a\) 数组 \([l,r]\) 区间里的数放到了 \(b\) 数组里且其有序，并且已经知道了这个分界点和有 \(c\) 个学生是往右跑的。
那么这 \(c\) 个往右的学生的贡献应该是 \(\sum\limits_{i = 1}^c K + i - 1 - b_i\)。
拆开得 \(\sum\limits_{i = K}^{K + c - 1} i - \sum\limits_{i = 1}^{c} b_i\)。
显然前者就是一个等差数列。
类似的，我们把另一边拆得 \(\sum\limits_{c + 1}^{r - l + 1} b_i - \sum\limits_{i = K + c}^{K + r - l} i\)。
如果我们知道了这个分界点，求出答案就很简单了，只需要使用主席树。
但是我们不知道啊！
考虑二分。
乍一看答案的单调性不明显，但是它只会分成两部分，而且分界点的变化是单调性的。
于是在主席树上二分即可。
代码： 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
using namespace std;
const int N = 5e5;
const int C = 1e6;
int n,m;
struct node
{
int cnt;
long long sum;
int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
seg[++tot] = seg[p],p = tot;
seg[p].cnt += k,seg[p].sum += (long long)x * k;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
if(x <= mid)
insert(x,k,seg[p].ls,tl,mid);
else
insert(x,k,seg[p].rs,mid + 1,tr);
}
long long query(int k,int c,int u,int v,int tl,int tr)
{
if(!(seg[v].cnt - seg[u].cnt))
return 0;
int mid = tl + tr >> 1;
int cnt = seg[v].cnt - seg[u].cnt;
long long sum = seg[v].sum - seg[u].sum;
if(tl >= k + c)
return sum - (long long)(k + c + k + c + cnt - 1) * cnt / 2;
if(tr <= k + c + cnt - 1)
return (long long)(k + c + k + c + cnt - 1) * cnt / 2 - sum;
return query(k,c,seg[u].ls,seg[v].ls,tl,mid) + query(k,c + seg[seg[v].ls].cnt - seg[seg[u].ls].cnt,seg[u].rs,seg[v].rs,mid + 1,tr);
}
int main()
{
scanf("%d%d",&n,&m);
int x;
for(register int i = 1;i <= n;++i)
scanf("%d",&x),insert(x,1,rt[i] = rt[i - 1],1,C);
int l,r,k;
while(m--)
scanf("%d%d%d",&l,&r,&k),printf("%lld\n",query(k,0,rt[l - 1],rt[r],1,C));
}