写了拿来备忘……虽然应该没有什么用。
众所周知，对于 RMQ 问题来说，ST 表可以非常轻松地做到 (O(nlog n)) 预处理 (O(1)) 查询，线段树可以轻松做到 (O(n)) 预处理 (O(log n)) 查询还能支持修改。
然后这个 (O(n)) 预处理 (O(1)) 查询的算法我实现出来效率比前面两个慢了 10 倍。
所以大家可以离开了。
言归正传，接下来介绍算法流程。
首先把整个序列的笛卡尔树建出来，然后我们就成功地把区间求最值变成了两点求 LCA。
然后求 LCA 的话我们如果直接树剖的话时间复杂度还是 (O(log n)) 的，不过在这里我们就已经可以通过离线 + Tarjan 来得到一个线性的做法了。
那么如果要强制在线呢？
所以我们再把树的欧拉序搞出来，于是我们就成功地把树上求 LCA 变成了区间求最值。
问题做到这里我们成功地将问题规模扩大到原来的 2 倍，非常优秀。
然后我们考虑对欧拉序分块，假设每 (B) 个数分为一块，那么整个序列就被分成了 (O(frac{n}{B})) 块，这一部分用 ST 表的话就可以做到 (O(frac{n}{B}log n)) 的时间复杂度。
那么这里如果我们取 (B=log n) 的话 ST 表的预处理时间复杂度就变成了 (O(n))。
于是我们整块就可以 (O(1)) 查询了。
那么对于散块呢？
也许你可以回答能够预处理块内前缀后缀，然后就可以 (O(1)) 查询散块了。
那么对于两个端点在同一个块中的情况呢？
好像没有什么办法。
那么我们前面大费周章地做了这么大的转换干什么事哦！
我们发现，将整棵树的欧拉序弄出来之后，如果以深度为关键字的话，相邻两个数的差的绝对值恰好为 (1)。
这就意味着最多只有 (2^B) 中不同的散块方案。
如果我们暴力预处理的话那么可以做到 (O(2^BB^2))，把 (B=log n) 带进去得到 (O(nlog^2 n))，我们成功地获得了一个比原来更劣的时间复杂度。
这个时候我们会发现为什么 (B) 一定要是 (log n) 呢？所以我们把 (B) 取值为 (frac{log n}{2})，接下来我们看一看时间复杂度发生了什么样的变化。
ST 表的预处理成功地变成了原来的两倍常数，然而这并不影响时间复杂度。
但是后面的暴力预处理就变成了 (O(sqrt{n}log^2 n)) 的时间复杂度，并且这个复杂度是低于线性的，可以忽略。
然后我们就成功地做到了 (O(n)) 预处理 (O(1)) 在线查询的 RMQ！
是不是非常激动！然后当你实现了这个算法之后，你会发现如果你直接暴力分块的话（甚至直接在笛卡尔树上暴力从根开始向下跳）在数据随机的情况下跑得不知道比这个算法快到哪里去了。
也许你会说“那么我可以专门造数据对着块大小卡！”
然后你忘了读入的时间复杂度是 (O(nlog V))（后面多了一个 (log) 的原因是读入数字的长度）。
嗯，复杂度瓶颈在于读入，非常好。
也许你可以说那我可以只输入 (0sim 9) 之间的数！
嗯，但是跑不过就是跑不过，不管怎么样都跑不过。
不过扯了这么多，还是放一下代码吧。
洛谷上有一道模板题，是P3793 由乃救爷爷。
然后这份代码就是那一道题的。
别误会了，MLE 不说，极限数据本机要跑 20s，我这代码没救了。
只是拿来参考而已。
#include <cstdio>
#include <cassert>
/******************************************/
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;
}
/******************************************/
template<typename Elem>
Elem min(Elem a,Elem b){
return a<b?a:b;
}
template<typename Elem>
Elem max(Elem a,Elem b){
return a>b?a:b;
}
template<typename Elem>
void swap(Elem &a,Elem &b){
Elem t=a;
a=b;
b=t;
}
typedef unsigned long long ull;
const int Maxn=20000000;
const int Maxk=13;
const int Inf=0x7fffffff;
struct Value{
int minn,id;
Value(int _minn=Inf,int _id=-1){
minn=_minn;
id=_id;
}
friend bool operator <(Value a,Value b){
return a.minn<b.minn;
}
};
int n,m,s;
Value f_max[Maxk<<1|1][(Maxn<<1)/Maxk+6];
int log_2[(Maxn<<1)/Maxk+6];
int f_len;
int dfn[Maxn+5];
Value lis[Maxn<<1|5];
int lis_len;
int a[Maxn+5];
int st[Maxn+5],top;
int lson[Maxn+5],rson[Maxn+5];
int dep[Maxn+5];
int root;
int mn_pos[1<<Maxk|5][Maxk+5][Maxk+5];
int b_mask[((Maxn<<1)-1)/Maxk+6];
int find_belong(int x){
return (x-1)/Maxk+1;
}
int find_bel_l(int x){
return (x-1)*Maxk+1;
}
int find_bel_r(int x){
return min(lis_len,x*Maxk);
}
void init_dfs(int u,int fa){
dep[u]=dep[fa]+1;
lis[++lis_len]=Value(dep[u],u);
dfn[u]=lis_len;
if(lson[u]){
init_dfs(lson[u],u);
lis[++lis_len]=Value(dep[u],u);
}
if(rson[u]){
init_dfs(rson[u],u);
lis[++lis_len]=Value(dep[u],u);
}
}
void init_f(){
f_len=0;
for(int i=1;i<=lis_len;i+=Maxk){
Value val=Value();
for(int j=i;j<min(i+Maxk,lis_len);j++){
val=min(val,lis[j]);
}
f_len++;
f_max[0][f_len]=val;
}
for(int i=1;(1<<i)<=f_len;i++){
for(int j=1;j+(1<<i)-1<=f_len;j++){
f_max[i][j]=min(f_max[i-1][j],f_max[i-1][j+(1<<(i-1))]);
}
}
for(int i=2;i<=f_len;i++){
log_2[i]=log_2[i>>1]+1;
}
}
Value query_f(int l,int r){
int k=log_2[r-l+1];
return min(f_max[k][l],f_max[k][r-(1<<k)+1]);
}
void init_pos(){
for(int mask=0;mask<(1<<(Maxk-1));mask++){
for(int i=0;i<Maxk;i++){
for(int j=i;j<Maxk;j++){
int val=0,minn=0,pos=i;
for(int k=i;k<j;k++){
if((mask>>(Maxk-2-k))&1){
val++;
}
else{
val--;
}
if(val<minn){
minn=val;
pos=k+1;
}
}
mn_pos[mask][i][j]=pos;
}
}
}
}
void init_mask(){
for(int i=1;i<=f_len;i++){
b_mask[i]=0;
for(int j=find_bel_l(i)+1;j<find_bel_l(i)+Maxk;j++){
if(j<=find_bel_r(i)){
if(lis[j].minn==lis[j-1].minn+1){
b_mask[i]=(b_mask[i]<<1|1);
}
else{
b_mask[i]=(b_mask[i]<<1);
}
}
else{
b_mask[i]=(b_mask[i]<<1|1);
}
}
}
}
void init(){
init_dfs(root,0);
init_f();
init_pos();
init_mask();
}
int query(int l,int r){
if(find_belong(l)==find_belong(r)){
int bel=find_belong(l);
return a[lis[mn_pos[b_mask[bel]][l-find_bel_l(bel)][r-find_bel_l(bel)]+find_bel_l(bel)].id];
}
int bel_l=find_belong(l),bel_r=find_belong(r);
if(bel_l+1<=bel_r-1){
int ans=a[query_f(bel_l+1,bel_r-1).id];
ans=max(ans,query(l,find_bel_r(bel_l)));
ans=max(ans,query(find_bel_l(bel_r),r));
return ans;
}
else{
return max(query(l,find_bel_r(bel_l)),query(find_bel_l(bel_r),r));
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
srand(s);
for(int i=1;i<=n;i++){
a[i]=read();
if(root==0||a[i]>a[root]){
root=i;
}
}
top=0;
for(int i=1;i<=n;i++){
while(top&&a[st[top]]<a[i]){
lson[i]=st[top];
top--;
}
rson[st[top]]=i;
st[++top]=i;
}
init();
ull ans=0;
for(int i=1;i<=m;i++){
int l=read()%n+1,r=read()%n+1;
if(l>r){
swap(l,r);
}
l=dfn[l],r=dfn[r];
if(l>r){
swap(l,r);
}
ans+=query(l,r);
}
printf("%llu
",ans);
return 0;
}
