洛谷上一道关于st表的题

Question

洛谷P3509，题目描述如下
有 n 个点，升序给出每个点到起点的距离。有编号为 1∼n 的 n 只青蛙分别在第 1∼n 个点上，每次它们会跳到距离自己第 k 远的点上。
如果有相同距离的点，就跳到下标更小的点上。
求跳 m 次之后，第 i 只的青蛙在哪个点上。
输入共一行三个整数：代表 n,k,m。
输出共一行 n 个整数，代表每只青蛙最终所处在的点。

我的代码如下：

#include<iostream>//!!!这里左移最多31位，开1ll可以防止左移运算溢出
#include<cmath>
using namespace std;
int n, k, m;//m极大
typedef unsigned long long ull;
ull a[1000010];
//int dk[1000010];//记录每个第k远的点  最终输出坐标
int nxt[1000010][80];//这里注意第二维的含义，表示向后数不包括自身  存储编号
ull abs(ull i, ull j) {
    return (i > j) ? (i - j) : (j - i);
}
void constructnxt0() {
    //这里注意状态可以递推
    int h = 1,t = k+1;//表示队列头和尾
    nxt[1][0] = k+1;//第一次转移
    int cnt = 1;
    while (cnt < n) {
        cnt++;
        while (t<n&&abs(a[t + 1], a[cnt]) < abs(a[h], a[cnt])) {//
            t++;
            h++;//这里保证间距是K
        }
        if (abs(a[cnt], a[h]) >= abs(a[cnt], a[t])) {//这里等号代表优先级
            nxt[cnt][0] = h;
        }
        else {
            nxt[cnt][0] = t;
        }
    }
}
void constructst() {
    for (int j = 1;j < 63;j++) {
        for (int i = 1;i <= n;i++) {
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        }
    }
}
int query(ull m, int i) {//编号为i的点转移m次后的位置
    for (int j = 62;j >= 0;j--) {
        if ((1ll<<j) < m) {//
            m -= (1ll<<j);
            i = nxt[i][j];
        }
    }
    return nxt[i][0];
}
int main() {
    cin >> n >> k >> m;
    for (int i = 1;i <= n;i++) {
        scanf("%d", &a[i]);
    }
    constructnxt0();
    constructst();
    for (int i = 1;i <= n;i++) {
        cout << query(m, i) << " ";
    }
}

57分，不知道错在哪，请指教

Answer 1

hang-li 晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

你的代码有一个小错误： 你在scanf的语句中使用了%d，但实际上数组a是ull型，应该使用%llu。

另外，你的构造函数constructnxt0()和constructst()看起来是没有问题的。但是函数query()中的循环条件有一个小错误。应该是j > 0 而不是 j >= 0。

下面是修改后的代码：

#include<iostream>//!!!这里左移最多31位，开1ll可以防止左移运算溢出
#include<cmath>
using namespace std;
int n, k, m;//m极大
typedef unsigned long long ull;
ull a[1000010];
int nxt[1000010][80];//这里注意第二维的含义，表示向后数不包括自身 存储编号
ull abs(ull i, ull j) {
    return (i > j) ? (i - j) : (j - i);
}
void constructnxt0() {
    //这里注意状态可以递推
    int h = 1,t = k+1;//表示队列头和尾
    nxt[1][0] = k+1;//第一次转移
    int cnt = 1;
    while (cnt < n) {
        cnt++;
        while (t<n&&abs(a[t + 1], a[cnt]) < abs(a[h], a[cnt])) {//
            t++;
            h++;//这里保证间距是K
        }
        if (abs(a[cnt], a[h]) >= abs(a[cnt], a[t])) {//这里等号代表优先级
            nxt[cnt][0] = h;
        }
        else {
            nxt[cnt][0] = t;
        }
    }
}
void constructst() {
    for (int j = 1;j < 63;j++) {
        for (int i = 1;i <= n;i++) {
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        }
    }
}
int query(ull m, int i) {//编号为i的点转移m次后的位置
    for (int j = 62;j > 0;j--) {
        if ((1ll<<j) < m) {//
            m -= (1ll<<j);
            i = nxt[i][j];
        }
    }
    return nxt[i][0];
}
int main() {
    cin >> n >> k >> m;
    for (int i = 1;i <= n;i++) {
        scanf("%llu", &a[i]);
    }
    constructnxt0();
    constructst();
    for (int i = 1;i <= n;i++) {
        cout << query(m, i) << " ";
    }
}

经过修改后，代码应该能够正确地输出每只青蛙最终所处的点。希望能帮到你！