rt,思路是跑莫队,用一个set存前后趋,优先队列存答案,WA一个RE四个
本地与暴力在n<=1000时对拍没问题怀疑数据有锅
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#define int long long
using namespace std;
const int maxn=1e5+5;
struct Query
{
int l,r,id,kl;
inline bool operator < (const Query &a) const{
return kl!=a.kl?kl<a.kl:(kl&1?r<a.r:r>a.r);
}
}qu[maxn];
set<int> st;
priority_queue<int,vector<int>,greater<int> > insq,delq;
int vis[maxn],a[maxn],b[maxn],id[maxn],n,m,tt,istwo,nowans,ans[maxn];
template<typename T>
inline void read(T &x)
{
char c;int f=1;
while(!isdigit(c=getchar())) (c=='-')&&(f=-1);
x=c^48;
while(isdigit(c=getchar())) x=x*10+(c^48);
x*=f;
}
inline void insque(int x)
{
//cout<<'i'<<x<<endl;
if(!delq.empty()&&delq.top()==x) delq.pop();
else insq.push(x);
}
inline void delque(int x)
{
//cout<<'d'<<x<<endl;
if(!insq.empty()&&insq.top()==x) insq.pop();
else delq.push(x);
}
inline int getque()
{
while(!insq.empty()&&!delq.empty()&&insq.top()==delq.top()) insq.pop(),delq.pop();
return insq.top();
}
inline void ins(int x)
{
if(vis[id[x]]) {
if(vis[id[x]]==1) istwo++;
vis[id[x]]++;return;
}
vis[id[x]]++;
if(st.empty()) {st.insert(a[x]);return;}
set<int>::iterator f=st.lower_bound(a[x]);
set<int>::iterator t=f;
if(f!=st.begin()) f--;
if(t==st.end()) t--;
insque(abs(*f-a[x]));
//if(st.size()==1) return;
if(*f!=*t) insque(abs(a[x]-*t)),delque(abs(*f-*t));
st.insert(a[x]);
//
}
inline void del(int x)
{
vis[id[x]]--;
if(vis[id[x]]) {
if(vis[id[x]]==1) istwo--;return;
}
st.erase(a[x]);
if(st.empty()) return;
//
set<int>::iterator f=st.lower_bound(a[x]);
set<int>::iterator t=f;
if(f!=st.begin()) f--;
if(t==st.end()) t--;
delque(abs(*f-a[x]));
//if(st.size()==1) return;
if(*f!=*t) delque(abs(a[x]-*t)),insque(abs(*f-*t));
//
}
signed main()
{
read(n);read(m);
int klen=n/sqrt(m*2/3);
for(int i=1;i<=n;++i) read(a[i]),b[i]=a[i];
sort(b+1,b+n+1);
tt=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i)
id[i]=lower_bound(b+1,b+tt+1,a[i])-b;
for(int i=1;i<=m;++i)
{
read(qu[i].l);read(qu[i].r);
qu[i].id=i;qu[i].kl=(qu[i].l-1)/klen+1;
}
sort(qu+1,qu+m+1);
int l=1,r=0;
for(int i=1;i<=m;++i)
{
while(r<qu[i].r) ins(++r);
while(l>qu[i].l) ins(--l);
while(l<qu[i].l) del(l++);
while(r>qu[i].r) del(r--);
if(istwo) ans[qu[i].id]=0;
else ans[qu[i].id]=getque();
}
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}