P3793 题解

· · 题解

题解 P3793 由乃救爷爷

补充一篇其他题解没有出现的做法，思路来自 A_zjzj 老师 在 mx 北京最后一天课上的讲解，加上了一些理解，以及来自 Firacode 完善的代码。

题意

题意很简单，给定一个长度为 n 的序列，m 次询问 RMQ。
数据范围：n,m \le 2 \times 10^7。

做法

考虑将询问离线下来，按照右端点 r 排序，从前往后扫的过程中维护一个单调栈。由于单调栈维护的是递减序列，当扫描到一个询问时，我们希望对于 l 向后找到第一个位于单调栈内的元素，那么这个元素就是我们希望求出的答案。

具体实现

现在难点就在具体的实现方式上了，我们来考虑每个点。

比较显然的一点，我们不能使用 sort 进行排序，不难想到把每个位置上的询问维护 vector，但实测会 MLE，因此考虑使用计数排序。

接下来的问题就是需要维护出从 l 向后第一个位于单调栈中的元素，其实就是维护一个连续段。

考虑把出栈操作看作删除一个元素，那么我们希望找到从 l 向后第一个没有被删除的元素，这个操作可以使用并查集实现。

具体的，当我们删除掉一个位置 i 时，我们把 i 和 i + 1 合并，想要查询只需要查询 i + 1 的祖先即可，总时间复杂度可以做到 O(n \alpha)，记得路径压缩。

虽然跑的比较慢，需要看评测机心情，但也是一种做法。

实现细节

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e7 + 2;
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[maxn],rk[maxn],Max[maxn];
short dep[maxn];
pair<int, int> b[maxn];
int fa[maxn];
stack<int> st;
int getf(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = getf(fa[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    unsigned long long ans = 0;
    int n,m,s;
    cin >> n >> m >> s;
    srand(s);
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 1;i <= m;i++)
    {
        int l = read() % n + 1;
        int r = read() % n + 1;
        if(l > r) swap(l,r);
        b[i] = {l, r};
    }
    for(int i = 1;i <= m;i++) ++fa[b[i].second];
       for(int i = 1;i <= n;i++) fa[i] += fa[i - 1];
       for(int i = m;i >= 1;i--) rk[fa[b[i].second]--] = i;
    for(int i = 1;i <= n;i++) fa[i] = Max[i] = i, dep[i] = 1;
    for(int i = 1, j = 1;i <= n;i++)
    {
        while(st.size() && a[st.top()] <= a[i])
        {
            int k = st.top();
            st.pop();
            int fk = getf(k), ft = getf(k + 1);
            if (dep[fk] < dep[ft]) fa[fk] = ft;
            else if (dep[fk] > dep[ft]) fa[ft] = fk, Max[fk] = Max[ft];
            else fa[fk] = ft, dep[ft]++;
            // cout << "---" << fk << ' ' << Max[getf(k)] << ' ' << ft << ' ' << Max[ft] << endl;
        }

        st.push(i);
        while(j <= m && b[rk[j]].second == i) ans += a[Max[getf(b[rk[j]].first)]], ++j;
    }
    cout << ans;
    return 0;
}

据说还有链表维护方式，奈何我太菜了不会使用链表，有想法可以私信评论。

希望对你有所帮助。