P4559-[JSOI2018]列队

2020-11-01 约 1014 字预计阅读 3 分钟次阅读

P4559-[JSOI2018]列队

题目:

题目描述:

作为一名大学生，九条可怜在去年参加了她人生中的最后一次军训。

军训中的一个重要项目是练习列队，为了训练学生，教官给每一个学生分配了一个休息位置。每次训练开始前，所有学生都在各自的休息位置休息，但是当教官发出集合命令后，被点到的学生必须要到指定位置集合。

为了简化问题，我们把休息位置和集合位置抽象成一根数轴。一共有 $n$ 个学生，第 $i$ 个学生的休息位置是 $a_i$。每一次命令，教官会指定一个区间 $[l,r]$ 和集合点 $K$ ，所有编号在 $[l,r]$ 内的学生都必须赶到集合点列队。在列队时，每一个学生需要选择 $[K,K+r-l]$ 中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标 $x$ 跑到坐标 $y$ 需要耗费体力 $\vert y-x \vert$ 。

在一天的训练中，教官一共发布了 $m$ 条命令 $(l,r,K)$ ，现在你需要计算对于每一条命令，在所有可能的列队方案中，消耗的体力值总和最小是多少。

以下是对题意的一些补充：

任何两条命令是无关的，即在一条集合命令结束后，所有学生都会回到自己的休息位置，然后教官才会发出下一条命令。
在集合的时候，可能有编号不在 $[l,r]$ 内的学生处在区间 $[K,K+r-l]$ 中，这时他会自己跑开，且跑动的距离不记在消耗的体力值总和中。

输入格式:

第一行输入两个整数 $n,m$。

第二行 $n$ 个整数 $a_i$ 表示学生的休息位置。保证学生休息的位置两两不同。

接下来 $m$ 行每行三个整数 $l,r,K$ 表示一条命令。

输出格式:

对于每一条命令输出一行一个整数表示最小的体力值总和。

样例:

样例输入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
// Problem: P4559 [JSOI2018]列队
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4559
// Memory Limit: 500 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
typedef long long LL;
const int MN = 500005;
const int MS = 11000005;

int n, m, s = 1000000;
int rt[MN];
int ls[MS], rs[MS], mx[MS], mn[MS], sz[MS], cnt;
LL sum[MS];

void Add(int &rt, int l, int r, int p)
{
    ls[++cnt] = ls[rt], rs[cnt] = rs[rt], sz[cnt] = sz[rt] + 1, sum[cnt] = sum[rt] + p, rt = cnt;
    if (l == r)
        return;
    int mid = l + r >> 1;
    if (p <= mid)
        Add(ls[rt], l, mid, p);
    else
        Add(rs[rt], mid + 1, r, p);
}

LL Qur(int rt1, int rt2, int l, int r, int f, int k)
{
    if (!(sz[rt1] - sz[rt2]))
        return 0;
    LL Sz = sz[rt1] - sz[rt2], Sum = sum[rt1] - sum[rt2];
    if (l >= k + f)
        return Sum - (2 * k + 2 * f + Sz - 1) * Sz / 2;
    if (r <= k + f + Sz - 1)
        return (2 * k + 2 * f + Sz - 1) * Sz / 2 - Sum;
    int mid = l + r >> 1, lsz = sz[ls[rt1]] - sz[ls[rt2]];
    return Qur(ls[rt1], ls[rt2], l, mid, f, k) + Qur(rs[rt1], rs[rt2], mid + 1, r, f + lsz, k);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; ++i)
    {
        scanf("%d", &x);
        Add(rt[i] = rt[i - 1], 1, s, x);
    }
    for (int i = 1, l, r, k; i <= m; ++i)
    {
        scanf("%d%d%d", &l, &r, &k);
        printf("%lld\n", Qur(rt[r], rt[l - 1], 1, s, 0, k));
    }
    return 0;
}

目录

P4559-[JSOI2018]列队

P4559-[JSOI2018]列队

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入1:

样例输出1:

思路:

实现: