问题描述
作为一名大学生，九条可怜在去年参加了她人生中的最后一次军训。
军训中的一个重要项目是练习列队，为了训练学生，教官给每一个学生分配了一个休息位置。每次训练开始前，所有学生都在各自的休息位置休息，但是当教官发出集合命令后，被点到的学生必须要到指定位置集合。
为了简化问题，我们把休息位置和集合位置抽象成一根数轴。一共有 (n) 个学生，第 (i) 个学生的休息位置是 (a_i)。每一次命令，教官会指定一个区间 ([l,r]) 和集合点 (K) ，所有编号在 ([l,r]) 内的学生都必须赶到集合点列队。在列队时，每一个学生需要选择 ([K,K+r-l]) 中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标 (x) 跑到坐标 (y) 需要耗费体力 (|y-x|) 。
在一天的训练中，教官一共发布了 (m) 条命令 ((l,r,K)) ，现在你需要计算对于每一条命令，在所有可能的列队方案中，消耗的体力值总和最小是多少。
以下是对题意的一些补充：
- 任何两条命令是无关的，即在一条集合命令结束后，所有学生都会回到自己的休息位置，然后教官才会发出下一条命令。
- 在集合的时候，可能有编号不在 ([l,r]) 内的学生处在区间 ([K,K+r-l]) 中，这时他会自己跑开，且跑动的距离不记在消耗的体力值总和中。
题解
显然，不改变原相对顺序更优。
因此答案为 (sumlimits_{i=l}^r{a_i+rk_i-k-1}) 。
把这个式子拆掉绝对值，就变为了向左跑和向右跑的两种情况。
在可持久化权值线段树上记录 (sum a_i) 即可。
(mathrm{Code})
从今天起更改码风。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500007;
const int maxs = 11000007;
const int s = 1000000;
int n, T;
int rt[maxn];
int ls[maxs], rs[maxs], cnt;
int size[maxs];
LL sum[maxs];
void Insert(int &x ,int l, int r, int val) {
ls[++cnt] = ls[x], rs[cnt] = rs[x], size[cnt] = size[x] + 1, sum[cnt] = sum[x] + (LL)val;
x = cnt;
if(l == r) return ;
int mid = (l + r) >> 1;
if(val <= mid) Insert(ls[x], l, mid, val);
else Insert(rs[x], mid + 1, r, val);
}
int k;
LL Query(int rt1, int rt2, int l, int r, int st) {
if(size[rt1] - size[rt2] == 0) return 0ll;
LL sz = size[rt1] - size[rt2], sigma = sum[rt1] - sum[rt2];
if(l >= k + st) return sigma - sz * (2 * st + 2 * k + sz - 1) / 2;
if(r <= k + st + sz - 1) return sz * (2 * st + 2 * k + sz - 1) / 2 - sigma;
int mid = (l+r) >> 1;
return Query(ls[rt1], ls[rt2], l, mid, st) + Query(rs[rt1], rs[rt2], mid + 1, r, st + size[ls[rt1]] - size[ls[rt2]]);
}
void Init(void) {
scanf("%d%d", &n, &T);
for(int i = 1, x; i <= n; i++) {
scanf("%d", &x);
rt[i] = rt[i-1];
Insert(rt[i], 1, s, x);
}
}
void Work(void) {
while(T--) {
int l, r;
scanf("%d%d%d", &l, &r, &k);
printf("%lld
",Query(rt[r], rt[l-1], 1, s, 0));
}
}
int main() {
Init();
Work();
return 0;
}