HDU6703 array（权值线段树）

喜欢ヅ旅行 2021-09-07 06:08 340阅读 0赞

考虑建权值线段树，那么线段树存的值就是它的坐标，考虑到答案一定存在且最大值为 n + 1 n+1 n\+1,可以多加一个点 n + 1 n+1 n\+1  
对于操作1  ( 1 , x ) (1,x) (1,x)，直接单点修改位置 s \[ x \] s\[x\] s\[x\] 为 n + 1 n+1 n\+1(s\[x\]为初始位置x的值)  
对于操作2  ( 2 , r , x ) (2,r,x) (2,r,x)，要查询区间 \[ x , n + 1 \] \[x,n+1\] \[x,n\+1\]内第一个大于 r r r的位置，考虑建一棵维护最大值的线段树，比赛时候第一次写这种问题，当时的思路是，查询时先访问左子树，假如左子树不行才访问右子树，但是这个时候的复杂度是 l o g ( n ) ∗ l o g ( n ) log(n)\*log(n) log(n)∗log(n)，然后开始yy各种剪枝，最后有用的剪枝是当查询的区间包含现在的区间时，可以直接判断符不符合情况，这样可以把多的 l o g ( n ) log(n) log(n)变成常数

int query(int p,int l,int r,int x,int y,int tmp)//query(1,1,n+1,x,n+1,r)
    	{ 
    		if(l == r)//查询到叶子节点
    		{ 
    			if(tr[p] > tmp)
    			{ 
    				return l;
    			}
    			else
    			{ 
    				return -1;
    			}
    		}
    		if(x <= l && r <= y)//区间包含于查询区间
    		{ 
    			if(tr[p] <= tmp)
    			{ 
    				return -1;
    			}
    		}
    		int mid = (l+r)/2;
    		if(y <= mid)
    		{ 
    			return query(p*2,l,mid,x,y,tmp);
    		}
    		if(x >= mid + 1)
    		{ 
    			return query(p*2+1,mid+1,r,x,y,tmp);
    		}
    
    		int judge = query(p*2,l,mid,x,y,tmp);//先判断左子树
    
    		if(judge != -1)
    		{ 
    			return judge;
    		}
    
    		return query(p*2+1,mid+1,r,x,y,tmp);
    
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，340人围观）

还没有评论，来说两句吧...

相关阅读

相关树套树(权值线段树套区间线段树)

有N个位置，M个操作。操作有两种，每次操作如果是： `1 a b c`：表示在第a个位置到第b个位置，每个位置加上一个数c `2 a b c`：表示询问从第a个位

墨蓝/ 2023年08月17日 17:27/ 0 赞/ 56 阅读

相关 hdu 5023 线段树

A Corrupt Mayor's Performance Art Time Limit: 2000/1000 MS (Java/Others) Memory Li

刺骨的言语ヽ痛彻心扉/ 2022年08月08日 14:52/ 0 赞/ 150 阅读

相关 BZOJ4627 权值线段树

4627: \[BeiJing2016\]回转寿司 Time Limit: 10 Sec Memory Limit: 256 MB Submit: 1204 So

待我称王封你为后i/ 2021年12月16日 20:07/ 0 赞/ 255 阅读

相关洛谷P1168 中位数(权值线段树)

题目描述给出一个长度为N的非负整数序列Ai，对于所有1 ≤ k ≤ (N + 1) / 2，输出A1, A3, …, A2k - 1的中位数。即前1,3,5，…个数的

た入场券/ 2021年12月16日 16:07/ 1 赞/ 309 阅读

相关 B. Interesting Array（线段树）

[![知识共享许可协议][80x15.png]][80x15.png 1] 本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可

系统管理员/ 2021年11月02日 08:46/ 0 赞/ 222 阅读

相关 HDU6183(线段树)

Do you like painting? Little D doesn’t like painting, especially messy color paintings.

╰+哭是因爲堅強的太久メ/ 2021年11月01日 10:54/ 0 赞/ 330 阅读

相关 HDU-5249 KPI(STL or 权值线段树)

安利博客：[https://blog.csdn.net/qq\_35776579/article/details/55004134][https_blog.csdn.net_q

青旅半醒/ 2021年11月01日 06:38/ 0 赞/ 277 阅读

相关 [权值线段树]

Find the answer Description Given a sequence of n integers called W and an integer

Love The Way You Lie/ 2021年11月01日 04:38/ 0 赞/ 383 阅读

相关 HDU - 5775-Bubble Sort（权值线段树）

P is a permutation of the integers from 1 to N(index starting from 1). Here is the co

分手后的思念是犯贱/ 2021年10月29日 15:22/ 0 赞/ 294 阅读

相关 HDU6703 array（权值线段树）

考虑建权值线段树，那么线段树存的值就是它的坐标，考虑到答案一定存在且最大值为 n + 1 n+1 n\+1,可以多加一个点 n + 1 n+1 n\+1 对于操作1 (

喜欢ヅ旅行/ 2021年09月07日 06:08/ 0 赞/ 341 阅读