思路
首先，不难看出一个规律，就是对于一个序列 \(a\)，如果它将操作所有以 \(x\) 为第一关键字的二元组，那么序列的 \(a_{x \sim n}\) 将循环右移一位。（注意，在这里的 \(x\) 指的是在 \(1 \sim (n - 1)\) 中的任意一个定值）
那么，我们就可以将编号分别为 \(l \sim r\) 的这些二元组分为三组：
- \((x_1,y_1) \sim (x_1,n)\)，其中 \((x_1,y_1)\) 为编号为 \(l\) 的二元组。
- \((x_1 + 1,x_1 + 2) \sim (x_2,n)\)，其中 \((x_2,n)\) 为编号不大于 \(r\) 的最后一个完整操作区间的最后一个二元组。（完整操作区间表示对于一个 \(x\)，\((x,x + 1) \sim (x,n)\) 都会被取到的二元组区间）
- \((x_2 + 1,x_2 + 2) \sim (x_2 + 1,y_2)\)，其中 \((x_2 + 1,y_2)\) 为编号为 \(r\) 的二元组。
然后分别维护这三种情况即可：
- 首先，定义 \(sum_i = \sum_{j = 1}^{n - i}(n - j)\)，那么，我们可以二分得出二元组 \((x_1,y_1)\)，然后暴力维护 \((x_1,y_1) \sim (x_1,n)\) 即可。时间复杂度 \(\Theta(n)\)。
- 由上文的规律，我们只需要将每种状态循环右移一位即可，时间复杂度 \(\Theta(n \sqrt n)\)，考虑优化。在这里先举一个例子，那么我们可以用两个
vector\(A,B\) 维护此过程（其中 \(A\) 表示循环右移时最后的元素走到序列前面的元素，\(B\) 表示循环右移时没有走到序列前面的元素），对于每一次循环右移，都会将 \(B\) 中的最后一个元素放在 \(A\) 的末尾，时间复杂度 \(\Theta(\sqrt n)\)。然后将 \(A,B\) 拼起来得到当前序列 \(a\)。需要注意的是，\(B\) 的初始状态是将 \(x_1 \sim n\) 放入，因为在 \(x_1\) 之前的根本不会动。 - 将剩下的操作次数全部花光即可。
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;
}