Prelude

ODT这个东西真是太好用了，以后写暴力骗分可以用，写在这里mark一下。

题目链接：ヽ(✿ﾟ▽ﾟ)ノ

---

Solution

先把原题解贴在这里：(ﾉ*･ω･)ﾉ

简单地说，因为数据是全部随机的，所以一定会有特别多的区间set，就会有很多数字相同，那么我们暴力把相同的数字合并成一个点，合并完之后数组就变得很短，然后对于询问暴力做就可以了。

具体复杂度是什么我也不会证明qwq，所以就把由乃的题解贴上来了qwq，感觉很靠谱的样子。

题解中给的是用STL的set维护缩点后的数组，我感觉不是很好写，就直接用数组维护了。

ddd还写过链表维护的，不过感觉都差不多，反正复杂度都是对的，肯定能过qwq。

---

Code

#include <bits/stdc++.h>

#define dprint printf

using namespace std;

typedef long long ll;

typedef pair<ll,int> pli;

const int MAXN = 100010;

int _w;

void noprint(...) {}

int fpow( int a, int b, int mod ) {

	int c = 1;

	while(b) {

		if( b & 1 ) c = int(1LL * c * a % mod);

		a = int(1LL * a * a % mod);

		b >>= 1;

	}

	return c;

}

int inter( int l1, int r1, int l2, int r2 ) {

	int l = max(l1, l2);

	int r = min(r1, r2);

	return max(r-l+1, 0);

}

int n, m, seed, vmax;

ll a[MAXN];

int rnd() {

	const int MOD = 1e9+7;

	int ret = seed;

	seed = int((1LL * seed * 7 + 13) % MOD);

	return ret;

}

pli b[MAXN];

int sz;

void prelude() {

	sz = 1;

	b[sz-1].first = a[1], b[sz-1].second = 0;

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

		if( b[sz-1].first == a[i] ) {

			++b[sz-1].second;

		} else {

			b[sz].first = a[i], b[sz].second = 1, ++sz;

		}

	}

}

pli c[MAXN];

int csz;

void append( ll x, int cnt ) {

	if( csz && c[csz-1].first == x )

		c[csz-1].second += cnt;

	else

		c[csz].first = x, c[csz].second = cnt, ++csz;

}

void solve1( int l, int r, int x ) {

	int L = 0, R = 0;

	csz = 0;

	for( int i = 0; i < sz; ++i ) {

		L = R+1;

		R = L + b[i].second - 1;

		ll num = b[i].first;

		int cntl = inter(L, l-1, L, R);

		int cnt = inter(L, R, l, r);

		int cntr = inter(r+1, R, L, R);

		if( cntl ) append(num, cntl);

		if( cnt ) append(num+x, cnt);

		if( cntr ) append(num, cntr);

	}

	sz = csz;

	for( int i = 0; i < sz; ++i )

		b[i] = c[i];

}

void solve2( int l, int r, int x ) {

	int L = 0, R = 0;

	csz = 0;

	for( int i = 0; i < sz; ++i ) {

		L = R+1;

		R = L + b[i].second - 1;

		ll num = b[i].first;

		int cntl = inter(L, l-1, L, R);

		int cnt = inter(L, R, l, r);

		int cntr = inter(r+1, R, L, R);

		if( cntl ) append(num, cntl);

		if( cnt ) append(x, cnt);

		if( cntr ) append(num, cntr);

	}

	sz = csz;

	for( int i = 0; i < sz; ++i )

		b[i] = c[i];

}

void solve3( int l, int r, int x ) {

	int L = 0, R = 0;

	csz = 0;

	for( int i = 0; i < sz; ++i ) {

		L = R+1;

		R = L + b[i].second - 1;

		int cnt = inter(L, R, l, r);

		if( cnt ) c[csz++] = pli( b[i].first, cnt );

	}

	sort(c, c+csz);

	L = R = 0;

	for( int i = 0; i < csz; ++i ) {

		L = R+1;

		R = L + c[i].second - 1;

		if( x >= L && x <= R )

			return (void)printf( "%lld\n", c[i].first );

	}

	return assert(0);

}

void solve4( int l, int r, int x, int y ) {

	int L = 0, R = 0, ans = 0;

	for( int i = 0; i < sz; ++i ) {

		L = R+1;

		R = L + b[i].second - 1;

		int cnt = inter(L, R, l, r);

		if( cnt ) ans = int((ans + 1LL * cnt * fpow( int(b[i].first % y), x, y )) % y);

	}

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

}

void output_array() {

	for( int i = 0; i < sz; ++i ) {

		int t = b[i].second;

		while( t-- )

			dprint( "%lld ", b[i].first );

	}

	dprint("\n");

}

int main() {

	_w = scanf( "%d%d%d%d", &n, &m, &seed, &vmax );

	// dprint("Init:\n");

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

		a[i] = rnd() % vmax + 1;

		// dprint("%lld ", a[i]);

	}

	// dprint("\n");

	prelude();

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

		int op, l, r, x, y;

		op = rnd() % 4 + 1;

		l = rnd() % n + 1;

		r = rnd() % n + 1;

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

		if( op == 3 )

			x = rnd() % (r-l+1) + 1;

		else

			x = rnd() % vmax + 1;

		if( op == 4 )

			y = rnd() % vmax + 1;

		if( op == 1 ) solve1(l, r, x);

		else if( op == 2 ) solve2(l, r, x);

		else if( op == 3 ) solve3(l, r, x);

		else if( op == 4 ) solve4(l, r, x, y);

		// dprint("op = %d, l = %d, r = %d, x = %d, y = %d\n", op, l, r, x, y);

		// output_array();

	}

	return 0;

}