您的位置: 首页  >  IT文章  >  [线段树] Codeforces #1132G Greedy Subsequences 题目大意 题解 代码

[线段树] Codeforces #1132G Greedy Subsequences 题目大意 题解 代码

分类: IT文章 • 2024-02-11 23:37:49

  • 给出n个数和一个数m，求区间[1,m],[2,m+1]......[n−m+1,n] [1,m],[2,m+1]......[n-m+1,n][1,m],[2,m+1]......[n−m+1,n]的最长贪心子序列

  • 最长贪心子序列的求法是，在每个数后面接上右边第一个比它大的数

题解

  • 对于询问区间的改变，可以看作在左边加数，右边删数

  • 设f[i]表示以该位置为开头的子序列的长度，则在加入右边的数num[k]的贡献时，要把左边所有满足右边比它大的第一个数是num[k]的点的dp值都+1

  • 然后就可以发现，这恰好是一段区间[v+1,k]，v是k左边最大的且满足num[v]>=num[k]的数，这个只要用线段树维护区间加和区间查询最大值即可

代码

 1 #include <cstdio>    
 2 #include <iostream>
 3 #include <cstring>
 4 #define N 1000010
 5 using namespace std;
 6 int n,m,tot,num[N],L[N];
 7 struct node { int l,r,mx,sum; }t[N<<1];
 8 void build(int d,int l,int r)
 9 {
10     if (l==r) return;
11     int mid=l+r>>1;
12     t[d].l=++tot,build(tot,l,mid),t[d].r=++tot,build(tot,mid+1,r);
13 }
14 void add(int d,int l,int r,int L,int R,int x)
15 {
16     if (L<=l&&r<=R) { t[d].mx+=x,t[d].sum+=x; return; }
17     int mid=l+r>>1;
18     if (L<=mid) add(t[d].l,l,mid,L,R,x); 
19     if (R>mid) add(t[d].r,mid+1,r,L,R,x);    
20     t[d].mx=max(t[t[d].l].mx,t[t[d].r].mx)+t[d].sum;
21 }
22 int query(int d,int l,int r,int L,int R)
23 {
24     if (L<=l&&r<=R) return t[d].mx;
25     int mid=l+r>>1,res=0;
26     if (L<=mid) res=max(res,query(t[d].l,l,mid,L,R));
27     if (mid<R) res=max(res,query(t[d].r,mid+1,r,L,R));
28     return res+t[d].sum;
29 }
30 int main()
31 {
32     scanf("%d%d",&n,&m),num[0]=N;
33     for (int i=1;i<=n;i++) scanf("%d",&num[i]);
34     for (int i=1;i<=n;i++) { L[i]=i-1; for (;num[i]>num[L[i]];L[i]=L[L[i]]); }
35     build(tot=1,1,n);
36     for (int i=1;i<m;i++) add(1,1,n,L[i]+1,i,1);
37     for (int i=1,j=m;j<=n;i++,j++) add(1,1,n,L[j]+1,j,1),printf("%d ",query(1,1,n,i,j));
38 }

相关推荐