11.17 鲜花（RMQ专题）
哈哈，回家看到朴彩英这个歌绷不住了。
不是吧，姐？
推歌-박채영《아파트》
채영이가 좋아하는
랜덤 게임
랜덤 게임
Game start
아파트 아파트
아파트 아파트
아파트 아파트
Uh, uh huh uh huh
아파트 아파트
아파트 아파트
아파트 아파트
Uh, uh huh uh huh
Kissy face, kissy face
Sent to your phone but,
I'm trying to kiss your lips for real
Red hearts, red hearts
That’s what I’m on yeah
Come give me something I can feel
Oh oh oh
Don't you want me like I want you, baby
Don't you need me like I need you now
Sleep tomorrow but tonight go crazy
All you gotta do is just meet me at the
아파트 아파트
아파트 아파트
아파트 아파트
Uh, uh huh uh huh
아파트 아파트
아파트 아파트
아파트 아파트
Uh, uh huh uh huh
It’s whatever it’s whatever it’s whatever you like
Turn this 아파트 into a club
I’m talking drink, dance, smoke, freak, party all night
건배 건배 girl what’s up
Oh oh oh
Don't you want me like I want you, baby
Don't you need me like I need you now
Sleep tomorrow but tonight go crazy
All you gotta do is just meet me at the
아파트 아파트
아파트 아파트
아파트 아파트
Uh, uh huh uh huh
아파트 아파트
아파트 아파트
아파트 아파트
Uh, uh huh uh huh
Hey so now you know the game
Are you ready?
Cause I’m comin to get ya
Get ya, get ya
Hold on, hold on
I’m on my way
Yeah yeah yeah yeah yeah
I’m on my way
Hold on, hold on
I’m on my way
Yeah yeah yeah yeah yeah
I’m on my way
Don't you want me like I want you, baby
Don't you need me like I need you now
Sleep tomorrow but tonight go crazy All
you gotta do is just meet me at the
아파트 아파트
아파트 아파트
아파트 아파트
Just meet me at the
(Uh huh uh huh)
아파트 아파트
아파트 아파트
아파트 아파트
Just meet me at the
(Uh huh uh huh)
아파트 아파트
아파트 아파트
아파트 아파트
Just meet me at the
(Uh huh uh huh)
아파트 아파트
아파트 아파트
아파트 아파트
Uh, uh huh uh huh
省流： \(HANGRY\_Sol\) 牌拍子大大地好用！
RMQ 专题
四毛子（Four Russian）算法
据说是四个俄罗斯科学家发明的。
还是举区间最大值的例子。
我们把这么个区间分块，分成左边散块，中间整块，右边散块。
然后如果我们把块长调成 \(\frac{\log_2n}{2}\) 然后发现这个可以 \(\mathcal{O}(n)\) 预处理（ \(\mathcal{O}(\frac{n}{len}\log{\frac{n}{len}})\) ）， \(\mathcal{O}(1)\) 查询。
但是这个区间在一个块里面怎么办？
然后这四只毛熊就开始唐了。
首先噢，先建一颗大根笛卡尔树。
然后统计一下 \(dfs\) 序。发现 \(LCA\) 就是最大值。
转化成 \(dfs\) 序，即 \(\pm RMQ\) 问题。
对于长度为 \(len = \frac{\log_2n}{2}\) 的块来说，他只有 \(\mathcal{O}(\sqrt N)\) 种不同的情况吧。
我们直接对于每个块的情况状压，最后统计一下第 \(i\) 种， \([l, r]\) 的最大值。
时间复杂度 \(\mathcal{O}(n)\) , 空间复杂度 \(\mathcal{O}(N)\) 。
然后你就发现不仅难写，常数还贼大。
伯约的这真有单 log 跑得快吗？
然后考虑怎么优化一下这个东西。
我们发现这个题的瓶颈就在于两个端点在一个块时的情况。
然后发现块长为 \(\log\) 级，也就是说 \(r - l \le \log n\)
那我们直接跑残疾 \(ST\) 表，跑到 \(\log\log n\) 大概 \(2 \times 10 ^ 7\) 才 \(4\) 的样子。
额……这是不是能叫…… \(O(n)\) ?
有兴趣的可以去由乃救爷爷草草，应该可以过的。
四毛子 Pro Max : 二毛子
感觉这个东西就应该叫四毛娘吧，毕竟阉割了……
这个和四毛子后面我想的的那个东西异曲同工，都是在对于两个端点在同一个块时的优化。
考虑一个显然的性质，对于一个区间 \([l, r]\) , 其区间最值的位置肯定是
\[\min_{1 \le i \le l}maxpos_{i, r} (maxpos_{i, r} \ge l) \]其实为什么考虑这个呢，就是因为开不下，想想有没有什么能够优化空间的。
这个 \(maxpos\) 显然可单调栈维护。发现这个后，直接将 \(maxpos_{i, r}\) 在 \(r\) 处状压。查的时候先将 \(l\) 前的清掉，然后再找第一个 \(1\)（函数 builtin_ctzll(ull) 可以完成这个操作，复杂度为 \(\log\log\) 或常数）。
然后就做完了。这个写了，可以给码。
CODE of 由乃救爷爷
#include <bits/stdc++.h>
#define int unsigned int
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int N = 2e7 + 100;
int a[N], n, m; ull s;
int st[21], top;
namespace GenHelper {
unsigned z1, z2, z3, z4, b;
inline 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);
}
}
inline void srand(unsigned x) {
using namespace GenHelper;
z1 = x; z2 = (~ x) ^ 0x233333333U; z3 = x ^ 0x1234598766U; z4 = (~ x) + 51;
}
inline int read() {
using namespace GenHelper;
int a = rand_() & 32767;
int b = rand_() & 32767;
return a * 32768 + b;
}
#define l(x) ((x - 1) << 6 | 1)
#define r(x) (x << 6)
#define belong(x) ((x + 63) >> 6)
int ST[__lg(N >> 6) + 1][N >> 6];
ull val[N]; int lg[N];
int Prefix[N], Suffix[N];
inline int MaxST(int l, int r) {
if (l > r) return 0;
int k = lg[r - l + 1];
return max(ST[k][l], ST[k][r - (1 << k) + 1]);
}
inline void In() {
int tot = belong(n), Maxer;
for (int i = 2; i <= n; ++ i) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= tot; ++ i) {
Maxer = 0;
for (int j = l(i); j <= r(i); ++ j) Maxer = max(Maxer, a[j]), Prefix[j] = Maxer;
Suffix[r(i)] = a[r(i)];
for (int j = r(i) - 1; j >= l(i); -- j) Suffix[j] = max(Suffix[j + 1], a[j]);
ST[0][i] = Maxer;
}
for (int j = 1; j <= __lg(belong(n)); ++ j)
for (int i = 1; i <= tot - (1 << j) + 1; ++ i)
ST[j][i] = max(ST[j - 1][i], ST[j - 1][i + (1 << (j - 1))]);
for (int j = 1; j <= tot; ++ j) {
top = 0;
for (int i = l(j); i <= r(j); ++ i) {
if (i > l(j)) val[i] = val[i - 1];
while (top && a[st[top]] <= a[i]) {
val[i] ^= (1ULL << (st[top] - l(j))); -- top;
}
val[i] |= (1ULL << (i - l(j)));
st[++ top] = i;
}
}
}
inline int Query(int x, int y) {
if (belong(x) == belong(y)) return a[x + __builtin_ctzll(val[y] >> (x - l(belong(x))))];
return max(max(Prefix[y], Suffix[x]), MaxST(belong(x) + 1, belong(y) - 1));
}
signed main() {
cin >> n >> m >> s;
srand(s); int l, r; ull ans = 0;
for (int i = 1; i <= n; ++ i) a[i] = read();
In();
while (m --) {
l = read() % n + 1, r = read() % n + 1;
if (l > r) swap(l, r);
ans += Query(l, r);
}
cout << ans;
}
p
