Swapity Swapity Swap

    1#include <bits/stdc++.h>
    2using namespace std;
    3int main(){
    4    ios::sync_with_stdio(0); cin.tie(0);
    5    int N, M; long long K;
    6    cin >> N >> M >> K;
    7    vector<pair<int,int>> seg(M);
    8    for(int i = 0; i < M; i++){
    9        int L, R; cin >> L >> R;
    10        seg[i] = {L, R};
    11    }
    12    // Build pos after one routine, position newPos holds oldPos
    13    vector<int> pos(N + 1);
    14    iota(pos.begin(), pos.end(), 0); // pos[i] = i
    15    for(auto [L, R] : seg){
    16        for(int i = 0; i < (R - L + 1) / 2; i++){
    17            swap(pos[L + i], pos[R - i]);
    18        }
    19    }
    20    // Q's perpose is mapping oldPos to newPos after one routine
    21    vector<int> Q(N + 1);
    22    for(int newPos = 1; newPos <= N; newPos++){
    23        int oldPos = pos[newPos];
    24        Q[oldPos] = newPos;
    25    }
    26 
    27    // Binary lifting up[i][v] = Q^(2^i)(v)
    28    const int LOG = 60;
    29    vector<vector<int>> up(LOG, vector<int>(N + 1));
    30    for(int v = 1; v <= N; v++) up[0][v] = Q[v];
    31    for(int i = 1; i < LOG; i++){
    32        for(int v = 1; v <= N; v++){
    33            up[i][v] = up[i - 1][up[i - 1][v]];
    34        }
    35    }
    36    // For each label s (initially at position s), jump K times along Q
    37    vector<int> res(N + 1, 0);
    38    for(int s = 1; s <= N; s++){
    39        int cur = s;
    40        long long x = K;
    41        for(int i = 0; x; i++, x >>= 1){
    42            if(x & 1) cur = up[i][cur];
    43        }
    44        res[cur] = s; // label s ends at position cur
    45    }
    46    for(int i = 1; i <= N; i++) cout << res[i] << '\n';
    47    return 0;
    48}
    49