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个盒子左边盒子的序号和右边盒子的序号

参考代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <set>

 #include <map>

 #include <queue>

 #include <stack>

 #include <sstream>

 #include <cctype>

 #include <cassert>

 #include <typeinfo>

 #include <utility>    //std::move()

 using std::cin;

 using std::cout;

 using std::endl;

 const int INF = 0x7fffffff;

 const double EXP = 1e-;

 const int MS = ;

 typedef long long LL;

 int left[MS], right[MS];

 int n, m, kase;

 void link(int l, int r)

 {

     right[l] = r;

     left[r] = l;

 }

 int main()

 {

     int kase = ;

     while (cin >> n >> m)

     {

         for (int i = ; i <= n; i++)

         {

             left[i] = i - ;

             right[i] = (i + ) % (n + );

         }

         right[] = ;

         left[] = n;

         int op, x, y, inv = ;

         while (m--)

         {

             cin >> op;

             if (op == )

                 inv = !inv;

             else

             {

                 cin >> x >> y;

                 if (op ==  && right[y] == x)

                     std::swap(x, y);

                 if (op !=  && inv)

                     op =  - op;

                 if (op ==  && x == left[y])

                     continue;

                 if (op ==  && x == right[y])

                     continue;

                 int lx = left[x], rx = right[x], ly = left[y], ry = right[y];

                 if (op == )

                 {

                     link(lx, rx);

                     link(ly, x);

                     link(x, y);

                 }

                 else if (op == )

                 {

                     link(lx, rx);

                     link(y, x);

                     link(x, ry);

                 }

                 else if (op == )

                 {

                     if (right[x] == y)

                     {

                         link(lx, y);

                         link(y, x);

                         link(x, ry);

                     }

                     else

                     {

                         link(lx, y);

                         link(y, rx);

                         link(ly, x);

                         link(x, ry);

                     }

                 }

             }

         }

         int  b = ;

         LL ans = ;

         for (int i = ; i <= n; i++)

         {

             b = right[b];

             if (i % )

                 ans += b;

         }

         if (inv&&n %  == )

             ans = (LL)n*(n + ) /  - ans;

         cout << "Case " << ++kase << ": " << ans << endl;

     }

     return ;

 }

巴特西

Boxes in a Line

Boxes in a Line

Input

Output

Sample Input

Sample Output

最新文章

热门文章