Boxes in a Line（UVA 12657）

网址如下：

Boxes in a Line - UVA 12657 - Virtual Judge (vjudge.net)

（第三方网站）

发！发！发！（生发器）

做完之后直接TLE，操作都没问题，就是算法上需要优化

而且我感觉我是笨比，因为在执行操作3的时候，如果X、Y紧挨着，如果直接改变值，就会导致半途中目标值改变（比如交换两个数的值的时候不用变量储存其中一个值的话，就会导致失去其中一个数的值）

然后我怎么做的呢？ 分类讨论

然后我一看算法书的做法：直接新增变量记录

我的代码因此又臭又长

至于TLE嘛

因为题目中的操作4非常耗时（毕竟是翻转整个链表）

我的代码老老实实操作，操作4多起来就超时了

算法书给出的优化：

增加一个标记inv，表示有没有执行过操作4（如果inv = 1时再执行一次操作4，则inv变为0）。这样，当op（操作指令）为1和2且inv = 1时，只需把op变成3 - op（注意操作3不受inv影响）即可。最终输出时要根据inv的值进行不同处理

提示：如果数据结构的某一个操作很耗时，有时可以用加标记的方式处理，而不需要真的执行那个操作。但同时，该数据结构的所以其他操作都要考虑这个标记。

代码如下：

#include<cstdio>
int left[100001], right[100001];
inline void link(int L, int R){right[L] = R; left[R] = L;}

int main(void)
{
    int n, m, kase = 0;
    while(scanf("%d%d", &n, &m) == 2)
    {
        //预处理
        int inv = 0;
        for(int i = 0; i <= n; i++){left[i] = i - 1; right[i] = i + 1;} right[n] = 0;
        for(int i = 0; i < m; i++)
        {
            int command; scanf("%d", &command);
            if(command == 4){inv = (inv + 1) % 2; continue;}
            if(inv && command != 3) command = 3 - command;
            if(command == 1)
            {
                int X, Y; scanf("%d%d", &X, &Y);
                if(right[X] != Y)
                {
                    right[left[X]] = right[X]; left[right[X]] = left[X];
                    right[left[Y]] = X; left[X] = left[Y];
                    link(X, Y);
                }
            }
            else if(command == 2)
            {
                int X, Y; scanf("%d%d", &X, &Y);
                if(left[X] != Y)
                {
                    right[left[X]] = right[X]; left[right[X]] = left[X];
                    left[right[Y]] = X; right[X] = right[Y];
                    link(Y, X);
                }
            }
            else
            {
                int X, Y; scanf("%d%d", &X, &Y);
                if(left[X] == Y)
                {
                    right[left[Y]] = X; left[right[X]] = Y;
                    left[X] = left[Y]; right[Y] = right[X];
                    link(X, Y);
                }
                else if(right[X] == Y)
                {
                    right[left[X]] = Y; left[right[Y]] = X;
                    right[X] = right[Y]; left[Y] = left[X];
                    link(Y, X);
                }
                else
                {
                    right[left[X]] = Y; left[right[X]] = Y;
                    right[left[Y]] = X; left[right[Y]] = X;
                    left[X] ^= left[Y] ^= left[X] ^= left[Y];
                    right[X] ^= right[Y] ^= right[X] ^= right[Y];
                }
            }
        }
        if(inv)
            for(int j = right[0]; j; j = left[j])
                {left[j] ^= right[j] ^= left[j] ^= right[j]; right[0] = j;}
        //输出
        long long ans = 0, pos = 0;
        for(int i = right[0]; i; i = right[i])
            if(++pos % 2) ans += (long long)i;
        printf("Case %d: %lld\n", ++kase, ans);
    }
    return 0;
}

这里用了算法书给出的用数组表示的链表的方法，没有用list容器，是为了练习一下

又学到了一些东西