专栏首页wymHDU 6621 (2019杭电第四场 1008) K-th Closest Distance (主席树 + 二分, 求第 k 小绝对值)

HDU 6621 (2019杭电第四场 1008) K-th Closest Distance (主席树 + 二分, 求第 k 小绝对值)

题意:给出n m, 表示n个数,m组询问, 每组询问给出 l , r , p ,k 四个数,求[L,R]区间内 |p - a[i]|值第 k 小的数

题解:二分答案ans, 那么我们可以确定一个值域 [p-ans,p+ans] ,如果这个区间个数大于k个,那么答案就是合法的,

一直二分到最小答案即可。 找区间数的个数可以用主席树实现。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 300000;
int sum[maxn*20+5];//sum为森林的不同根结点
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);
}
int l,r,pl,pr,p,k,mid,prem,pmid;
void solve(){
	scanf("%d %d %d %d",&pl,&pr,&p,&k);
	pl^=prem;	pr^=prem;	p^=prem;	k^=prem;
	if(pl>pr)swap(pl,pr);
	l = 0;	r = 1e6+5;	pmid = 0;
	while(l<=r){
		mid = (l+r)>>1;
		int t1 = p-mid;
		int t2 = p+mid;
		t1 = lower_bound(b+1,b+1+sz,t1) - b - 1;
		t2 = upper_bound(b+1,b+1+sz,t2) - b - 1;
		if((query2(sum[pl-1],sum[pr],1,sz,t2)-query2(sum[pl-1],sum[pr],1,sz,t1))>=k){
			pmid = mid;
			r = mid-1;
		}else l = mid+1;
	}
	prem = pmid;
	printf("%d\n",prem); 
}
int main() {
	int t;
	scanf("%d",&t);
	
	while(t--) {
		scanf("%d %d",&n,&m);
		for(int i=1; i<=n; i++)scanf("%d",&a[i]),b[i]=a[i];
		sort(b+1,b+n+1);
		sz = unique(b+1,b+n+1) - (b+1);
		cnt = 0;
		sum[0] = build(1,sz);//建立空树
		for(int i=1; i<=n; i++) a[i] = lower_bound(b+1,b+sz+1,a[i]) - b;
		for(int i=1; i<=n; i++) sum[i] = update(1,sz,sum[i-1],a[i]);
		prem = 0;
		while(m--) {
			solve();
		}
	}
	return 0;
}
/*
1
5 2
31 2 5 45 4
2 5 3 2
1 5 5 1

2
6 2
31 31 2 5 45 4
3 5 77 1
1 6 41 2
5 2
31 2 5 45 4
1 3 100 1
2 5 3 2

*/

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P3834 【模板】可持久化线段树 1(主席树) (多次查询第k大或第k小)

    用户2965768
  • HDU 1878 欧拉回路

    #include <bits/stdc++.h> using namespace std; const int N=1005; int in[N]; i...

    用户2965768
  • Hdu 6534 莫队+树状数组

    用户2965768
  • BZOJ4299: Codechef FRBSUM(主席树)

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

    attack
  • LeetCode 周赛题解 213

    因为 arr 和 pieces 中都不包含重复的数字,所以直接在pieces中暴力寻找 arr[i] 即可,然后连续的元素是否相同即可。

    ACM算法日常
  • 洛谷P4396 [AHOI2013]作业(树套树)

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

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

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

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

    attack
  • POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

    Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

    Angel_Kitty
  • 【 HDU - 4456 】Crowd (二维树状数组、cdq分治)

    给你一个n行n列的格子,一开始每个格子值都是0。有M个操作,p=1为第一种操作,给格子(x,y)增加z。p=2为询问与格子(x,y)的曼哈顿距离不超过z的格子值...

    饶文津

扫码关注云+社区

领取腾讯云代金券