• 欢迎光临~

# 题解：「GLR-R3」雨水

### 前言

`const int MAXN = 712; // Set a right value according to your solution.`

### 正文

#### 解题

Code

``````#include<bits/stdc++.h>
#define ull unsigned long long
#define MAX 10000002
#define INF 999999999
using namespace std;

int n,a[MAX];

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;
}
}

unsigned int key[MAX],pos[MAX];
ull ans;
inline void work()
{
key[n+1]=INF;
for(int i=n;i>=2;i--)
{
key[i]=key[i+1],pos[i]=pos[i+1];
if(a[i]<key[i]) key[i]=a[i],pos[i]=i;
}
int mink,minp;
for(int i=1;i<n;i++)
{
mink=key[i+1],minp=pos[i+1];
if(mink<a[i]) swap(a[i],a[minp]),i=minp;
}
return;
}

int main()
{
scanf("%d",&n);
scanf("%llu %llu %d",&Generator::k1,&Generator::k2,&Generator::thres);
Generator::generate();
work();
for(int i=1;i<=n;i++)
ans+=(unsigned long long)a[i]*i;
cout<<ans;
return (0-0);
}
``````