时间戳

首页 > 技术文章 > 【BZOJ 4527】 4527: K-D-Sequence （线段树）

【BZOJ 4527】 4527: K-D-Sequence （线段树）

Konjakmoyu 2017-03-28 11:02 原文

4527: K-D-Sequence

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 145  Solved: 59

Description

我们称一个数列为一个好的k-d数列，当且仅当我们在其中加上最多k个
数之后，数列排序后为一个公差为d的等差数列。
你手上有一个由n个整数组成的数列a。你的任务是找到它的最长连续子
串，使得满足子串为好的k-d数列。

Input

第一行包含三个用空格隔开的整数n,k,d（1<=n<=2*10^5;0<=k<=
2*10^5;0<=d<=10^9）。第二行包含n个空格隔开的整数：a1,a2,...,an（-10^9<=ai<=10^9）表示数列a。

Output

输出两个用空格隔开的整数L,r（1<=L<=r<=n），表示数列a_L,a_L+1,...,
ar是好k-d数列的子串中最长的。
如果有多个最优答案，输出那个L值最小的。

Sample Input

6 1 2
4 3 2 8 6 2

Sample Output

3 5
//第一个测试样例的答案为包括数字 2，8，6 的子串——在加入数字 4 并且
排序之后，它变成了数列 2，4，6，8——公差为 2 的等差数列。

HINT

Source

 

 

【分析】

　　我应该还是too young吧。。看到题目被吓到了。

　　首先，d=0，直接特判啦，for一遍。

　　除此之外，各个数都要不相等，然后他们mod d必须相等，所以我们把他们分成mod d相等的一段段。

　　然后a全部除以d，那么就变成d=1的情况的。因为有一个限制，最多加k个数，即这一段[j,i]的 max-min+j-i<=k

　　即max-min+j<=i+k,枚举右端点i之后，找最左边的j满足这个，线段树维护一个max-min+j的最小值，然后线段树上二分就能询问。

　　对于每个数都不相等，别人用的都是map，我离散之后搞了个链表。。

　　max和min用单调栈维护。

　　我WA了很久是因为mod d那里有些是负数，你最好把所有数弄正再算。。【搞到我大数据调试真是心酸。。

　　你也可以膜男神：http://blog.csdn.net/u010600261/article/details/53761943

 

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<stack>
  7 using namespace std;
  8 #define Maxn 400010
  9 #define INF 0x7fffffff
 10 
 11 int mymax(int x,int y) {return x>y?x:y;}
 12 int mymin(int x,int y) {return x<y?x:y;}
 13 
 14 int a[Maxn];
 15 int n,k,d;
 16 
 17 void solve1()
 18 {
 19     int mx=0,id,st=1;
 20     for(int i=1;i<=n;i++)
 21     {
 22         if(a[i]!=a[i+1]||i==n)
 23         {
 24             if(mx<i-st+1) mx=i-st+1,id=st;
 25             st=i+1;
 26         }
 27     }
 28     printf("%d %d\n",id,id+mx-1);
 29 }
 30 int nt[Maxn],cc[Maxn];
 31 
 32 struct node
 33 {
 34     int l,r,lc,rc,mn,lazy;
 35 }tr[Maxn*2];
 36 
 37 int tot;
 38 int build(int l,int r)
 39 {
 40     int x=++tot;
 41     tr[x].l=l;tr[x].r=r;tr[x].mn=0;tr[x].lazy=0;
 42     if(l!=r)
 43     {
 44         int mid=(l+r)>>1;
 45         tr[x].lc=build(l,mid);
 46         tr[x].rc=build(mid+1,r);
 47     }
 48     else tr[x].lc=tr[x].rc=0,tr[x].mn=l;
 49     return x;
 50 }
 51 
 52 void upd(int x)
 53 {
 54     tr[x].mn+=tr[x].lazy;
 55     if(tr[x].lazy==0||(tr[x].l==tr[x].r)) {tr[x].lazy=0;return;}
 56     int lc=tr[x].lc,rc=tr[x].rc;
 57     tr[lc].lazy+=tr[x].lazy;
 58     tr[rc].lazy+=tr[x].lazy;
 59     tr[x].lazy=0;
 60 }
 61 
 62 void change(int x,int l,int r,int z)
 63 {
 64     if(tr[x].l==l&&tr[x].r==r)
 65     {
 66         tr[x].lazy+=z;
 67         upd(x);
 68         return;
 69     }upd(x);
 70     int mid=(tr[x].l+tr[x].r)>>1;
 71     if(r<=mid) change(tr[x].lc,l,r,z);
 72     else if(l>mid) change(tr[x].rc,l,r,z);
 73     else
 74     {
 75         change(tr[x].lc,l,mid,z);
 76         change(tr[x].rc,mid+1,r,z);
 77     }
 78     tr[x].mn=mymin(tr[tr[x].lc].mn,tr[tr[x].rc].mn);
 79 }
 80 
 81 int query(int x,int l,int r,int y)
 82 {
 83     upd(x);
 84     if(tr[x].mn>y) return -1;
 85     if(tr[x].l==tr[x].r) return tr[x].l;
 86     int mid=(tr[x].l+tr[x].r)>>1;
 87     if(r<=mid) return query(tr[x].lc,l,r,y);
 88     else if(l>mid) return query(tr[x].rc,l,r,y);
 89     else
 90     {
 91         int nw=query(tr[x].lc,l,mid,y);
 92         if(nw!=-1) return nw;
 93         else return query(tr[x].rc,mid+1,r,y);
 94     }
 95 }
 96 
 97 int mx=-1,id;
 98 struct hp{int x,id;};
 99 stack<hp > q1,q2;
