[Jsoi2018]军训列队 主席树

Description
一共有$n$n个学生，第$i$i个学生的休息位置是$a[i]$a[i]。每一次命令，教官会指定一个区间$[l, r]$[l,r]和集合点$k$k，所有编号在$[l, r]$[l,r]内的学生都必须赶到集合点列队。在列队时，每一个学生需要选择$[k, k+r-l]$[k,k+r−l]中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标$x$x跑到坐标$y$y需要耗费体力$|x − y|$∣x−y∣。
在一天的训练中，教官一共发布$m$m条命令$l$l, $r$r, $k$k，现在你需要计算对于每一条命令，在所有可能的列队方案中，消耗的体力值总和最小是多少。

---

Sample Input
5 5
1 5 7 6 2
1 5 2
1 5 3
1 3 9
2 4 2
3 5 5

---

Sample Output
5
4
17
9
3

---

一个比较显然的结论就是$a[1]$a[1]跑位置$1$1，$a[2]$a[2]跑位置$2$2…然后以一个点作为分界点，肯定是一堆人向右跑，一堆人向左跑。
考虑在主席树上二分这个东西。
在当前区间中，$mid$mid之前有$cnt$cnt个人，
假设$k+cnt-1>mid$k+cnt−1>mid，因为$mid>=左区间最后一个元素$mid>=左区间最后一个元素，所以左区间的人一定都会向右跑，到右区间中继续递归中。
假如$k+cnt-1&lt;mid$k+cnt−1<mid，因为右边最小的元素不会小于$mid+1$mid+1，所以$k+cnt&lt;mid+1$k+cnt<mid+1，也就是说右边最小的元素向左跑，换言之，右边所有人都向左跑。
假如$k+cnt-1=mid$k+cnt−1=mid，
这时，假设右边第一个元素是$mid+1$mid+1，那么$k+cnt=mid+1$k+cnt=mid+1，也就是说$mid+1$mid+1这个位置的人原地不动，他成为了分界点，不用继续递归，
假设右边第一个元素大于$mid$mid，那么$k+cnt&lt;右边第一个元素$k+cnt<右边第一个元素，我们再假设左边最后一个元素是$mid$mid，那么以$mid$mid为分界点，不用继续递归，再假设左边最后一个元素小于$mid$mid则$k+cnt-1&gt;左边第一个元素$k+cnt−1>左边第一个元素，
此时$k+cnt-1&gt;左边第一个元素$k+cnt−1>左边第一个元素，$k+cnt&lt;右边第一个元素$k+cnt<右边第一个元素，即左边的人向右跑，右边的人向左跑，不用继续递归。

---

#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;
typedef long long LL;
int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
const int N = 500001;
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}
void put(LL x) {
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

struct tnode {
	int lc, rc, c; LL s;
} t[N * 20]; int cnt, rt[N];
LL lcnt, ls;

void Link(int &u, int l, int r, int p) {
	if(!u) u = ++cnt;
	t[u].c++, t[u].s += p;
	if(l == r) return ;
	int mid = (l + r) / 2;
	if(p <= mid) Link(t[u].lc, l, mid, p);
	else Link(t[u].rc, mid + 1, r, p);
}

void Merge(int &u1, int u2) {
	if(!u1 || !u2) {u1 = u1 + u2; return ;}
	t[u1].c += t[u2].c, t[u1].s += t[u2].s;
	Merge(t[u1].lc, t[u2].lc);
	Merge(t[u1].rc, t[u2].rc);
}

void query(int u1, int u2, int l, int r, int k) {
	if(l == r) return ;
	int mid = (l + r) / 2;
	LL c = t[t[u1].lc].c - t[t[u2].lc].c, s = t[t[u1].lc].s - t[t[u2].lc].s;
	if(mid - k + 1 < c + lcnt) lcnt += c, ls += s, query(t[u1].rc, t[u2].rc, mid + 1, r, k);
	else if(mid - k + 1 == c + cnt) lcnt += c, ls += s;
	else query(t[u1].lc, t[u2].lc, l, mid, k);
}

LL solve(int l, int r, int k) {
	lcnt = ls = 0;
	LL cnt = t[rt[r]].c - t[rt[l - 1]].c, s = t[rt[r]].s - t[rt[l - 1]].s;
	query(rt[r], rt[l - 1], 0, 1000000, k);
	LL rcnt = cnt - lcnt, rs = s - ls;
	LL ans = (lcnt + k + k - 1) * lcnt / 2 - ls + rs - (k + lcnt + k + cnt - 1) * rcnt / 2;
	return ans;
}

int main() {
	int n = read(), m = read();
	for(int i = 1; i <= n; i++) Link(rt[i], 0, 1000000, read()), Merge(rt[i], rt[i - 1]);
	for(int i = 1; i <= m; i++) {
		int l = read(), r = read(), k = read();
		put(solve(l, r, k)), puts("");
	} return 0;
}