题目链接:http://codeforces.com/contest/1132
题目大意
定义一个贪心子序列为:一个子序列下标集合
并且满足题目中给定的条件,给定n和k,
输出n-k个数字,有n-k个滑动区间,每个对应
该区间中最大贪心子序列的长度.
题目分析
可以说是蛮自闭的题目了,,,看别人的提示
外加自己研究好久才终于弄明白了.
首先是建图的思想,不难发现对于这个关系来说是无环的,
如何使得每个数和自己最近的大值相连呢,可以利用单调栈维护递减
序列在退栈的时候添加边关系.
然后我们建立虚点把森林建成一棵树,在这个树上跑DFS构造DFS序.
我们考虑滑动窗口,窗口滑动本质就是:把一个位置的贡献消去,
增加一个位置的贡献,那么对于这题,
每个位置的答案其实就是该位置在树上的深度,
增加一个点的贡献就是:把这个节点对应的子树中的所有点权值加一,
删除贡献一样,想到用DFS序辅助区间修改优化成log.
那么答案其实就是当前线段树中维护出来的最大值.
详见代码.
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=1e6+5;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意:
定义一个贪心子序列为:一个子序列下标集合
并且满足题目中给定的条件,给定n和k,
输出n-k个数字,有n-k个滑动区间,每个对应
该区间中最大贪心子序列的长度.题目分析:
可以说是蛮自闭的题目了,,,看别人的提示
外加自己研究好久才终于弄明白了.首先是建图的思想,不难发现对于这个关系来说是无环的,如何使得每个数和自己最近的大值相连呢,可以利用单调栈维护递减序列在退栈的时候添加边关系.然后我们建立虚点把森林建成一棵树,在这个树上跑DFS构造DFS序.我们考虑滑动窗口,窗口滑动本质就是:把一个位置的贡献消去,增加一个位置的贡献,那么对于这题,每个位置的答案其实就是该位置在树上的深度,增加一个点的贡献就是:把这个节点对应的子树中的所有点权值加一,删除贡献一样,想到用DFS序辅助区间修改优化成log.那么答案其实就是当前线段树中维护出来的最大值.详见代码.
*/
int n,k,a[maxn];
int sk[maxn],l,r,rt=1e6+1;///虚点
vector<int> g[maxn];
int pl[maxn],pr[maxn],tot=0;
void dfs(int u,int pre){pl[u]=++tot;for(int i=0;i<g[u].size();i++){if(g[u][i]==pre) continue;dfs(g[u][i],u);}pr[u]=tot;
}
///线段树
int tree[maxn<<3],maxv[maxn<<3],lazy[maxn<<3];
void build(lrt){lazy[rt]=0;if(l==r) return ;int mid=l+r>>1;build(lson),build(rson);
}
void pushdown(int rt,int l,int r){int mid=l+r>>1;if(lazy[rt]){lazy[rt<<1]+=lazy[rt];lazy[rt<<1|1]+=lazy[rt];maxv[rt<<1]+=lazy[rt];maxv[rt<<1|1]+=lazy[rt];lazy[rt]=0;}
}
void update(lrt,int L,int R,int v){if(L<=l&&r<=R){maxv[rt]+=v;lazy[rt]+=v;return ;}pushdown(rt,l,r);int mid=l+r>>1;if(L<=mid) update(lson,L,R,v);if(mid<R) update(rson,L,R,v);maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
}
int query(lrt,int L,int R){if(L<=l&&r<=R) return maxv[rt];pushdown(rt,l,r);int mid=l+r>>1,ans=0;if(L<=mid) ans=max(ans,query(lson,L,R));if(mid<R) ans=max(ans,query(rson,L,R));return ans;
}
int main(){cin>>n>>k;l=1,r=l-1;rep(i,1,n+1){cin>>a[i];while(r>=l&&a[sk[r]]<a[i]){g[i].push_back(sk[r]);g[sk[r]].push_back(i);r--;}sk[++r]=i;}rep(i,l,r+1){g[sk[i]].push_back(rt);g[rt].push_back(sk[i]);}dfs(rt,0);///建立dfs序build(1,tot,1);rep(i,1,k+1) update(1,tot,1,pl[i],pr[i],1);rep(i,1,n+2-k){cout<<query(1,tot,1,1,tot)<<" ";update(1,tot,1,pl[i],pr[i],-1);if(i+k<=n)update(1,tot,1,pl[i+k],pr[i+k],1);}return 0;
}