P3793 由乃救爷爷做题记录

hlsnqdmz · 2025-05-12 21:52:33 · 个人记录

调了一个晚上终于调出来了……

看到题干我们能想到~~坦克世界~~ST 表，但是它 n\log{n} 的空间能气死 20000000 的数据，而我们又刚好学了分块，所以我们使用分块减小 ST 表的空间，使其能够通过这道题。

首先还是老样子，分成多个长度为 \sqrt{n} 的块，然后顺带求出每个块往前跳 2^0 步（包括自身）的最大值，然后我们分类讨论 l 和 r（懒得画图了）：

在相邻的块中（|---l---|---r---|）：记录每个点在自己块里的前缀最大值和后缀最大值：
```
for (rnt i = 1, last = 0; i <= b[n]; last = 0, i++)
for (rnt j = (i - 1) * len + 1; j <= i * len; j++)
pre[j] = last = max(last, a[j]);
for (rnt i = b[n], last = 0; i >= 1; last = 0, i--)
for (rnt j = i * len; j >= (i - 1) * len + 1; j--)
suf[j] = last = max(last, a[j]);
```
这里要注意 j 最大值超过了 20000000，比它多个 3256，所以数组别开小了。然后答案就从 l 的后缀最大值和 r 的前缀最大值中找。
在遥远的块中（|l|-|-|-|-|-|-|-|-|r|）：以上面答案为基础，使用 ST 表的查询，但是有一点不同：
```
int query(int l, int r)
{
if (l >= r)
    return 0;
int k = lg[r - l];
return max(st[l][k], st[r - (1 << k)][k]);
}
```
另外记得传参时 l 要加一：query(b[l] + 1, b[r])，这样可以处理上面那种情况，至于写法为什么不同，我也不知道。

好了，改出来了，我们发现 l 和 r 所在块都已经算过了，所以我们要算 l+1\sim r-1 的范围最大值，当两者相等时不需要返回 0，而是继续求值（毕竟还有一块呢），然后其他就跟正常 ST 一样了。
belike：

int query(int l, int r)
{
    if (l > r)
        return 0;
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}
query(b[l] + 1, b[r] - 1)

其他就没什么了，贴出代码：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 30000005
#define M 1000000007
using namespace std;

inline ll read()
{
    ll x = 0, f = 1;
    char ch = gr();
    while (ch < '0' || ch > '9')
        ch == '-' ? f = -1, ch = gr() : ch = gr();
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
    return x * f;
}

inline void write(unsigned ll x)
{
    static int sta[39], top = 0;
    do
        sta[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        pr(sta[top--] ^ 48);
}

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 rd()
{
    using namespace GenHelper;
    int a = rand_() & 32767;
    int b = rand_() & 32767;
    return a * 32768 + b;
}
int n, m, s, l, r, len;
int a[N], b[N], lg[10000], pre[N], suf[N];
int st[10000][40];
unsigned ll ans;

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

int main()
{
    n = read(), m = read(), s = read(), len = sqrt(n);
    srand(s), lg[0] = -1;
    for (rnt i = 1; i <= n; i++)
        a[i] = rd(), b[i] = (i - 1) / len + 1, st[b[i]][0] = max(st[b[i]][0], a[i]);
    for (rnt i = 1; i <= b[n]; i++)
        lg[i] = lg[i >> 1] + 1;
    for (rnt i = 1, last = 0; i <= b[n]; last = 0, i++)
        for (rnt j = (i - 1) * len + 1; j <= i * len; j++)
            pre[j] = last = max(last, a[j]);
    for (rnt i = b[n], last = 0; i >= 1; last = 0, i--)
        for (rnt j = i * len; j >= (i - 1) * len + 1; j--)
            suf[j] = last = max(last, a[j]);
    for (rnt i = 1; i <= lg[b[n]]; i++)
        for (rnt j = 1; j <= b[n] - (1 << i) + 1; j++)
            st[j][i] = max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
    for (rnt i = 1; i <= m; i++)
    {
        l = rd() % n + 1, r = rd() % n + 1;
        int mx = 0;
        if (l > r)
            swap(l, r);
        if (b[l] == b[r])
            for (rnt i = l; i <= r; i++)
                mx = max(mx, a[i]);
        else
        {
            mx = max(pre[r], suf[l]);
            mx = max(mx, query(b[l] + 1, b[r] - 1));
        }
        ans += mx;
    }
    write(ans);
    return 0;
}

P3793 由乃救爷爷 做题记录

P3793 由乃救爷爷做题记录