题解：ABC013D 阿弥陀

闲话：这是 AtCoder 宣传片里的题，被我找到了！

先考虑 D=1，明显可以 O(M) 模拟预处理出在最上面的每个位置往下走会走到什么位置，之后每次就可以 O(1) 查询了。

当 D>1 时，可以依赖预处理的数据每次 O(D) 暴力查询。又注意到每次对所有位置进行的变换操作是一样的，可以倍增后用类似快速幂的方法优化到 O(\log D)。

时间复杂度 O(M+N\log D)。

核心代码：

//By: OIer rui_er
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)

const int N = 2e5 + 5;

int n, m, d, a[N], p[N], f[30][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> d;
    rep(i, 1, m) cin >> a[i];
    rep(i, 1, n) p[i] = i;
    rep(i, 1, m) swap(p[a[i]], p[a[i] + 1]);
    rep(i, 1, n) f[0][p[i]] = i;
    rep(j, 1, 29) rep(i, 1, n) f[j][i] = f[j - 1][f[j - 1][i]];
    rep(i, 1, n) {
        int u = i;
        per(j, 29, 0) if((d >> j) & 1) u = f[j][u];
        cout << u << endl;
    }
    return 0;
}