1. 题面描述
给定长为 \(n\) 的序列,\(m\) 次询问,查询区间最大值。
\(n,m\le 10^7\),数据随机。
2. 分析
经典的静态区间最小值问题,经典题目配经典算法,考虑到 ST 表和笛卡尔树。
而时间复杂度为 \(O(nlogn)\) 的 ST 表无法通过本题,于是考虑笛卡尔树。
首先构建一颗笛卡尔树。
根据笛卡尔树性质可知,对于区间 \([l,r]\),最大值即为笛卡尔树上 \(lca(l,r)\) 的值。
说明:
根据二叉搜索树性质,可知 \(l\le lca(l,r)\le r\),满足最大值在 \([l,r]\) 范围内。
根据大根堆性质,可知 \(lca(l,r)\) 为区间 \([l,r]\) 的最大值。
于是问题就转变为 \(n\) 个节点的树,\(m\) 次询问,查询 LCA。
这里可以选择 Tarjan 算法离线以 \(O(m)\) 的时间复杂度求解 LCA。
不过因为本体数据随机,笛卡尔树期望树高为 \(logn\) 数量级。同时询问随机,每次询问所查询的 LCA 不会过深,于是可以考虑从根开始暴力寻找 LCA。经测试,可以通过本题。
3. 代码
#include <bits/stdc++.h>
using namespace std;
const int N=20000005;
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 n,m,s,top;
int a[N],son[N][2],sta[N];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m>>s;
srand(s);
for (int i=1; i<=n; i++) {
a[i]=read();
while (top && a[sta[top]]<a[i]) son[i][0]=sta[top--];
if (top) son[sta[top]][1]=i;
sta[++top]=i;
}
int rt=sta[1];
unsigned long long ans=0;
while (m--) {
int l=read()%n+1,r=read()%n+1;
if (l>r) swap(l,r);
int p=rt;
while (true) {
if (l<=p && p<=r) {ans+=a[p]; break;}
p=son[p][p<l];
}
}
cout<<ans<<'\n';
return 0;
}
本文完。
标签:由乃救,le,洛谷,笛卡尔,题解,最大值,lca,LCA,z1 From: https://www.cnblogs.com/XeRnHe/p/16974338.html