final

原始文件为 cpp 代码，本文是转换后的 Markdown 文件。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <math.h>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
const int maxn = 100005;

struct node
{
    int left, right;
};

node* node_arr[maxn];
node* head;
node* tail;

void init(int n)
{
    for(int i = 0; i <= n+1; ++i)
    {
        delete node_arr[i];
        node_arr[i] = (node *)malloc(sizeof(node));
        node_arr[i]->left = i - 1;
        node_arr[i]->right = i + 1;
    }
    node_arr[n + 1]->right = -1;
    node_arr[0]->left = -1;

    head = node_arr[0];
    tail = node_arr[n + 1];
}

void print(int n)
{
    int cur = head->right;
    while(node_arr[cur]->right != -1)
    {
        printf("%d ", cur);
        cur = node_arr[cur]->right;
    }
    printf("\n");
}

long long sum(int n)
{
    long long result = 0;
    int cur = head->right;

    for(int i = 0; i < (n+1)/2; ++i)
    {
        result += cur;
        cur = node_arr[cur]->right;
        cur = node_arr[cur]->right;
    }
    return result;
}

void choice_01(int X, int Y);
void choice_02(int X, int Y);
void choice_03(int X, int Y);
void choice_04(int n);

int main(void)
{
    freopen("in.txt", "r", stdin);
    int n, m; int count = 0;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        init(n);

        for(int i = 0; i < m; ++i)
        {
            int choice; scanf("%d", &choice);
            if(choice == 4)
            {
                choice_04(n);
            }else
            {
                int X, Y; scanf("%d%d", &X, &Y);
                if(choice == 1) choice_01(X, Y);
                if(choice == 2) choice_02(X, Y);
                if(choice == 3) choice_03(X, Y);
            }
        }
        // print(n);
        printf("Case %d: %ld\n", ++count, sum(n));
    }
    return 0;
}

void choice_01(int X, int Y)
{
    node* x_node = node_arr[X];
    node* y_node = node_arr[Y];

    if(X != y_node->left)
    {
        node* x_left = node_arr[x_node->left];
        node* y_left = node_arr[y_node->left];
        node* x_right = node_arr[x_node->right];
        node* y_right = node_arr[y_node->right];

        x_left->right = x_node->right;
        x_right->left = x_node->left;

        x_node->left = y_node->left;
        y_left->right = X;

        x_node->right = Y;
        y_node->left = X;
    }
}

void choice_02(int X, int Y)
{

    node* x_node = node_arr[X];
    node* y_node = node_arr[Y];

    if(Y != x_node->left)
    {
        node* x_left = node_arr[x_node->left];
        node* y_left = node_arr[y_node->left];
        node* x_right = node_arr[x_node->right];
        node* y_right = node_arr[y_node->right];

        x_left->right = x_node->right;
        x_right->left = x_node->left;

        x_node->right = y_node->right;
        y_right->left = X;

        x_node->left = Y;
        y_node->right = X;
    }
}

void choice_03(int X, int Y)
{
    node* x_node = node_arr[X];
    node* y_node = node_arr[Y];

    node* x_left = node_arr[x_node->left];
    node* y_left = node_arr[y_node->left];
    node* x_right = node_arr[x_node->right];
    node* y_right = node_arr[y_node->right];

    int y_left_num = y_node->left;
    int y_right_num = y_node->right;

    x_left->right = Y;
    y_node->left = x_node->left;

    x_right->left = Y;
    y_node->right = x_node->right;

    y_left->right = X;
    x_node->left = y_left_num;

    y_right->left = X;
    x_node->right = y_right_num;
}

void choice_04(int n)
{
    for(int i = 0; i <= n+1; ++i)
    {
        node* cur_node = node_arr[i];
        int tmp = cur_node->left;
        cur_node->left = cur_node->right;
        cur_node->right = tmp;
    }
    node* tmp = head;
    head = tail;
    tail = tmp;
}