题解 P6823 【「EZEC-4」zrmpaul Loves Array】

· · 题解

由于我在打比赛时太菜想不出正解，所以只能打暴力qwq，结果一不小心用暴力过了，来发篇题解。

首先我们来看看裸的暴力，暴力sort+暴力reverse，时间复杂度为\operatorname{O}(mn\log n)，面对如此强大的数据范围很明显卡不过去。

考虑优化qwq，首先我们发现在一次排序操作之后，前面的所有操作都将没有用，所以我们找到最后一个排序操作，然后从这个操作开始执行，我们发现加了这个优化之后程序快了很多，但是还是卡不过去。

那么接下来再分享一个优化，即对于连续的k次reverse，可以将其转化为(k \operatorname{mod}2)次reverse，这个东西挺好证的吧，因为连续的两次reverse可以相互抵消。

大的优化至此已经结束，这个程序加上火车头已经可以过了，但是在真实的比赛中是用不了火车头的qwq，那么我们来卡常：

然后......就过了qwq，AC 记录。

代码：

#include <bits/stdc++.h>
using namespace std;
int n, m, opt[1000005], x[1000005], y[1000005], a[1000005], start = 1, cnt;
void rvs()
{
    for (register int i = 1; i <= n / 2; ++i)
        swap(a[i], a[n - i + 1]);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (register int i = 1; i <= n; ++i)
        a[i] = i;
    for (register int i = 1; i <= m; ++i)
    {
        cin >> opt[i];
        if (opt[i] == 3)
            cin >> x[i] >> y[i];
        if (opt[i] == 1 || opt[i] == 2)
            start = i + 1;
    }
    if (opt[start - 1] == 2)
        rvs();
    for (register int i = start; i <= m; ++i)
    {
        if (opt[i] == 4)
            ++cnt;
        else
        {
            if (cnt % 2)
                rvs();
            swap(a[x[i]], a[y[i]]);
            cnt = 0;
        }
    }
    if (cnt % 2)
        rvs();
    for (register int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
}

话说数据理论上讲可以把我的代码卡到\operatorname{O}(mn)，但是我深得面向数据编程的精髓（逃