100 void solve(int st,int ed)
101 {
102     int fr=st;
103     // while(!q1.empty()) q1.pop();
104     // while(!q2.empty()) q2.pop();
105     // printf("%d %d\n",st,ed);
106     for(int i=st;i<=ed;i++)
107     {
108         fr=mymax(fr,nt[i]+1);
109         int edd=i-1;
110         while(!q1.empty())
111         {
112             hp x=q1.top();
113             if(x.x<=a[i]) {q1.pop();change(1,x.id,edd,a[i]-x.x);edd=x.id-1;}
114             else break;
115         }change(1,i,i,a[i]);
116         hp nw;nw.x=a[i];nw.id=edd+1;q1.push(nw);
117         edd=i-1;
118         while(!q2.empty())
119         {
120             hp x=q2.top();
121             if(x.x>=a[i]) {q2.pop();change(1,x.id,edd,x.x-a[i]);edd=x.id-1;}
122             else break;
123         }change(1,i,i,-a[i]);
124         nw.x=a[i];nw.id=edd+1;q2.push(nw);
125         int nj=query(1,fr,i,i+k);
126         if(nj!=-1&&mx<i-nj+1) mx=i-nj+1,id=nj;
127     }
128 }
129 
130 void solve2()
131 {
132     build(1,n);
133     int st=1;
134     for(int i=1;i<=n;i++)
135     {
136         if(cc[i]!=cc[i+1]||i==n)
137         {
138             solve(st,i);
139             st=i+1;
140         }
141     }
142     printf("%d %d\n",id,id+mx-1);
143 }
144 
145 struct col{int x,id;}c[Maxn];int ft[Maxn];
146 bool cmp(col x,col y) {return x.x<y.x;}
147 
148 void init()
149 {
150     int mn=INF;
151     for(int i=1;i<=n;i++) mn=mymin(mn,a[i]);
152     mn=-mn;if(mn<0) mn=0;
153     for(int i=1;i<=n;i++) a[i]+=mn;
154     for(int i=1;i<=n;i++) c[i].x=a[i],c[i].id=i;
155     sort(c+1,c+1+n,cmp);
156     int p=1;cc[c[1].id]=1;
157     for(int i=2;i<=n;i++)
158     {
159         if(c[i].x!=c[i-1].x) p++;
160         cc[c[i].id]=p;
161     }
162     for(int i=1;i<=p;i++) ft[i]=0;
163     for(int i=1;i<=n;i++)
164     {
165         nt[i]=ft[cc[i]];
166         ft[cc[i]]=i;
167     }
168     for(int i=1;i<=n;i++) cc[i]=a[i]%d,a[i]/=d;
169     // printf("%d %d %d\n",cc[99989],cc[99996],d);
170     // for(int i=1;i<=n;i++) printf("%d\n",nt[i]);
171 }
172 
173 int main()
174 {
175     scanf("%d%d%d",&n,&k,&d);
176     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
177     if(d==0) solve1();
178     else
179     {
180         init();
181         solve2();
182     }
183     return 0;
184 }
View Code

 

2017-03-28 11:02:49

推荐阅读