[codeforces 407E]k-d-sequence

2019-11-06 06:01:48

字體：大中小

供稿：網(wǎng)友

題目大意

給定一個(gè)序列，以及k和d，找一個(gè)最長的連續(xù)子序列，滿足給這個(gè)連續(xù)子序列加入至多k個(gè)數(shù)，然后從小到大排序，可以得到一個(gè)公差為d的等差數(shù)列。 k,n≤200000 0≤d≤109 $10^9$ 所有數(shù)絕對(duì)值≤109 $10^9$

分析一波

當(dāng)d=0時(shí)隨便搞搞。

當(dāng)d≠0，怎樣的序列可以構(gòu)造出一個(gè)合法的等差數(shù)列呢？所有數(shù)對(duì)d取模得到的值一樣，并且它們除d之后，假設(shè)最大、小值分別是max，min，序列長度為len，那么max?min?len≤k $max-min-len≤k$ 還有一點(diǎn)很關(guān)鍵，序列中沒有重復(fù)的數(shù)。

那么思路出來了！枚舉區(qū)間的左端或右端，然后用兩個(gè)單調(diào)棧維護(hù)最大、最小值。退棧的時(shí)候，相當(dāng)于一個(gè)區(qū)間加。求答案是區(qū)間查詢（注意控制查詢的區(qū)間沒有相同元素和模d不同的元素）。求完當(dāng)前位置的答案后又要區(qū)間減1。線段樹解決。細(xì)節(jié)自行補(bǔ)上吧。

時(shí)間復(fù)雜度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; } }