Atcoder

Atcoder

题目：

题目链接：

题意，给定n和k，求最长子序列使得序列内最小值和最大值的相差不超过k，输出序列的长度。

思路：

注意题中要求的子序列可以不连续，namo，值与值之间互相限制同时又有递推、继承的关系，朴素的思路就是dp，dp[i]表示将第i个数选入序列中后，能构成的最长序列，不难发现，dp[i]只受到相差在k以内的元素的约束，取最大即可，所以可以得到转移关系：

dp[i]=max(dp[j])+1//abs(a[i]-a[j])<=k

我们可以用二重循环去找所有满足条件的j，但这种做法的时间复杂度是，但是此处可以用线段树的数据结构优化：要做的是对于所有的j满足，找最大的dp[j]。

Namo，他就是一个偏序问题，两个属性，一个a一个dp值，在限制a的大小的情况下求最大的dp值，那可以用线段树来求解，也就是找区间最大值，将数值对应到下标，dp值对应到权值，构造权值线段树即可解决此题。

小细节：

1.注意a[i]-k和a[i]+k可能会超过数据范围，导致线段树报错，询问的左右端点要进行预处理。

2.这里的upd函数要做的是更新节点为最大值，即：

    if (l == r){t[p] =max(t[p],x);return;}

AC code:

#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<cstring>
#include<set>
#include<queue>
#define eol "\n"
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N   = 2E6 + 7;
using namespace std;
ll ksm(ll a,ll b) {ll res=1;a%=mod; while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res%mod;}
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
ll inv(ll x) {return ksm(x, mod-2);}
int t[N << 2];
void up(int p) { t[p] = max(t[p << 1], t[p << 1 | 1]); }
void update(int p, int l, int r,int f, int x){if (l == r){t[p] =max(t[p],x);return;}int mid = l + r >> 1;if (f<=mid)update(p << 1, l, mid, f, x);else if(f>mid) update(p << 1|1, mid+1, r, f, x);up(p);
}
//区间查询（查询区间a，b的最大值）
int xquery(int p,int l,int r,int a,int b) {int ans = -1;if (a <= l && r <= b) {return t[p];}int mid = (l + r) / 2;if (a <= mid)ans = max(ans, xquery(p << 1, l, mid, a, b));if (b > mid)ans = max(ans, xquery(p << 1 | 1, mid + 1, r, a, b));return ans;
}
ll dp[N];
void solve(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){int temp;cin>>temp;int le=max(temp-k,0),r=min(300001,temp+k);if(le<=r)dp[i]= xquery(1,0,300001,le,r)+1;update(1,0,300001,temp,dp[i]);}ll ans=0;for(int i=1;i<=n;i++)ans=max(ans,dp[i]);cout<<ans<<eol;
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int t=1;//cin>>t;while(t--)solve();
}