前缀和

容易得到暴力做法：从 $1$ 到 $n$ 枚举 $i$，每次判断 $i$ 是不是区间 $[i,n]$ 的最小值。

• 如果是，令 $i \leftarrow i+1$。
• 如果不是，交换 $a_i$ 和区间 $[i,n]$ 中最后一个最小值 $a_j$，令 $i \leftarrow j+1$。

时间复杂度 $O(n^2)$，瓶颈是找 $[i,n]$ 的最小值。由于只需要后缀最小值，预处理区间 $[i,n]$ 中最后一个最小值所在位置，记为 $p_i$。

如果 $a_i$ 不等于 $a_{p_i}$ 则交换 $a_i$ 和 $a_{p_i}$，不应根据 $i$ 是否等于 $p_i$ 进行判断，因为 $a_i$ 的值可能与 $a_{p_i}$ 的值相同。时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
unsigned long long k1,k2,ans;
int n,thres,a[10000005],p[10000005];
inline unsigned long long xorShift128Plus(){
    unsigned long long k3=k1,k4=k2;
    k1=k4,k3^=k3<<23,k2=k3^k4^(k3>>17)^(k4>>26);
    return k2+k4;
}
int main(){
    scanf("%d%llu%llu%d",&n,&k1,&k2,&thres);
    for(int i=1;i<=n;i++) a[i]=xorShift128Plus()%thres;
    p[n]=n;
    for(int i=n-1;i>=1;i--) p[i]=a[i]<a[p[i+1]] ? i:p[i+1];
    for(int i=1;i<=n;i++) if(a[i]>a[p[i]]) swap(a[i],a[p[i]]),i=p[i];
    for(int i=1;i<=n;i++) ans+=1ull*i*a[i];
    printf("%llu\n",ans);
    return 0;
}