Boxes in a Line

You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4
kinds of commands:
? 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )
? 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )
? 3 X Y : swap box X and Y
? 4: reverse the whole line.
Commands are guaranteed to be valid, i.e. X will be not equal to Y .
For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing
2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1.
Then after executing 4, then line becomes 1 3 5 4 6 2

Input

There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m
(1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.

Output

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n
from left to right.

Sample Input

6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4

Sample Output

Case 1: 12
Case 2: 9
Case 3: 2500050000

直接模拟肯定会超时用stl中的链表也超时只能用数组自己模拟一个双向链表了 le[i],ri[i]分别表示第i个盒子左边盒子的序号和右边盒子的序号

参考代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <string>
  7 #include <vector>
  8 #include <set>
  9 #include <map>
 10 #include <queue>
 11 #include <stack>
 12 #include <sstream>
 13 #include <cctype>
 14 #include <cassert>
 15 #include <typeinfo>
 16 #include <utility>    //std::move()
 17 using std::cin;
 18 using std::cout;
 19 using std::endl;
 20 const int INF = 0x7fffffff;
 21 const double EXP = 1e-8;
 22 const int MS = 100005;
 23 typedef long long LL;
 24 int left[MS], right[MS];
 25 int n, m, kase;
 26 void link(int l, int r)
 27 {
 28     right[l] = r;
 29     left[r] = l;
 30 }
 31 
 32 int main()
 33 {
 34     int kase = 0;
 35     while (cin >> n >> m)
 36     {
 37         for (int i = 1; i <= n; i++)
 38         {
 39             left[i] = i - 1;
 40             right[i] = (i + 1) % (n + 1);
 41         }
 42         right[0] = 1;
 43         left[0] = n;
 44         int op, x, y, inv = 0;
 45         while (m--)
 46         {
 47             cin >> op;
 48             if (op == 4)
 49                 inv = !inv;
 50             else
 51             {
 52                 cin >> x >> y;
 53                 if (op == 3 && right[y] == x)
 54                     std::swap(x, y);
 55                 if (op != 3 && inv)
 56                     op = 3 - op;
 57                 if (op == 1 && x == left[y])
 58                     continue;
 59                 if (op == 2 && x == right[y])
 60                     continue;
 61                 int lx = left[x], rx = right[x], ly = left[y], ry = right[y];
 62                 if (op == 1)
 63                 {
 64                     link(lx, rx);
 65                     link(ly, x);
 66                     link(x, y);
 67                 }
 68                 else if (op == 2)
 69                 {
 70                     link(lx, rx);
 71                     link(y, x);
 72                     link(x, ry);
 73                 }
 74                 else if (op == 3)
 75                 {
 76                     if (right[x] == y)
 77                     {
 78                         link(lx, y);
 79                         link(y, x);
 80                         link(x, ry);
 81                     }
 82                     else
 83                     {
 84                         link(lx, y);
 85                         link(y, rx);
 86                         link(ly, x);
 87                         link(x, ry);
 88                     }
 89                 }
 90             }
 91             
 92         }
 93         int  b = 0;
 94         LL ans = 0;
 95         for (int i = 1; i <= n; i++)
 96         {
 97             b = right[b];
 98             if (i % 2)
 99                 ans += b;
100         }
101         if (inv&&n % 2 == 0)
102             ans = (LL)n*(n + 1) / 2 - ans;
103         cout << "Case " << ++kase << ": " << ans << endl;
104     }
105     return 0;
106 }