G. Greedy Subsequences
题意
给你一个长度为n的数组，对其中每个长度为k的连续子序列求这个子序列的最长贪心子序列
选定一个数作为第一个数，那么他右面离他最近而且比他大的数作为第二个数，以此类推直到不能再加数这样产生的序列被称为贪心子序列。
对于一个序列选定每一个数作为起点，得到的最长的贪心子序列就是一个序列的最长贪心子序列。
1≤n,k≤1061 \leq n,k \leq 10^61≤n,k≤106
做法
首先这道题一定是滑动窗口来做的。也就是算出第一段的贡献之后，加上一个数的贡献，减去一个数的贡献。
可是我们怎么维护好一些呢，由于要计算每个数靠右的第一个比他大的数，我们这个过程用一个单调栈就能做完。
之后我们把每个数和右边第一个比他大的数建边，我们就可以得到一个森林，再把所有的根同时指向一个虚根，就得到一颗虚树。
我们设树上每个点的权值代表他到虚根这条路径上有多少个点，那么所有点中最大的权值就是答案，那么我们怎么维护加入一个点呢，我们发现，加入一个点的贡献就是把包括他在内的子树中所有点的权值+1，这个用一个基于dfs序的线段树就可以维护，删除一个点的贡献同理，只要将他的子树内所有点的权值-1即可。
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
#define pb push_back
const int maxn = 1e6+5;
struct T
{
int l,r,mid;int maxx,add;
}tree[maxn<<2];
int in[maxn],ou[maxn];
int a[maxn];
int fa[maxn];
vector<int> G[maxn];
int tim;
void dfs(int rt,int fa)
{
in[rt]=++tim;for(int i=0;i<G[rt].size();i++){
int to=G[rt][i];if(to==fa) continue;dfs(to,rt);}ou[rt]=tim;
}
void push_up(int rt)
{
tree[rt].maxx=max(tree[rt<<1].maxx,tree[rt<<1|1].maxx);
}
void push_down(int rt)
{
if(tree[rt].add!=0){
int tmp=tree[rt].add;tree[rt<<1].maxx+=tmp;tree[rt<<1|1].maxx+=tmp;tree[rt<<1].add+=tmp;tree[rt<<1|1].add+=tmp;tree[rt].add=0;}
}
void build(int rt,int l,int r)
{
tree[rt].l=l;tree[rt].r=r;tree[rt].add=0;if(l==r){
tree[rt].maxx=0;return ;}int mid=tree[rt].mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);push_up(rt);return ;
}
void update(int rt,int l,int r,int val)
{
if(tree[rt].l>r||tree[rt].r<l) return ;if(tree[rt].l>=l&&tree[rt].r<=r){
tree[rt].add+=val;tree[rt].maxx+=val;return ;}push_down(rt);if(tree[rt].mid>=l) update(rt<<1,l,r,val);if(tree[rt].mid<r) update(rt<<1|1,l,r,val);push_up(rt);
}
int ans[maxn];
int main()
{
int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(1,1,n+1);stack<int>st;for(int i=n;i>=1;i--){
while(!st.empty()&&a[st.top()]<=a[i]) st.pop();if(st.empty()) G[0].pb(i);else G[st.top()].pb(i);st.push(i);}dfs(0,-1);for(int i=n;i>=n-k+1;i--) update(1,in[i],ou[i],1);ans[n-k+1]=tree[1].maxx;for(int i=n-k;i>=1;i--){
update(1,in[i+k],ou[i+k],-1);update(1,in[i],ou[i],1);ans[i]=tree[1].maxx;}for(int i=1;i<=n-k+1;i++) printf("%d ",ans[i]);return 0;
}