洛谷P3793题解

$\texttt{Description}:$

见题面

$\texttt{Soluton}:$

一眼看上去就是个rmq卡常题，st表显然过不去（lxl不会这么良心的（大雾）

但是众所周知随机数据=用脚趾造数据。

既然st表，考虑其它鬼畜算法。看到由乃题首先应该想到分块。所以我们想到一个十分鬼畜的算法：对整个区间进行分块，st表维护连续若干个块的最小值，对于不完整块，记录前缀后缀和，如果 $l,r$ 在一个块内暴力统计即可。

这样做的期望时间复杂度大概是多少呢？取块长为 $S$（这里假设块长是 $n$ 的约数方便计算时间复杂度），那么期望时间复杂度为 $O(N+(N/S)log(N/S)+m\times (\frac{S^2}{N}+1)\div 2)$。

只要知道期望的定义应该都会推上面的式子。$O(N)$ 是预处理前缀后缀的复杂度，$O((N/S)log(N/S))$ 是st表预处理复杂度，$\frac{S}{N}$ 是 $l,r$ 在同一个区间内的概率，$\frac{S^2}{N}$ 是在同一块内的期望复杂度（从数学上来说这里有一些常数没算进去，但无伤大雅）， 不在一个块的期望复杂度为 $1$，那么总的期望就是 $(\frac{S^2}{N}+1)\div 2$。

块长 $S$ 无脑取 $\sqrt{n}$ 就能做到一个不错的线性复杂度，虽然这个块长不是最优的，但是不管你块长再优，优化的也仅仅是几乎看不出来的常数而已了。

另外 $l>r$ 的情况是交换 $l$ 和 $r$，因为这个我被坑了好久…………

完结撒花~

$\texttt{Code}:$

#include <cstdio>
#include <cmath>

inline int max(const int x, const int y) {return x > y ? x : y;}
inline int min(const int x, const int y) {return x < y ? x : y;}
inline void max2(int& x, const int y) {if (x < y) x = y;}

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

int a[20000005], b[5005], c[20000005], d[20000005], s[5005], st[5005][15], S;
inline int Query(const int L, const int R) {
	int k(log2(R - L + 1));
	return max(st[L][k], st[R - (1 << k) + 1][k]);
}
inline int query(const int l, const int r) {
	int i((l - 1) / S + 1), j((r - 1) / S + 1), ans(0);
	if (i == j) {
		for (int k(l); k <= r; ++ k) ans = max(ans, a[k]);
		return ans;
	}
	if (i + 1 < j) ans = Query(i + 1, j - 1);
	return max(ans, max(d[l], c[r]));
}

int main() {
	int n, m, s;
	unsigned long long ans(0);
	scanf("%d%d%d", &n, &m, &s);
	S = sqrt(n);
	srand(s);
	int len(ceil(n * 1.0 / S));
	for (int i(1); i <= n; ++ i) max2(b[(i - 1) / S + 1], a[i] = read());
	for (int i(1); i <= len; ++ i) {
		int st((i - 1) * S + 1), ed(min(n, i * S));
		c[st] = a[st];
		for (int j(st + 1); j <= ed; ++ j) c[j] = max(c[j - 1], a[j]);
		d[ed] = a[ed];
		for (int j(ed - 1); j >= st; -- j) d[j] = max(d[j + 1], a[j]);
	}
	for (int i(1); i <= len; ++ i) st[i][0] = b[i];
	for (int j(1); 1 << j <= len; ++ j)
	for (int i(1); i + (1 << j) - 1 <= len; ++ i)
	st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
	while (m --) {
		int l, r;
		l = read() % n + 1, r = read() % n + 1;
		if (l > r) l ^= r ^= l ^= r;
		ans += query(l, r);
	}
	printf("%llu", ans);
	return 0;
}