HDU6703 array（权值线段树）

喜欢ヅ旅行 2021-09-07 06:08 345阅读 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 条评论，345人围观）

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

相关阅读

相关代码源扫描线权值线段树板子

矩形面积并（存档） [矩形面积并 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![a

Bertha 。/ 2024年03月17日 14:51/ 0 赞/ 53 阅读

相关高级数据结构 - 线段树、权值线段树（Java & JS & Python）

引子现在给定一个数组 arr = \[4, 7, 5, 3, 8, 9, 0, 1, 2, 6\]，arr.length = n，无规律地多次进行如下操作：查

偏执的太偏执、/ 2023年10月13日 17:16/ 0 赞/ 3 阅读

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

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

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

相关 2019ccpc网络赛hdu6703 array(线段树)

array [题目传送门][Link 1] 解题思路操作1是把第pos个位置上的数加上\\(10^7\\)，操作2是找到区间\[1,r\]中没有且大于k的最小的

朴灿烈づ我的快乐病毒、/ 2023年08月17日 17:21/ 0 赞/ 142 阅读

相关 hdu 5023 线段树

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

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

相关 BZOJ4627 权值线段树

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

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

相关 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 赞/ 281 阅读

相关 [权值线段树]

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 赞/ 388 阅读

相关 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 赞/ 298 阅读

相关 HDU6703 array（权值线段树）

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

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