题解：P7804 [JOI Open 2021] 决算报告 / Financial Report
Hisy
·
·
题解
思路
令 dp_i 表示结尾为第 i 个且末尾最大值为 a_i 的最大长度。因为中间没有贡献的数没有贡献，所以问题转变成了这一个式子。
同时，考虑改变枚举顺序，从 $a_i$ 从小到大枚举，这样子就可以少掉一个判断条件。但是，如果出现 $a$ 相同的情况，需要下表从大到小，避免同样数值从前面同样的 $a_i$ 转移。
由于顺序的变化，$dp$ 的转移变为需要从前面的数值跳，每跳到一个最左端的值就可以增加答案。对于这一个东西，我们发现一个数值只有一个跳到的左端点，这一个可以看作父亲节点，即考虑维护一个块，每一个块的贡献取决于左端点的贡献。考虑使用并查集维护每一个点的祖先节点，即为可以贡献的下标。
## 代码
```cpp
#include<bits/stdc++.h>
#define MAXN 300030
using namespace std;
struct node{
int val,id;
}a[MAXN];
int n,d;
inline bool compare(const node &x,const node &y){
if(x.val==y.val){
return x.id>y.id;
}
return x.val<y.val;
}
namespace SegementTree{
int maxt[MAXN<<2];
inline void change(int root,int l,int r,int pos,int val){
if(l==pos&&r==pos){
maxt[root]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
change(root<<1,l,mid,pos,val);
}else{
change(root<<1|1,mid+1,r,pos,val);
}
maxt[root]=max(maxt[root<<1],maxt[root<<1|1]);
}
inline int query(int root,int l,int r,int L,int R){
if(L<=l&&r<=R){
return maxt[root];
}
int mid=(l+r)>>1;
int res=0;
if(L<=mid){
res=max(res,query(root<<1,l,mid,L,R));
}
if(mid<R){
res=max(res,query(root<<1|1,mid+1,r,L,R));
}
return res;
}
}
namespace FindMergeSet{
int fa[MAXN];
inline void init(){
for(int i=1;i<MAXN;++i){
fa[i]=i;
}
}
inline int get(int son){
if(fa[son]^son){
return fa[son]=get(fa[son]);
}
return son;
}
inline void stick(int x,int y){
fa[x]=get(y);
}
}
namespace BalancedTree{
struct balanced{
int lson,rson,key,siz,val;
}tree[MAXN];
int cnt,root;
inline void push_up(int root){
tree[root].siz=tree[tree[root].lson].siz+tree[tree[root].rson].siz+1;
}
inline int newnode(int val){
tree[++cnt].val=val;
tree[cnt].siz=1;
tree[cnt].key=rand();
return cnt;
}
inline void split(int root,int val,int &x,int &y){
if(!root){
x=y=0;
return;
}
if(tree[root].val<=val){
x=root;
split(tree[root].rson,val,tree[root].rson,y);
}else{
y=root;
split(tree[root].lson,val,x,tree[root].lson);
}
push_up(root);
}
inline int merge(int x,int y){
if(!x||!y){
return x+y;
}
if(tree[x].key<tree[y].key){
tree[x].rson=merge(tree[x].rson,y);
push_up(x);
return x;
}
tree[y].lson=merge(x,tree[y].lson);
push_up(y);
return y;
}
inline void insert(int val){
int x,y;
split(root,val,x,y);
root=merge(merge(x,newnode(val)),y);
}
inline void erase(int val){
int x,y,z;
split(root,val,x,z);
split(x,val-1,x,y);
y=merge(tree[y].lson,tree[y].rson);
root=merge(merge(x,y),z);
}
inline int query_val(int root,int rnk){
if(tree[tree[root].lson].siz>=rnk){
return query_val(tree[root].lson,rnk);
}
if(tree[tree[root].lson].siz+1==rnk){
return tree[root].val;
}
return query_val(tree[root].rson,rnk-tree[tree[root].lson].siz-1);
}
inline int prev_of(int val){
int x,y;
split(root,val-1,x,y);
const int res=query_val(x,tree[x].siz);
root=merge(x,y);
return res;
}
inline int next_of(int val){
int x,y;
split(root,val,x,y);
const int res=query_val(y,1);
root=merge(x,y);
return res;
}
}
using namespace SegementTree;
using namespace FindMergeSet;
using namespace BalancedTree;
int main(){
srand(time(0));
init();
scanf("%d %d",&n,&d);
for(int i=1;i<=n;++i){
scanf("%d",&a[i].val);
a[i].id=i;
}
sort(a+1,a+1+n,compare);
insert(0);
insert(n+1);
for(int i=1;i<=n;++i){
int res=1;
const int pre=prev_of(a[i].id);
const int nxt=next_of(a[i].id);
if(pre&&a[i].id<=pre+d){
res=query(1,1,n,get(pre),a[i].id-1)+1;
stick(a[i].id,pre);
}
if(nxt!=n+1&&nxt<=a[i].id+d){
stick(nxt,a[i].id);
}
change(1,1,n,a[i].id,res);
insert(a[i].id);
}
printf("%d",query(1,1,n,1,n));
return 0;
}
```