HDU 5063 Operation the Sequence (역방향 사상)

Operation the Sequence
제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=5063
문제 풀이 방향:
BestCoder 공식 문제 풀이:
조회 횟수 가 50 회 를 초과 하지 않 는 다 는 것 을 알 게 되면 조회 위치 에서 역 주 행 을 할 수 있 고 최초 서열 의 위 치 를 발견 한 다음 에 역 주 행 을 하면 현재 조 회 를 구 할 수 있다.
값, 한 그룹의 데이터 에 대한 복잡 도 는 약 O (50 * n) 입 니 다.
제목 의 이 말 에 주의 하 세 요. Type 4: Q i query current value of a [i], this operator will have at most 50. 그리고 폭력 으로 직접 풀 수 있다 는 것 을 알 게 되 었 습 니 다.
AC 코드:

#include <iostream>
#include <cstdio>
#define MOD 1000000007
using namespace std;

typedef long long ll;
int n,m,ans;
int op[100010];

int fun1(int x){  //           
    int odd = n>>1;
    if(n&1)
        odd++;
    if(x <= odd)
        return 2*x-1;
    else
        return 2*(x-odd);
}

int fun2(int x){ //           
    return n-(x-1);
}

ll solve(ll x){
    int t = 0;
    for(int i = ans-1; i >= 0; i--){
        if(op[i] == 1)
            x = fun1(x);
        else if(op[i] == 2)
            x = fun2(x);
        else
            t++;
    }
    for(int i = 1; i <= t; i++)
        x = x*x%MOD;      //       
    return x;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ans = 0;
        cin>>n>>m;
        for(int i = 0; i < m; i++){
            char c;
            int d;
            cin>>c>>d;
            if(c=='O')
                op[ans++] = d;
            else
                cout<<solve((ll)d)<<endl;
        }
    }
    return 0;
}