题面

也就是说, 随机序列RMQ.(\(n \le 8388608\), \(m \le 8*10^6\))

解法

我写了笛卡尔树+tarjan

然而听神仙说, 因为数据随机, 建完树暴力找lca就行, 跑的飞快...吊打std...

还有题解, 真是神仙做法...

设 \(p_i\) 表示比 \(a_i\) 大的前一个数所在的位置,那么 p 构成了一棵树。

若我们需要查询 [l, r] 的答案,只需找到 r 在这棵树上不小于 l 的祖先。于是我们可以按照 l

从大到小排序,一边向上查询祖先一边路径压缩(类似并查集)。

由于树上的每条边至多被压缩一次,复杂度 O(n) 。

我的代码:

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

using namespace std;

#define rep(i,l,r) for(register int i=(l);i<=(r);++i)

#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)

#define il inline

typedef double db;

typedef long long ll;

//---------------------------------------

int n,m;

int gen,p1,p2;

int number(){

    gen=(1LL*gen*p1)^p2;

    return (gen&(n-1))+1;

}

const int nsz=8388700;

int a[nsz],ans[nsz];

struct tnd{int ch[2];}car[nsz];

int rt,pc=0;

int stk[nsz],top=0;

void build(){

	rep(i,1,n){

		while(top&&a[stk[top]]<a[i])car[i].ch[0]=stk[top--];

		car[stk[top]].ch[1]=i;

		stk[++top]=i;

	}

	rt=stk[1],pc=n;

}

struct tq{int t,pr;}qu[nsz*2];

int hd[nsz],pq=1;

void adde(int f,int t){qu[++pq]=(tq){t,hd[f]};hd[f]=pq;}

void adddb(int f,int t){adde(f,t);adde(t,f);}

int fa[nsz];

void init(){rep(i,1,n)fa[i]=i;}

void merge(int a,int b){fa[b]=a;}

int find(int p){return p==fa[p]?p:fa[p]=find(fa[p]);}

int vi[nsz];

void tar(int p){

	vi[p]=1;

	int v;

	rep(i,0,1){

		v=car[p].ch[i];

		if(v==0)continue;

		tar(v);

		merge(p,v);

	}

	for(int i=hd[p];i;i=qu[i].pr){

		if(vi[qu[i].t])

			ans[i/2]=find(qu[i].t);

	}

}

int main() {

//	freopen("max.in", "r", stdin);

//	freopen("max.out", "w", stdout);

	scanf("%d%d", &n, &m);

	scanf("%d%d%d", &gen, &p1, &p2);

	for (int i = 1; i <= n; ++i)

		a[i] = number();

	int l,r;

	for (int i = 1; i <= m; ++i) {

		l = number(), r = number();

		if (l > r) swap(l,r);

		adddb(l,r);

	}

	build();

	init();

	tar(rt);

	ll sum = 0;

	for (int i = 1; i <= m; ++i) {

		sum=(sum+a[ans[i]])%p2;

	}

	sum=sum*p1%p2;

	printf("%lld\n", sum);

}

std:

#include <cstdio>

#include <ctime>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int N = 1e7 + 5;

int n, m;

int gen, cute1, cute2;

int number() {

    gen = (1LL * gen * cute1) ^ cute2;

    return (gen & (n - 1)) + 1;

}

int hd[N], nxt[N], id[N], to[N], cnt;

int ans[N], a[N], p[N], q[N];

int add(int x, int y, int i) {

    ++cnt;

    nxt[cnt] = hd[x];

    to[cnt] = y;

    id[cnt] = i;

    hd[x] = cnt;

}

int getfa(int x, int y) {

    int fa = x;

    for (int i = x; i; i = p[i])

        if (p[i] < y || p[i] == i) {

            fa = i;

            break;

        }

    for (int j, i = x; i != fa; i = j) {

        j = p[i], p[i] = fa;

    }

    return fa;

}

int main() {

    freopen("max.in", "r", stdin);

    freopen("max.out", "w", stdout);

    scanf("%d%d", &n, &m);

    scanf("%d%d%d", &gen, &cute1, &cute2);

    for (int i = 1; i <= n; ++i)

        a[i] = number();

    for (int i = 1; i <= m; ++i) {

        int l = number(), r = number();

        if (l > r) swap(l, r);

        add(l, r, i);

    }

    double t1;

    fprintf(stderr, "%lf\n", t1 = (double)clock()/CLOCKS_PER_SEC);

    int ind = 0;

    for (int i = 1; i <= n; ++i) {

        while (ind && a[q[ind]] <= a[i]) --ind;

        if (ind) p[i] = q[ind];

        else p[i] = i;

        q[++ind] = i;

    }

    for (int i = n; i; --i) {

        for (int j = hd[i]; j; j = nxt[j])

            ans[id[j]] = a[getfa(to[j], i)];

    }

    fprintf(stderr, "%lf\n", (double)clock()/CLOCKS_PER_SEC - t1);

    int sum = 0;

    for (int i = 1; i <= m; ++i)

        (sum += 1LL * ans[i] * cute1 % cute2) %= cute2;

    printf("%d\n", sum);

}