关于这道题目卡 \(O(n\log n)\) 但是放 \(O(n^2)\) 我也是很疑惑。
我们发现，题目要求的是字典序最小的序列。但凡涉及了字典序最小，答案或多或少的都会带点贪心思想。
那我们也来贪一贪。考虑当前枚举到第 \(i\) 个点，如果后面有比它更小的数，那显然把它们交换过来是更优的。如果有多个，那显然也是最小的那一个交换过来是最优的。如果最小的还有多个，那肯定把当前这个和最后一次出现的交换是最优的。
同时，由于题目要求 \(P\) 是 \(\lang 1,2,\dots,n\rang\) 的一个子序列，所以假设我们这次将 \(i\) 和 \(j\) 位置上的元素交换了，接下来就不能对下标 \(k\le j\) 的元素动手动脚了，下一个枚举到的点就是 \(j + 1\) 了。
如果这么说还不明白的话，我们模拟一下样例：
样例一：
1 1 3 0 0 1 3
↑ ↑
i j
起初，i = 1，我们发现 i 以后最小的数是 0，它是小于 a[i] 的，而 j = 5 是 0 最后一次出现的位置，所以将 a[1] 和 a[5] 交换。
0 1 3 0 1 1 3
↑
i
接下来 i 移动到 6 的位置，发现后面没有小于 a[i] 的数了。
0 1 3 0 1 1 3
↑
i
最后，i 移动到 7，程序结束。
样例二：
2 8 0 6 2 2 1 7 8 3
↑ ↑
i j
起初，i = 1，我们发现 i 以后最小的数是 0，它是小于 a[i] 的，而 j = 3 是 0 最后一次出现的位置，所以将 a[1] 和 a[3] 交换。
0 8 2 6 2 2 1 7 8 3
↑ ↑
i j
接下来 i 移动到 4 的位置，我们发现 i 以后最小的数是 1，它也是小于 a[i] 的，而 j = 7 是 0 最后一次出现的位置，所以将 a[4] 和 a[7] 交换。
0 8 2 1 2 2 6 7 8 3
↑ ↑
i j
接下来 i 移动到 8 的位置，我们发现 i 以后最小的数是 3，它同样是小于 a[i] 的，而 j = 10 是 3 最后一次出现的位置，所以将 a[8] 和 a[10] 交换。
0 8 2 1 2 2 6 3 8 7
↑
i
最后，i 移动到 11，程序结束。
至于实现，我们可以维护一个后缀最小值最后一次出现的位置 \(p\)，而且是最后一次出现的位置，然后将 \(a_i\) 与 \(a_{p_i}\) 交换，再令 \(i = p_i + 1\)，然后重复以上步骤直到 \(i \ge n\)。
我的程序中是用 \(nxt\) 来存储后缀最小值最后一次出现的位置的，大家看的时候转换一下就好：
#include<bits/stdc++.h>
#define MAXN 10000010
using namespace std;
typedef unsigned long long ull;
int n, m, k;
int a[MAXN], nxt[MAXN];
namespace Generator{
ull k1, k2;
int thres;
inline ull xorShift128Plus() {
ull k3 = k1, k4 = k2;
k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
inline void generate() {
for (int i = 1; i <= n; ++i) {
a[i] = xorShift128Plus() % thres;
}
}
}
int main(){
scanf("%d%llu%llu%d", &n, &Generator::k1, &Generator::k2, &Generator::thres);
Generator::generate();
nxt[n] = n;
for(int i = n - 1; i >= 1; i--){
if(a[i] < a[nxt[i + 1]]) nxt[i] = i;
else nxt[i] = nxt[i + 1];
}
for(int i = 1; i < n; i++){
if(a[nxt[i + 1]] < a[i]){
swap(a[i], a[nxt[i + 1]]);
i = nxt[i + 1];
}
}
ull ans = 0;
for(int i = 1; i <= n; i++) ans += (ull)i * a[i];
printf("%llu\n",ans);
return 0;
}