[codeforces 407E]k-d-sequence

2019-11-06 06:01:48

字体：大中小

来源：转载

供稿：网友

题目大意

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

分析一波

当d=0时随便搞搞。

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

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

时间复杂度O(nlogn) $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;}

上一篇：BZOJ 3028 食物

下一篇：竖式问题