Problem address: http://codeforces.com/contest/474/problem/E
This is the first time I encountered this kind of problem using line segment trees to maintain DP. I also encountered it in ASC. At that time, I naturally thought of maintaining DP with line segment trees, but there was a simple method for that question, so I didn't write it. This time I finally wrote it. .
The DP idea of this question is the same as the idea of finding the longest ascending subsequence. However, the search for the previous maximum value here will time out, so you can use a line segment tree to maintain this maximum value, and then because you need to output the path, you need to use a line segment tree to maintain the position information of each number in the sequence.
After a lot of handicaps, I finally debugged it. . .
The code is as follows:
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64#define lson l, mid, rt<<1#define rson mid+1, r, rt<<1|1const int INF=0x3f3f3f3f;const int MAXN=100000;int maxv[MAXN<<2], cnt, pre[MAXN+10], f[MAXN+10], q_maxp, maxp[MAXN<<2], q_maxv;LL a[MAXN+10], c[MAXN+10], d[MAXN+10];void PushUp(int rt){ maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]); if(maxv[rt<<1]>=maxv[rt<<1|1]) maxp[rt]=maxp[rt<<1]; else maxp[rt]=maxp[rt<<1|1];}void update(int p, int x, int i, int l, int r, int rt){ if(l==r) { maxv[rt]=x; maxp[rt]=i; return ; } int mid=l+r>>1; if(p<=mid) update(p,x,i,lson); else update(p,x,i,rson); PushUp(rt);}void query(int ll, int rr, int l, int r, int rt){ if(ll<=l&&rr>=r) { if(q_maxv<maxv[rt]) { q_maxv=maxv[rt]; q_maxp=maxp[rt]; } return ; } int mid=l+r>>1, ans=0; if(ll<=mid) query(ll,rr,lson); if(rr>mid) query(ll,rr,rson);}int bin_seach(LL x){ int low=0, high=cnt-1, mid; while(low<=high) { mid=low+high>>1; if(d[mid]==x) return mid; else if(d[mid]>x) high=mid-1; else low=mid+1; }}int l_seach(LL x){ int low=0, high=cnt-1, mid, ans=-1; while(low<=high) { mid=low+high>>1; if(d[mid]<=x) { ans=mid; low=mid+1; } else high=mid-1; } return ans;}int r_seach(LL x){ int low=0, high=cnt-1, mid, ans=-1; while(low<=high) { mid=low+high>>1; if(d[mid]>=x) { ans=mid; high=mid-1; } else low=mid+1; } return ans;}void print(int x){ if(x==-1) return ; print(pre[x]); printf("%d ",x+1);}int main(){ int n, dd, i, x, ans, y, z, max1=-1, pos, tot; scanf("%d%d",&n,&dd); for(i=0; i<n; i++) { scanf("%I64d",&a[i]); c[i]=a[i]; } sort(c,c+n); d[0]=c[0]; cnt=1; for(i=1; i<n; i++) { if(c[i]!=c[i-1]) { d[cnt++]=c[i]; } } /*for(i=0;i<cnt;i++) { printf("%d ",c[i]); } puts("");*/ memset(maxv,0,sizeof(maxv)); memset(pre,-1,sizeof(pre)); for(i=0; i<n; i++) { x=bin_seach(a[i]); y=l_seach(a[i]-dd); z=r_seach(a[i]+dd); //printf("%d %d %d\n",x,y,z); q_maxp=-1; q_maxv=-1; if(y!=-1) query(0,y,0,cnt-1,1); if(z!=-1) query(z,cnt-1,0,cnt-1,1); update(x,q_maxv+1,i,0,cnt-1,1); pre[i]=q_maxp; if(q_maxv==0) pre[i]=-1; if(max1<q_maxv+1) { max1=q_maxv+1; pos=i; } } printf("%d\n",max1); print(pos); return 0;}
How to solve the invalid mysql identifier error
How to delete blank pages in word without affecting other formats
js split usage
stripslashes function usage
How to copy an Excel table to make it the same size as the original
Introduction to the use of vscode
Linux adds update source method
Basic usage of insert statement
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
