AT_abc253_g [ABC253G] Swap Many Times

思路

首先，不难看出一个规律，就是对于一个序列 $a$，如果它将操作所有以 $x$ 为第一关键字的二元组，那么序列的 $a_{x \sim n}$ 将循环右移一位。（注意，在这里的 $x$ 指的是在 $1 \sim (n - 1)$ 中的任意一个定值）

那么，我们就可以将编号分别为 $l \sim r$ 的这些二元组分为三组：

1. $(x_1,y_1) \sim (x_1,n)$，其中 $(x_1,y_1)$ 为编号为 $l$ 的二元组。
2. $(x_1 + 1,x_1 + 2) \sim (x_2,n)$，其中 $(x_2,n)$ 为编号不大于 $r$ 的最后一个完整操作区间的最后一个二元组。（完整操作区间表示对于一个 $x$，$(x,x + 1) \sim (x,n)$ 都会被取到的二元组区间）
3. $(x_2 + 1,x_2 + 2) \sim (x_2 + 1,y_2)$，其中 $(x_2 + 1,y_2)$ 为编号为 $r$ 的二元组。

然后分别维护这三种情况即可：

1. 首先，定义 $sum_i = \sum_{j = 1}^{n - i}(n - j)$，那么，我们可以二分得出二元组 $(x_1,y_1)$，然后暴力维护 $(x_1,y_1) \sim (x_1,n)$ 即可。时间复杂度 $\Theta(n)$。
2. 由上文的规律，我们只需要将每种状态循环右移一位即可，时间复杂度 $\Theta(n \sqrt n)$，考虑优化。在这里先举一个例子，那么我们可以用两个 vector $A,B$ 维护此过程（其中 $A$ 表示循环右移时最后的元素走到序列前面的元素，$B$ 表示循环右移时没有走到序列前面的元素），对于每一次循环右移，都会将 $B$ 中的最后一个元素放在 $A$ 的末尾，时间复杂度 $\Theta(\sqrt n)$。然后将 $A,B$ 拼起来得到当前序列 $a$。需要注意的是，$B$ 的初始状态是将 $x_1 \sim n$ 放入，因为在 $x_1$ 之前的根本不会动。
3. 将剩下的操作次数全部花光即可。

Code

#include <bits/stdc++.h>  
#define int long long  
#define re register  
  
using namespace std;  
  
const int N = 2e5 + 10;  
int n,l,r;  
int sum[N],arr[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 1) + (r << 3) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline void init(){//预处理 sum 数组   
    for (re int i = 1,k = n - 1;i < n;i++,k--) sum[i] = sum[i - 1] + k;  
}  
  
signed main(){  
    n = read();  
    l = read();  
    r = read();  
    init();  
    for (re int i = 1;i <= n;i++) arr[i] = i;  
    int a = lower_bound(sum + 1,sum + n/*注意这里只能不能写 + 1，因为 sum[n] = 0，加上后 sum 数组不有序无法二分*/,l) - sum;//找出 (x1,y1)   
    int b = a + l - sum[a - 1];  
    int cnt = 1;  
    while (cnt <= (r - l + 1) && b <= n){//暴力维护 (x1,y1) ~ (x1,n)   
        swap(arr[a],arr[b]);  
        cnt++;  
        b++;  
    }  
    int i = a + 1;  
    vector<int> A,B;//维护中间完整段   
    for (re int j = i;j <= n;j++) B.push_back(arr[j]);  
    while (sum[i] <= r && i < n){  
        if (B.empty()) break;  
        A.push_back(B.back());  
        B.pop_back();  
        i++;  
    }  
    for (auto x:A) arr[++a] = x;//更新新的序列   
    for (auto x:B) arr[++a] = x;  
    cnt = r - sum[i - 1];  
    for (int j = 1,k = i + 1;j <= cnt && k <= n;j++,k++) swap(arr[i],arr[k]);//暴力维护剩余的操作次数   
    for (re int i = 1;i <= n;i++) printf("%lld ",arr[i]);  
    return 0;  
}