(Analysis by Benjamin Qi)

First simulate the $M$ reversals in $O(NM)$ (or $O(N+M\log N)$ with a lazy balanced binary search tree, but that is outside the scope of silver). After this, let $p[i]$ denote the $i$-th cow from the right. It suffices to find

$$p^K[i]=\overbrace{p[p[\cdots p[i]\cdots]]}^{K\text{ times}}$$
for every $i$. To compute this expression for a single index $i$, first find the minimum positive integer $x$ such that $p^x[i]=i$. We can refer to the sequence
$$i,p[i],p^2[i],\ldots,p^{x-1}[i]$$
Now it is easy to compute $p^K[j]=p^{K\pmod{x}}[j]$ for all $j$ located on the cycle in $O(x)$ time.

As every index of the permutation lies on exactly one cycle, the sum of the cycle lengths is equal to $N$, meaning that this part of the solution runs in $O(N)$ time.

Dhruv Rohatgi's code:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 100000

int N,M,K;
int l[100],r[100];
int p[MAXN];
int cc[MAXN];
int pos[MAXN];
vector<int> A[MAXN+1];
int ans[MAXN];

int main() {
freopen("swap.in","r",stdin);
freopen("swap.out","w",stdout);
cin >> N >> M >> K;
for(int i=0;i<M;i++) {
cin >> l[i] >> r[i];
l[i]--,r[i]--;
}
for(int i=0;i<N;i++) {
p[i] = i;
for(int j=0;j<M;j++)
if(p[i] >= l[j] && p[i] <= r[j])
p[i] = r[j] + l[j] - p[i];
}
int C = 1;
for(int i=0;i<N;i++) if(!cc[i]) {
cc[i] = C;
A[C].push_back(i);
int j = p[i];
if(j != i) pos[j] = 1;
while(j != i) {
A[C].push_back(j);
cc[j] = C;
if(p[j]!=i) pos[p[j]] = 1 + pos[j];
j = p[j];
}
C++;
}
for(int i=0;i<N;i++)
ans[A[cc[i]][(pos[i] + K)%A[cc[i]].size()]] = i;
for(int i=0;i<N;i++)
cout << ans[i]+1 << '\n';

}


An alternative approach is to use binary exponentiation. Calculate $p^{2^k}[i]$ for each non-negative integer $k$ such that $2^k\le K$, and then combine the appropriate permutations together to get $p^K[k]$. This approach runs in $O(N\log K)$ time.

Nick Wu's code:

import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("swap.out")));
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] to = new int[n];
{
int[] l = new int[n];
for(int i = 0; i < n; i++) l[i] = i;
while(m-- > 0) {
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
while(a < b) {
int t = l[a];
l[a] = l[b];
l[b] = t;
a++;
b--;
}
}
for(int i = 0; i < n; i++) to[i] = l[i];
}
int[] ret = new int[n];
for(int i = 0; i < n; i++) ret[i] = i+1;
while(k > 0) {
if(k%2 == 1) {
ret = apply(ret, to);
}
k /= 2;
if(k > 0) to = apply(to, to);
}
for(int val: ret) pw.println(val);
pw.close();
}

public static int[] apply(int[] l, int[] op) {
int[] ret = new int[l.length];
for(int i = 0; i < ret.length; i++) {
ret[i] = l[op[i]];
}
return ret;
}
}