DDOSvoid's Blog

Luogu P3509 [POI2010]ZAB-Frog

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P3509

原题翻译有几个地方没有讲清楚

数轴上的n个点的坐标是升序给出的

Solution

首先能够注意到m非常大

另外能够发现跳一次之后就与原来的点没关系了

由此可以联想到倍增，由于空间不够，我们把第二维滚动一下

另外的难点就是如何向距当前点第k小的点

能够发现前k小的k+1(算上自己)个点一定是一个连续的区间，我们直接维护一个长度为k+1的区间即可，第k小的点一定位于端点

当我们从i转移到i+1的时候，左端点和右端点只有可能增加，简单判断即可，复杂度 $O(n)$

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
#include <iostream>
#include <cstdio>
#include <cctype>
#define maxn 1000010
#define gc getchar
#define ll long long 
using namespace std;

ll read() {
    ll x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
}

int n, k; ll m; 

ll a[maxn]; 

int st[maxn][2];

int ans[maxn]; 
int main() {
    n = read(); k = read(); m = read(); 
    for (int i = 1; i <= n; ++i) a[i] = read(); 
    int l = 1, r = k + 1; 
    for (int i = 1; i <= n; ++i) {
        while (r < n && a[r + 1] - a[i] < a[i] - a[l]) ++l, ++r;
        st[i][0] = a[r] - a[i] > a[i] - a[l] ? r : l; 
    }
    for (int i = 1; i <= n; ++i)
        if (m & 1) ans[i] = st[i][0];
        else ans[i] = i; 
    for (int j = 1; j < 32; ++j) {
        int t1 = j & 1, t2 = t1 ^ 1;
        for (int i = 1; i <= n; ++i) 
            st[i][t1] = st[st[i][t2]][t2];
        for (int i = 1; i <= n; ++i)
            if (m >> j & 1) ans[i] = st[ans[i]][t1]; 
    }
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
    return 0;
}