[codeforces 407E]k-d-sequence

3/8/2017来源:ASP.NET技巧人气:3573

题目大意

给定一个序列,以及k和d,找一个最长的连续子序列,满足给这个连续子序列加入至多k个数,然后从小到大排序,可以得到一个公差为d的等差数列。 k,n≤200000 0≤d≤109所有数绝对值≤109

分析一波

当d=0时随便搞搞。

当d≠0,怎样的序列可以构造出一个合法的等差数列呢? 所有数对d取模得到的值一样,并且它们除d之后,假设最大、小值分别是max,min,序列长度为len,那么max−min−len≤k 还有一点很关键,序列中没有重复的数。

那么思路出来了!枚举区间的左端或右端,然后用两个单调栈维护最大、最小值。退栈的时候,相当于一个区间加。求答案是区间查询(注意控制查询的区间没有相同元素和模d不同的元素)。求完当前位置的答案后又要区间减1。线段树解决。 细节自行补上吧。

时间复杂度O(nlogn)

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> using namespace std; const int N=200005,M=524305,inf=1e9; typedef long long LL; int n,m,D,a[N],t1,d1[N],t2,d2[N],ans,tot,la[N],xx,yy,Tag[M],t[M],b[N]; char c; bool bz; map <int,int> h; int read() { int x=0,sig=1; for (c=getchar();c<'0' || c>'9';c=getchar()) if (c=='-') sig=-1; for (;c>='0' && c<='9';c=getchar()) x=x*10+c-48; return x*sig; } void push_down(int x) { if (Tag[x]!=0) { Tag[x<<1]+=Tag[x]; Tag[x<<1|1]+=Tag[x]; t[x<<1]+=Tag[x]; t[x<<1|1]+=Tag[x]; Tag[x]=0; } } void insert(int l,int r,int g,int x) { if (l==r) { t[x]=0; return; } push_down(x); int mid=l+r>>1; if (g<=mid) insert(l,mid,g,x<<1);else insert(mid+1,r,g,x<<1|1); t[x]=min(t[x<<1],t[x<<1|1]); } void add(int l,int r,int a,int b,int v,int x) { if (l==a && r==b) { t[x]+=v; Tag[x]+=v; return; } push_down(x); int mid=l+r>>1; if (b<=mid) add(l,mid,a,b,v,x<<1);else if (a>mid) add(mid+1,r,a,b,v,x<<1|1);else { add(l,mid,a,mid,v,x<<1); add(mid+1,r,mid+1,b,v,x<<1|1); } t[x]=min(t[x<<1],t[x<<1|1]); } int get(int l,int r,int b,int x) { if (t[x]>m) return 0; if (l==r) return l; push_down(x); int mid=l+r>>1; if (b<=mid || t[x<<1|1]>m) return get(l,mid,b,x<<1); return get(mid+1,r,b,x<<1|1); } int main() { n=read(); m=read(); D=read(); if (D==0) { for (int i=1;i<=n;i++) a[i]=read(); for (int i=1,j;i<=n;i=j) { for (j=i;a[j]==a[i] && j<=n;j++); if (j-i>ans) { ans=j-i; xx=i; yy=j-1; } } PRintf("%d %d\n",xx,yy); return 0; } for (int i=1;i<=n;i++) { a[i]=read()+inf; b[i]=a[i]%D; a[i]/=D; } memset(t,42,sizeof(t)); d1[0]=d2[0]=n+1; ans=xx=yy=1; for (int i=n,R=n+1;i;i--) { if (b[i]!=b[i+1]) R=i+1; int x; if (h.find(a[i])==h.end()) h.insert(make_pair(a[i],x=++tot));else { x=h.find(a[i])->second; R=min(R,la[x]); } insert(1,n,i,1); la[x]=i; for (;t1>0 && a[i]<a[d1[t1]];t1--) add(1,n,d1[t1],d1[t1-1]-1,a[d1[t1]]-a[i],1); d1[++t1]=i; add(1,n,i,i,-a[i],1); for (;t2>0 && a[i]>a[d2[t2]];t2--) add(1,n,d2[t2],d2[t2-1]-1,a[i]-a[d2[t2]],1); d2[++t2]=i; add(1,n,i,i,a[i],1); x=get(1,n,R-1,1); if (x-i+1>=ans) { ans=x-i+1; xx=i; yy=x; } add(1,n,i,R-1,-1,1); } printf("%d %d\n",xx,yy); return 0; }