【HDOJ】5063 Operation the Sequence

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 #define MAXN 100005
 6 #define MOD 1000000007
 7 int que[MAXN], front = 0, rear = 0;
 8 int n;
 9 
10 void query(int index) {
11     int r = rear;
12     int square = 0;
13     int half = (n+1)>>1;
14 
15     while (r-- > front) {
16         if (que[r] == 3) {
17             ++square;
18         } else if (que[r] == 2) {
19             index = n+1-index;
20         } else {
21             if (index > half) {
22                 index = (index - half)*2;
23             } else {
24                 index = 2*index - 1;
25             }
26         }
27     }
28     __int64 ret = index%MOD;
29     for (int i=0; i<square; ++i) {
30         ret = ret*ret%MOD;
31     }
32     printf("%I64d
", ret);
33 }
34 
35 int main() {
36     int t, m;
37     int x;
38     char cmd[3];
39 
40     scanf("%d", &t);
41     while (t--) {
42         rear = 0;
43         scanf("%d%d", &n, &m);
44         while (m--) {
45             scanf("%s %d", cmd, &x);
46             if (cmd[0] == 'Q') {
47                 query(x);
48             } else {
49                 que[rear++] = x;
50             }
51         }
52     }
53     return 0;
54 }