jzoj 4999. 【NOI2017模擬3.3】螺旋序列不刪除版莫隊算法

2019-11-06 06:34:18

字體：大中小

來源：轉載

供稿：網友

題意

有一個長度為n的序列a，一個長度為m序列b被稱為螺旋序列當且僅當b1=bm且對于1<=i<=m有bi<=b1。 S需要回答q個詢問，每個詢問用l,r兩個參數描述，表示詢問區間[l,r]的最長連續子螺旋序列的長度。 n,m<=5*10^5;|ai|<=10^9

分析

一開始看到這個數據范圍估計沒人敢去打莫隊，不過事實告訴我們人還是要有點信仰才行。

先用rmq或主席樹之類的方法預處理出next和last數組，next[i]表示一個最小的j滿足a[j]==a[i]且max(a[i..j])==a[i]，last同理。然后就可以上莫隊了。然后會發現這題用莫隊不資瓷刪除，于是我們就只能用不刪除的莫隊。那不刪除的莫隊要怎么做呢？對每個詢問按照左端點所在的塊為第一關鍵字右端點為第二關鍵字排序，然后對于左右端點在同一塊內的詢問暴力處理。對于處理左端點在同一塊內的詢問，顯然右端點只需要往右移也就是添加，每次詢問的時候都先把左端點弄到該塊的最右邊，然后不斷左移，同時左移的時候不該邊全局變量，詢問玩后暴力恢復即可。對于這題而言我們需要維護若干條鏈，那么我們用一個數組fa[i]記錄第i個位置所在鏈的根節點，f[i]記錄答案。若右端點右移則更新其所在鏈；若左端點左移則其f值為其后繼的f值加上兩段間的長度，最后暴力恢復f即可。時間復雜度O(nn√) $O(n/sqrt n)$

代碼

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>#define N 500005using namespace std;int n,m,rmq[N][30],bel[N],a[N],f[N],fa[N],next[N],last[N],ls[N],block,vis[N],b[N];struct query{int l,r,ans,id;}q[N];int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}bool cmp(query a,query b){ return bel[a.l]<bel[b.l]||bel[a.l]==bel[b.l]&&a.r<b.r;}bool cmpid(query a,query b){ return a.id<b.id;}void get_rmq(){ int lg=log(n)/log(2); for (int i=1;i<=n;i++) rmq[i][0]=a[i]; for (int j=1;j<=lg;j++) for (int i=1;i<=n-(1<<j)+1;i++) rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);}int get_max(int l,int r){ int lg=log(r-l+1)/log(2); return max(rmq[l][lg],rmq[r-(1<<lg)+1][lg]);}int get_ans(int x){ int l=q[x].l,r=q[x].r,mx=1; for (int i=l;i<=r;i++) vis[i]=0; for (int i=l;i<=r;i++) if (!vis[i]) { vis[i]=1; if (next[i]&&next[i]<=r) { int j=next[i]; while (next[j]&&next[j]<=r) vis[j]=1,j=next[j]; mx=max(mx,j-i+1); } } q[x].ans=mx;}void solve(){ int ans=1,l,r=block*bel[q[1].l]+1; for (int j=1;j<=n;j++) fa[j]=j,f[j]=1; for (int i=1;i<=m;i++) { if (bel[q[i-1].l]!=bel[q[i].l]) { for (int j=1;j<=n;j++) fa[j]=j,f[j]=1; ans=1;r=block*bel[q[i].l]; } if (bel[q[i].l]==bel[q[i].r]) { get_ans(i); continue; } l=block*bel[q[i].l]+1; while (r<q[i].r) { r++; if (last[r]>=l) fa[r]=fa[last[r]],f[fa[r]]+=r-last[r],ans=max(ans,f[fa[r]]); } int ans2=ans; while (l>q[i].l) { l--; if (next[l]&&next[l]<=r) f[l]=f[next[l]]+next[l]-l,ans2=max(ans2,f[l]); } q[i].ans=ans2; int t=block*bel[q[i].l]; while (l<=t) f[l]=1,l++; }}int main(){ freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout); n=read();m=read();block=sqrt(n); for (int i=1;i<=n;i++) b[i]=a[i]=read(); sort(b+1,b+n+1); int b1=unique(b+1,b+n+1)-b-1; for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+b1+1,a[i])-b; get_rmq(); for (int i=1;i<=n;i++) { int x=a[i]; if (get_max(ls[x],i)==x) last[i]=ls[x],next[ls[x]]=i; bel[i]=(i+block-1)/block;ls[x]=i; } for (int i=1;i<=m;i++) { q[i].l=read();q[i].r=read();q[i].id=i; } sort(q+1,q+m+1,cmp); solve(); sort(q+1,q+m+1,cmpid); for (int i=1;i<=m;i++)