专栏文章

题解：P7804 [JOI Open 2021] 决算报告 / Financial Report

HHisy
P7804题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minqb3qk
此快照首次捕获于
2025/12/02 06:36
3 个月前
此快照最后确认于
2025/12/02 06:36
3 个月前
查看原文

思路

令 dpidp_i 表示结尾为第 ii 个且末尾最大值为 aia_i 的最大长度。因为中间没有贡献的数没有贡献，所以问题转变成了这一个式子。
dpidp_i 能够通过 dpjdp_j 转移且仅当 ai>aja_i>a_j 且 k∈[j,i)k\in[j,i) 连续大于等于 aia_i 的 aka_k 的长度不超过 dd。这一个式子是有单调性的，当 jj 满足转移条件的时候，j+1j+1 同样满足。所有满足转移条件的 jj 必定是连续的段，所以考虑使用线段树维护区间 max⁡\max。
同时，考虑改变枚举顺序，从 aia_i 从小到大枚举，这样子就可以少掉一个判断条件。但是，如果出现 aa 相同的情况，需要下表从大到小，避免同样数值从前面同样的 aia_i 转移。
由于顺序的变化，dpdp 的转移变为需要从前面的数值跳，每跳到一个最左端的值就可以增加答案。对于这一个东西，我们发现一个数值只有一个跳到的左端点，这一个可以看作父亲节点，即考虑维护一个块，每一个块的贡献取决于左端点的贡献。考虑使用并查集维护每一个点的祖先节点，即为可以贡献的下标。

代码

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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...