Codeforces 669D Little Artem and Dance(뇌)

제목의 뜻
1부터 n까지의 서열을 제시하고 그에게 두 가지 조작이 있다.전체적으로 오른쪽으로 x 칸을 이동한다. 2.짝수 비트의 숫자 교환은 q회 조작을 거친 후의 숫자 서열을 구한다.
사고의 방향
분명히 이 문제는 O(q)로 해야 한다. 첫 번째 사례에서 전체적으로 변하고 있지만 서로 인접한 두 수는 시종일관 함께 있는 것을 발견할 수 있다. 그러나 이것은 정해가 아니다. 왜냐하면 이동하는 자리가 홀수일 때 짝수 교환을 거치면 붙지 않기 때문이다.그리고 나는 아무렇게나 예를 하나 만들었는데 아무리 짝짝이가 같아져도 서로 인접한 수는 한 수의 순서를 사이에 두고 배열된 것을 발견했다. 그리고 변화 과정이 확실히 이렇다는 것을 생각해 보았다.그래서 우리는 1이 어디에 있는지 알면 모든 홀수의 위치를 찾을 수 있고, 2가 어디에 있는지 알면 모든 짝수의 위치를 찾을 수 있으며, 1과 2는 마음대로 찾으면 된다.
코드

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
#define Lowbit(x) ((x)&(-x))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1|1
#define MP(a, b) make_pair(a, b)
const int INF = 0x3f3f3f3f;
const int Mod = 1000000007;
const int maxn = 1e5 + 10;
const double eps = 1e-8;
const double PI = acos(-1.0);
typedef pair<int, int> pii;
int ans[1000007], pos[1000007];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n, q;
    scanf("%d%d", &n, &q);
    int pos1 = 0, pos2 = 1;
    for (int i = 0; i < q; i++)
    {
        int op, len;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d", &len);
            pos1 = (pos1 + len + n) % n;
            pos2 = (pos2 + len + n) % n;
        }
        else
        {
            if ((pos1 + 1) & 1) pos1++;
            else pos1--;
            if ((pos2 + 1) & 1) pos2++;
            else pos2--;
        }
    }
    ans[1] = pos1, ans[2] = pos2;
    pos[pos1] = 1, pos[pos2] = 2;
    for (int i = 3; i <= n; i++)
        ans[i] = (ans[i-2] + 2) % n, pos[ans[i]] = i ;
    for (int i = 0; i < n; i++)
        printf("%d ", pos[i]);
    printf("
");
    return 0;
}