思路:
宋文杰的题解很详细.
一开始每个点30s,结果在OJ上一共30s...
也就是说原来莫队是能过的,结果我无悬念TLE.
莫队怎么做我就不说了.(貌似官方正解就是莫队...)
莫队很暴力,因为没有利用一个题目中的性质:就是数据随机生成!
询问随不随机意义是不大的.
但是如果询问很特殊,我们就可以用科学的方法去处理:
(1)任意两个区间不互相包含.这种情况我们将区间随便排个序就能发现总移动次数是\(O(n)\)的.
(2)任意两个区间要么互相包含,要么不相交.这样就会形成一棵树.我们利用启发式合并,插入次数就为\(O(nlogn)\).
但是随机数据显然没有这种性质.
那么唯一可能有比较优秀的性质的就是随机数列了.
考虑一种朴素算法:
将所有询问离线按照右端点从小到大排序.
从前向后依次加入右端点,令\(f_i\)表示当前以\(i\)为起点的后缀的答案,那么朴素来看,如果当前加入的是\(n\),那么\(f_1-f_{n-1}\)都需要更新.
但是有很多冗余的更新.
例如我们考虑所有大于\(a_n\)的数,不妨令\(a_i,a_j>a_n,a_i>a_j,i<j\),那么如果我们能够维护一个后缀的答案,我们就只需更新\(f_j\)就可以了.
于是我们发现了某些单调性.
我们利用数据结构维护后缀的答案,那么只需更新一些点就行了.
那么我们的任务就是找到,对于\(n\)之前的数,一个均\(>a_n\)的递减序列,一个均\(<a_n\)的递增序列.然后我们就拿序列中的东西暴力更新答案.
然而由于是随机数据,序列中的元素个数是\(O(logn)\)级别的.
这样总时间复杂度就是\(O(qlogn+nlog^2n)\).
具体去看宋文杰的题解.
(另外此题要求结果\(>0\) 23333)
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
#define Q 100010
int n,q,a[N];
struct Interval{
int l,r,lab;
bool operator<(const Interval&B)const{return r<B.r;}
}S[N];
int re[Q];
inline void mini(int&x,int y){if(x>y)x=y;}
struct SegmentTree{
int A[262144],M;
inline void Init(int _siz){
for(M=1;M<(_siz+2);M<<=1);
memset(A,0x3f,sizeof A);
}
inline void modify(int x,int d){
for(x+=M;x;x>>=1)mini(A[x],d);
}
inline int query(int tl,int tr){
int re=~0U>>1;
for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
if(~tl&1)mini(re,A[tl^1]);
if(tr&1)mini(re,A[tr^1]);
}
return re;
}
}Seg;
int preless[N],premore[N],small[N][30],big[N][30],stk[N],top;
int main(){
//freopen("tt.in","r",stdin);
scanf("%d%d",&n,&q);
register int i,j,k;
for(i=1;i<=n;++i)scanf("%d",&a[i]);
for(i=1;i<=q;++i)
scanf("%d%d",&S[i].l,&S[i].r),S[i].lab=i;
sort(S+1,S+q+1);
Seg.Init(n);
for(i=1;i<=n;++i){
while(top&&a[stk[top]]>=a[i])--top;
preless[i]=stk[top];
stk[++top]=i;
}
top=0;
for(i=1;i<=n;++i){
while(top&&a[stk[top]]<=a[i])--top;
premore[i]=stk[top];
stk[++top]=i;
}
for(i=1;i<=n;++i){
if(premore[i]){
big[i][++big[i][0]]=premore[i];
j=big[i][1];
while(1){
bool find=0;
for(k=1;k<=small[j][0];++k)if(a[small[j][k]]>a[i]){find=1;break;}
if(find)big[i][++big[i][0]]=(j=small[j][k]);else break;
}
}
if(preless[i]){
small[i][++small[i][0]]=preless[i];
j=small[i][1];
while(1){
bool find=0;
for(k=1;k<=big[j][0];++k)if(a[big[j][k]]<a[i]){find=1;break;}
if(find)small[i][++small[i][0]]=(j=big[j][k]);else break;
}
}
}
j=1;
for(i=1;i<=n;++i){
for(k=1;k<=small[i][0];++k)Seg.modify(small[i][k],a[i]-a[small[i][k]]);
for(k=1;k<=big[i][0];++k)Seg.modify(big[i][k],a[big[i][k]]-a[i]);
for(;j<=q&&S[j].r==i;++j)re[S[j].lab]=Seg.query(S[j].l,S[j].r);
}
for(i=1;i<=q;++i)printf("%d\n",re[i]);
return 0;
}