Description

給出長度為 \(n\) 的序列,有 \(Q\) 組詢問,問 \(|a_i-a_j|\),\(l<=i,j<=r\)的最小值是多少?
題面

Solution

無刪莫隊.
把詢問按照左端點分塊,同一塊內(nèi)按右端點遞增排序,類似于莫隊
問題在于回溯:
直接刪除的話無法更新最小值,但是可以一邊插入一邊刪除
這樣我們就可以類似于 \(dancing links\) 那樣用鏈表維護這個東西了
假設(shè)塊為 \([L,R]\) ,我們先預(yù)處理出 \(suf[i]\) 表示把 \([R+1,i]\) 之間的數(shù)插入之后的最小值
假設(shè)詢問為 \([l,r]\),那么就只需要考慮 \([l,R]\) 和 \(suf[r]\) 的合并了

根據(jù) \(dancing links\) 的回溯的思想,鏈表先按照一定順序插入,然后是可以再按照相反順序刪除回來的
所以我們先把 \(r\) 移動到塊的右端點 \(R\),因為塊內(nèi) \(r\) 是單調(diào)的,所以可以單調(diào)刪除
算貢獻大致就是分三部分 : 塊外元素內(nèi)部的貢獻(就是 \(suf\)) , 塊內(nèi)元素的內(nèi)部的貢獻 , 塊內(nèi)和塊外的產(chǎn)生的貢獻
我們可以先把塊外的區(qū)間移動到正確的位置 , 然后再暴力插入一遍塊內(nèi)元素 , 這樣的話就把塊內(nèi)元素的內(nèi)部的貢獻 , 塊內(nèi)和塊外的產(chǎn)生的貢獻都算進去了 , 并且塊內(nèi)的移動復(fù)雜度 \(O(\sqrt{n})\) 的.
最后我們再把塊內(nèi)的元素刪掉就行了 , 每次詢問暴力把塊內(nèi)元素插入一次就行了.

總復(fù)雜度 \(O(n*\sqrt{n})\)

#include<bits/stdc++.h> #define mp make_pair using namespace std; const int N=1e5+10,M=320,inf=1e9+10; int n,a[N],w[N],block,m,ans[N*3],dp[N][M],suf[N]; pair<int,int>lis[N]; struct data{int l,r,id;}; vector<data>S[M]; inline bool comp(data i,data j){return i.r<j.r;} inline void priwork(){for(int i=1;i<=n;i++)dp[i][1]=inf;for(int j=2;j<M;j++)for(int i=1;i+j-1<=n;i++)dp[i][j]=min(min(dp[i][j-1],dp[i+1][j-1]),abs(a[i]-a[i+j-1])); } int L[N],R[N]; inline void Clear(){for(int i=1;i<=n;i++)L[i]=i-1,R[i]=i+1;L[n+1]=n;R[0]=1; } inline int ins(int x){int ret=inf;if(R[x]<=n)ret=min(ret,w[R[x]]-w[x]);if(L[x]>0)ret=min(ret,w[x]-w[L[x]]);L[R[x]]=x;R[L[x]]=x;return ret; } inline void del(int x){R[L[x]]=R[x];L[R[x]]=L[x];} int main(){freopen("pp.in","r",stdin);freopen("pp.out","w",stdout);scanf("%d",&n);block=sqrt(n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),lis[i]=mp(a[i],i);priwork();sort(lis+1,lis+n+1);for(int i=1;i<=n;i++)a[i]=lower_bound(lis+1,lis+n+1,mp(a[i],i))-lis,w[i]=lis[i].first;data q;scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&q.l,&q.r);if(q.r-q.l+1<M)ans[i]=dp[q.l][q.r-q.l+1];else q.id=i,S[q.l/block].push_back(q);}int num=(n+block-1)/block;for(int k=0;k<=num;k++){if(S[k].empty())continue;Clear();int l=k*block,r=l+block-1;for(int i=1;i<r;i++)del(a[i]);for(int i=n;i>r;i--)del(a[i]);suf[r]=inf;for(int i=r+1;i<=n;i++)suf[i]=min(suf[i-1],ins(a[i]));for(int i=r-1;i>=l;i--)ins(a[i]);sort(S[k].begin(),S[k].end(),comp);for(int j=S[k].size()-1,p=n,ret;j>=0;j--){data Q=S[k][j];while(p>Q.r)del(a[p--]);ret=suf[p];for(int i=l;i<r;i++)del(a[i]);for(int i=r-1;i>=Q.l;i--)ret=min(ret,ins(a[i]));for(int i=Q.l-1;i>=l;i--)ins(a[i]);ans[Q.id]=ret;}}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Yuzao/p/8688751.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 765F. Souvenirs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。