qwq

MLE 80 pts，#2 #10 过不去。

悬关 qwq。

已经卡了一早上了，求调。

#include<bits/stdc++.h>

#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

using namespace std;

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

void openFile() {
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}

void fastio() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
}

void init() {
//  openFile();
    fastio();
}

const int N = 6e5 + 10;
const int M = 2e7 + 10;

struct ST { 

    int lg[N], n, F[20][N];

    void init(int x) {
        n = x;
        L(i, 2, n) lg[i] = lg[i>>1]+1;
        L(i, 1, lg[n]) L(j, 1, n) F[i][j] = max(F[i-1][j], F[i-1][j+(1<<i-1)]);
    }

    int query(int l, int r) {
        int k = lg[r-l+1];
        return max(F[k][l], F[k][r-(1<<k)+1]);
    }

}st;

struct block {

    int a[M], sz, bel[M], pos[M], pre[M], suf[M], n, id;

    ll F[M];

    void buildST() {
        int cur = 0, id = 1;
        pos[0] = -1;
        L(i, 1, n) {
            st.F[0][id] = max(st.F[0][id], a[i]);
            bel[i] = id;
            if(bel[i] != bel[i-1])
              pos[i] = 0;
            else 
              pos[i] = pos[i-1] + 1;
            if(++cur == sz)
              cur = 0, id++;
        }
        if(n % sz == 0) id--;
        st.init(id);
    }

    void buildSubPre() {
        L(i, 1, n)
          if(bel[i] != bel[i-1])
           pre[i] = a[i];
          else 
           pre[i] = max(pre[i-1], a[i]);
        R(i, n, 1)
          if(bel[i] != bel[i+1])
           suf[i] = a[i];
          else 
           suf[i] = max(suf[i+1], a[i]);
    }

    void buildBlock() {
        static int s[100], tp;
        L(i, 1, n) {
            if(bel[i] != bel[i-1]) {
                tp = 0;
            }
            else F[i] = F[i-1];
            while(tp && a[s[tp]] <= a[i]) F[i] &= ~(1ull << pos[s[tp--]]);
            s[++tp] = i;
            F[i] |= (1ull << pos[i]);
        }
    }

    void init() {
        L(i, 1, n) a[i] = read();
        sz = log2(n)*1.5;
        buildST();
        buildSubPre();
        buildBlock();

    }

    int qmx(int l, int r) {
        int bl = bel[l], br = bel[r];
        if(bl != br) {
            int ans1 = 0, ans2 = 0;
            if(br - bl > 1) ans1 = st.query(bl+1, br-1);
            ans2 = max(suf[l], pre[r]);
            return max(ans1, ans2);
        }
        else 
          return a[l + __builtin_ctz(F[r] >> pos[l])];
    }
}R;

int m, s;
void Main() {
    cin >> R.n >> m >> s;
    srand(s);
    R.init();
    unsigned ll ans = 0;
    int l, r;
    while(m--) {
        l = read() % R.n + 1;
        r = read() % R.n + 1;
        if(l > r) swap(l, r);
        ans += R.qmx(l, r);
    }
    cout << ans << '\n';
}

signed main() {
    init();
    int T = 1;
    while(T--)
      Main();
    return 0;
}