专栏首页wym南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 F 主席树 或 滑动窗口

南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 F 主席树 或 滑动窗口

查询区间 [ id-k,id+k] 小于 val 的个数 num , 再在该区间查询第 num 大的数。

从小到大做,则每次只要找一次就行。 O(n*log2n)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int sum[maxn*20+5];//sum为森林的不同根结点
int id[maxn],ans[maxn];
struct E {
	int num;
	int l,r;
} t[maxn*20+5]; //t为tree树
int n,sz,m,a[maxn],b[maxn],cnt;
int q;
int build(int l,int r) {
	int now = ++cnt;
	int mid = (l+r)>>1;
	if(l<r) {
		t[now].l = build(l,mid);
		t[now].r = build(mid+1,r);
	}
	return now;
}
int update(int l,int r,int last,int p) {
	int now = ++cnt;
	t[now].num = t[last].num+1;
	t[now].l = t[last].l;
	t[now].r = t[last].r;
	int mid = (l + r)>>1;
	if(l<r) {
		if(p<=mid)t[now].l = update(l,mid,t[last].l,p);
		else t[now].r = update(mid+1,r,t[last].r,p);
	}
	return now;
}
int query(int u,int v,int l,int r,int k){//查询区间第k大 
	if(l==r)return l;
	// v 左孩子包含点个数减去 u 左孩子包含点的个数 
	int tmp = t[t[v].l].num - t[t[u].l].num;
	int mid = (l+r)>>1;
	if(k<=tmp)return query(t[u].l,t[v].l,l,mid,k);
	else return query(t[u].r,t[v].r,mid+1,r,k - tmp);
}
int query2(int u,int v,int l,int r,int k) {//查询区间小于等于k 
	if(k==0)return 0;
	if(l==r)return t[v].num - t[u].num;
	int tmp = t[t[v].l].num - t[t[u].l].num;
	int mid = (l+r)>>1;
	if(k<=mid)return query2(t[u].l,t[v].l,l,mid,k);
	else return tmp+query2(t[u].r,t[v].r,mid+1,r, k);
}
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main() {
	int t;
	t = read();
	while(t--) {
		n = read();	m = read();
		for(int i=1; i<=n; i++)a[i]=read(),id[a[i]]=i,ans[i] = 0;
		cnt = 0;
		sum[0] = build(1,n);//建立空树
		for(int i=1; i<=n; i++) sum[i] = update(1,n,sum[i-1],a[i]);
		for(int i=1;i<=n;i++){
			int tp = id[i],val = i,num;
			int l,r;
			l = max(tp-m,1);
			r = min(tp+m,n);
			while(1){
				num = query2(sum[l-1],sum[r],1,n,val-1);
				if(num==0)break;
				else{
					ans[i]++;
					val = query(sum[l-1],sum[r],1,n,num);
					if(val==0)break;
					else {
						ans[i]+=ans[val];
						break;	
					}
				}
			}
		}
		for(int i=1;i<n;i++){
			printf("%d ",ans[i]+1);
		}
		printf("%d",ans[n]+1);
		printf("\n");
	}
	return 0;
}
/*

*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle( 主席树求区间第k大)

    用户2965768
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768
  • hdu1025

    @坤的
  • 2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle( 主席树求区间第k大)

    用户2965768
  • PAT(乙级)1013

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.net/z...

    zy010101
  • BZOJ4260: Codechef REBXOR (01Tire树)

    attack
  • BZOJ4299: Codechef FRBSUM(主席树)

    那么若$a[i + 1] > s_i + 1$,那么$a[i + 1]$不能被拼成

    attack
  • HDU4352 XHXJ's LIS(LIS 状压)

    刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

    attack
  • 洛谷P4425 [HNOI/AHOI2018]转盘(线段树)

    首先猜一个结论:对于每次询问,枚举一个起点然后不断等到某个点出现时才走到下一个点一定是最优的。

    attack

扫码关注云+社区

领取腾讯云代金券