精华内容
下载资源
问答
  • 线段树三:求任意区间最值

    千次阅读 2012-08-29 10:02:10
    从做这几个题目我发现了,能调用库函数的尽量调用库函数,不然的话可能会超时。不信可以试,在题1的头文件...题1:Tyvj 1038(忠诚),给定区间求最小值。只需更改Query即可,由于没有修改操作,可以删除Update操作。 #

    从做这几个题目我发现了,能调用库函数的尽量调用库函数,不然的话可能会超时。不信可以试,在题1的头文件下定义宏:

    #define min(a,b) (a)<(b)?(a):(b)
    

    在题2中定义宏:

    #define max(a,b) (a)>(b)?(a):(b)

    题1:Tyvj 1038(忠诚),给定区间求最小值。只需更改Query即可,由于没有修改操作,可以删除Update操作。

    #include<iostream>
    #include<cstring>
    #include<cstdio> 
    #include<cmath> 
    using namespace std;
    const int MAX=100010;
    const int Inf=100000000;
    //#define min(a,b) (a)<(b)?(a):(b) 不要加这个,加后会超时 
    #define Lson L,mid,root<<1
    #define Rson mid+1,R,root<<1|1
    int n,m,Min[MAX<<2];
    int Pushup(int root) 
    {   Min[root]=min(Min[root<<1],Min[root<<1|1]);
    }
    void Build(int L,int R,int root)
    {   if(L==R) 
        {   scanf("%d",&Min[root]);
            return ;
        }
        int mid=(L+R)>>1;
        Build(Lson); 
        Build(Rson); 
        Pushup(root); 
    }
    int Query(int ql,int qr,int L,int R,int root) 
    {   if(ql<=L && R<=qr) return Min[root];
        int mid=(L+R)>>1;
        int res=Inf;
        if(ql<=mid) res=min(res,Query(ql,qr,Lson));
        if(qr>mid) res=min(res,Query(ql,qr,Rson));
        return res;
    }
    int main()
    {   int a,b;
        scanf("%d%d",&n,&m);
        Build(1,n,1);
        for(int i=0;i<m;i++)   
        {   scanf("%d%d",&a,&b);
            printf("%d\n",Query(a,b,1,n,1));
        } 
        return 0;
    }
    

    例题2:HDU 1754(I hate it),给定区间求最大值,记得update中只是更新该结点的值。

    #include<iostream>
    #include<cstring>
    #include<cstdio> 
    #include<cmath> 
    using namespace std;
    const int MAX=200010;
    //#define max(a,b) (a)>(b)?(a):(b) 不要加这个,加后会超时 
    #define Lson L,mid,root<<1
    #define Rson mid+1,R,root<<1|1
    int n,m,Max[MAX<<2];
    int Pushup(int root) 
    {   Max[root]=max(Max[root<<1],Max[root<<1|1]);
    }
    void Build(int L,int R,int root)
    {   if(L==R) 
        {   scanf("%d",&Max[root]);
            return ;
        }
        int mid=(L+R)>>1;
        Build(Lson); 
        Build(Rson); 
        Pushup(root); 
    }
    void Update(int q,int val,int L,int R,int root)
    {   if(L==R)
        {   Max[root]=val;
            return ;
        } 
        int mid=(L+R)>>1;
        if(q<=mid) Update(q,val,Lson);
        else Update(q,val,Rson); 
        Pushup(root);
    }
    int Query(int ql,int qr,int L,int R,int root) 
    {   if(ql<=L && R<=qr) return Max[root];
        int mid=(L+R)>>1;
        int res=0;
        if(ql<=mid) res=max(res,Query(ql,qr,Lson));
        if(qr>mid) res=max(res,Query(ql,qr,Rson));
        return res;
    }
    int main()
    {   int a,b;
        while(~scanf("%d%d",&n,&m))
        {   Build(1,n,1);   
            char op[5];
            getchar();
            while(m--)
            {   scanf("%s%d%d",op,&a,&b);
                if(op[0]=='U') Update(a,b,1,n,1);
                if(op[0]=='Q') printf("%d\n",Query(a,b,1,n,1));
            }
        } 
        return 0;
    }
    


     

    展开全文
  • 首先是一般的RMQ区间最值问题 void RMQ(int num) { for(int j = 0; j ; ++j) for(int i = 1; i ; ++i) { if(j==0)minsum[i][j]=arr[i];// else if(i + (1 ) - 1 <=

    首先是一般的RMQ区间求最值问题

    minsum[i][j]表示起始位置为i长度为j的区间内的最小值。RMQ利用二进制优化处理。

    所以,他的状态转移方程就是  F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])

    查询区间[i][j]的最小值相当于区间[i][k]和区间[t][j]的最小值,其中k>=t


    void RMQ(int num)
    {
        for(int j = 0; j < 19; ++j)
            for(int i = 1; i <= num; ++i)
            {
                if(j==0)minsum[i][j]=arr[i];//初始化
                else if(i + (1 << j) - 1 <= num)
                {
                    minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);//此处为区间求最小值  如果要求最小值,把min相应的改为max就好
                }
            }
    }

    我是在学习后缀数组的时候接触到RMQ算法的,下面的代码是求suffix(i)跟suffix(j)的最大公共前缀的RMQ预处理

    对于RMQ部分基本没有变化,只是初始化的时候arr改称了height数组

    void init()//获取相对应的最长长度Log[i]=j表示2^j<=i并且j是满足条件的最大值
    {
        Log[0] = -1;
        for(int i=1; i<=maxn; i++)
        {
            Log[i]=(i&(i-1))?Log[i-1]:Log[i-1] + 1 ;
        }
    }
    int val(int x,int y)//x,y表示要比较的以x位置开头的后缀与以y开头的后缀
    {
        if(x==y)return 1111111;
        x=rank[x];
        y=rank[y];
        int i=min(x,y);
        int j=max(x,y);
        i++;
        int tem=Log[j-i+1];
        return min(minsum[i][tem],minsum[j-(1<<tem)+1][tem]);
    }
    刚刚学习后缀数组,有写的不妥的地方还望指正。


    展开全文
  • RMQ(range minV/maxV query)算法...问题描述:给出n个数ary[i],快速求出某一区间最值。 算法思想:DP + 位运算 算法分析,状态:dp[i][j] 表示第i为开始,到(i + 2^j - 1)位的最大/小值。 状态转移方程建立:

    RMQ(range minV/maxV query)算法是一个快速求区间最值得离线算法,预处理时间为O(nlgn),查询时间为O(1)。这个问题也可以用线段树解决。


    问题描述:给出n个数ary[i],快速求出某一区间的最值。


    算法思想:DP + 位运算


    算法分析,状态:dp[i][j] 表示第i为开始,到(i + 2^j - 1)位的最大/小值。

    状态转移方程建立:dp[i][j]可以分为两部分,(i, i + 2^(j-1) - 1), (i + 2^(j-1), i + 2^j - 1)

    其实就是把(i, i + 2 ^j)这个区间分为了两部分,没一部分长度为2^(j - 1)。

    状态转移方程:dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]。(这是求最大值的,若求最小值,把max()换为min()即可)

    //需要一个一维待查询的数组,及其长度n,两个状态数组。 
    void RMQ() {  
        for (int i = 1; i <= n; ++i) {  
            dpMax[i][0] = dpMin[i][0] = ary[i];  
        } 
        for (int j = 1; (1 << j) <= n; ++j) {  
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {  
                dpMax[i][j] = max(dpMax[i][j - 1], dpMax[i + (1 << (j - 1))][j - 1]);  
                dpMin[i][j] = min(dpMin[i][j - 1], dpMin[i + (1 << (j - 1))][j - 1]);  
            }  
        }  
    } 
    
    那么查询的时候对于任意一个区间 L -- R ,我们同样可以得到区间差值 len = (R - L + 1)。

    那么我们这一用小于2^k<=len,的 k 把区间分成可以交叉的两部分L 到 L+2^(k)- 1, 到 R -(1<<k)+1 到 R 的两部分,很easy的求解了。


    查询代码:

    int queryRMQ(int L, int R) {  
        int k = 0, len = R - L + 1;  
        while ((1 << (k + 1)) <= len)  
            k++;    
        int maxV = max(dpMax[L][k], dpMax[R - (1 << k) + 1][k]);  
        int minV = min(dpMin[L][k], dpMin[R - (1 << k) + 1][k]);  
        return maxV - minV; //返回最大值还是最小值,还是最大最小值的差,视情况而定  
    }  


    例题:POJ3264

    RMQ 解法(TIME: 1657MS)

    #include <cstdio> 
    #include <algorithm>
    #define N 20
    using namespace std;
    const int maxn = 5e4 + 7;
    int ary[maxn], n, q;
    int dpMax[maxn][N], dpMin[maxn][N];
    void RMQ() {  
        for (int i = 1; i <= n; ++i) {  
            dpMax[i][0] = dpMin[i][0] = ary[i];  
        } 
        for (int j = 1; (1 << j) <= n; ++j) {  
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {  
                dpMax[i][j] = max(dpMax[i][j - 1], dpMax[i + (1 << (j - 1))][j - 1]);  
                dpMin[i][j] = min(dpMin[i][j - 1], dpMin[i + (1 << (j - 1))][j - 1]);  
            }  
        }  
    } 
    int queryRMQ(int L, int R) {  
        int k = 0, len = R - L + 1;  
        while ((1 << (k + 1)) <= len)  
            k++;    
        int maxV = max(dpMax[L][k], dpMax[R - (1 << k) + 1][k]);  
        int minV = min(dpMin[L][k], dpMin[R - (1 << k) + 1][k]);  
        return maxV - minV; //返回最大值还是最小值,还是最大最小值得差,视情况而定  
    }  
    int main()
    {
    	while(~scanf("%d%d", &n, &q)) {
    		for (int i= 1; i <= n; ++i) {
    			scanf("%d", ary + i);
    		}
    		RMQ();
    		while(q-- > 0) {
    			int L, R;
    			scanf("%d%d", &L, &R);
    			printf("%d\n", queryRMQ(L, R));
    		}
    	}
    	
    	return 0;
    } 



    线段树解法(TIME: 1563MS)

    #include<iostream>
    using namespace std;
    
    const int INF=0x7fffffff;
    const int maxn=800010;
    int minV=INF;
    int maxV=-INF;
    
    struct Node{
    	int L , R;
    	int minV,maxV;
    	int Mid(){
    		return (L+R)/2;
    	}
    }tree[maxn];
    
    void BuildTree(int root,int L,int R){
    	tree[root].L=L;
    	tree[root].R=R;
    	tree[root].minV=INF;
    	tree[root].maxV=-INF;
    	if(L!=R){
    		BuildTree(2*root+1,L,(L+R)/2);
    		BuildTree(2*root+2,(L+R)/2+1,R);
    	}
    }
    
    void Insert(int root,int i,int v){
    	if(tree[root].L==tree[root].R){
    		tree[root].minV=tree[root].maxV=v;
    		return;
    	}
    	tree[root].minV=min(tree[root].minV,v);
    	tree[root].maxV=max(tree[root].maxV,v);
    	if(i<=tree[root].Mid()) Insert(2*root+1,i,v);
    	else Insert(2*root+2,i,v);
    }
    
    void Query(int root,int s,int e){
    	if(tree[root].minV>=minV&&tree[root].maxV<=maxV) return;
    	if(tree[root].L==s&&tree[root].R==e){
    		minV=min(minV,tree[root].minV);
    		maxV=max(maxV,tree[root].maxV);
    		return;
    	}
    	if(e<=tree[root].Mid()) Query(2*root+1,s,e);
    	else if(s>tree[root].Mid()) Query(2*root+2,s,e);
    	else{
    		Query(2*root+1,s,tree[root].Mid());
    		Query(2*root+2,tree[root].Mid()+1,e);
    	}
    }
    int main(){
    	int n,q,h;
    	int i,j,k;
    	scanf("%d%d",&n,&q);
    	BuildTree(0,1,n);
    	for(i=1;i<=n;i++){
    		scanf("%d",&h);
    		Insert(0,i,h);
    	}
    	for(i=0;i<q;i++){
    		int s,e;
    		scanf("%d%d",&s,&e);
    		minV=INF;
    		maxV=-INF;
    		Query(0,s,e);
    		printf("%d\n",maxV-minV);
    	}	
    	return 0;
    }






    展开全文
  • 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能...

    思路:

    1. 求最多能拦截多少导弹是求最长不升子序列
    2. 求配备多少套这种系统是求最长下降子序列
    3. 题目要求做法为O(logn)O(\log{n})
    4. 题目的本质是最值的区间查询

    举例:
    序列:389 207 155 300 299 170 158 65
    最值(向上):1 2 3 2 3 4 5 6
    最值(向下):1 1 1 2 2 2 2 1
    我们只需要贪心的选取之前的最值即可

    代码:

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e5+500;
    
    int tot,a[maxn];//原数组
    int t[maxn],mx;	//树状数组与上边界
    
    int query1(int x){	// max(x,...,mx)
    	int res = 0;
    	for(int i=x;i<=mx;i+=i&-i)
    		res = max(res,t[i]);
    	return res;
    }
    
    void update1(int x,int val){
    	for(int i=x;i;i-=i&-i)
    		t[i] = max(t[i],val);
    }
    
    int query2(int x){
    	int res = 0;
    	for(int i=x;i;i-=i&-i)
    		res = max(res,t[i]);
    	return res;
    }
    
    void update2(int x,int val){
    	for(int i=x;i<=mx;i+=i&-i)
    		t[i] = max(t[i],val);
    }
    
    void solve1(){		//最长不升子序列
    	int res = 0;
    	for(int i=0;i<tot;i++){
    		int now = query1(a[i])+1;
    		res = max(res,now);
    		update1(a[i],now);
    		//不是update1(a[i]+1,now),因为自己的值也能贪心的选取
    	}
    	printf("%d\n",res);
    }
    
    void solve2(){		//最长下降子序列
    	memset(t,0,sizeof(t));
    	int res = 0;
    	for(int i=0;i<tot;i++){
    		int now = query2(a[i])+1;
    		res = max(res,now);
    		update2(a[i]+1,now);
    	}
    	printf("%d\n",res);
    }
    
    
    int main(){
    	while(scanf("%d",&a[tot])!=EOF)
    		mx = max(mx,a[tot++]);
    	solve1();	//求最长不升子序列
    	solve2();	//求最长下降子序列
    	return 0;
    }
    
    展开全文
  • 区间最值的问题

    2015-07-28 15:32:14
    区间最值问题 对于数组A[i] ,现要求下标l 到 r 的最值。
  • RAM区间最值

    2019-10-05 04:34:13
    =n),返回数列A中下标在i,j里的最小(大)值,也就是说,RMQ问题是指求区间最值的问题。 简介  主要方法及复杂度如下:  1、朴素(即搜索),O(n)-O(qn) online。  2、线段树,O(n)-O(qlogn) o...
  • RMQ区间最值问题

    2021-02-02 01:36:13
    RMQ区间最值问题问题描述基本思想1区间询问2区间长度询问总结 问题描述 RMQ ( Range Minimum / Maximum Query ) 问题是指:对于长度为 n 的数列 A,回答若干询问 RMQ (A , i , j ) ( i , j ≤ n),返回数列A中下标在...
  • 规则是:从环选取任意个数(但不能为0也不能取全部)的连续数字,使选取数字之和最大。但现在有m(4)个操作,用a, b两个数字来描述, 意思是:将环编号为a的数字换成b。现要求每次操作后都按照规则输出最大之和 ...
  • 道理和线段树差不多,因为树状数组里每个点存储的数据范围是[i-lowbit(i)+1,i],而任意一个区间都是可以被许多段这样的小区间所覆盖的,那么我们就可以用这些小区间的最值来更新所求区间最值了。 1 struct ...
  • 一:函数单调区间的求法:(1)图像法对于能作出图像的函数,我们可以通过观察图像...(2)定义法有些函数如果不能作出函数图像来观察出单调区间,可以用定义法来求其单调区间,即首先可以设X1、X2为该区间任意...
  • 区间最值与线段树

    千次阅读 2013-09-26 20:50:26
    区间最值问题: 有无序序列,求任意子区间段的最大值。 最常用的数据结构就是线段树。线段树是一种二叉搜索树,用分治的思想来解决,其中中间结果有点类似于动态规划的中间结果。我们用线段树可以快速地解决区间最值...
  • 离散化 区间最值

    2019-07-25 10:11:41
    题目链接 题目描述 小石有 n 个妹子,每个妹子都有一个细心程度 ai 和一个热心程度 bi,小石想给她们一个重要程度 ti(重要程度为 1 表示最重要,重要程度越小表示越重要)。...对于这些妹子的任意一...
  • 连续子序列 a[L]、a[L+1]、… 、a[R], 对于 1 ~ C的任意一个数,如果出现了,其 出现次数必须 ≥ K(即要求 出现次数 == 0 或 ≥ K) 问满足上述条件的最长连续子序列长度为多少?(N,C,K ≤ 105) 这位博主讲...
  • ST算法(区间最值

    2019-07-25 17:19:01
    ST算法是解决RMQ(区间最值)问题,它能在O(nlogn)的时间预处理,然后酶促查询的复杂度是O(1)。 其原理是倍增,f[i][j]表示从i位起的2^j个数中的最大数,即[i,i+2^j-1]中的最大值。 首先,我们要维护一个二维...
  • 小Ho把这个数目定义为区间[L,R]的价值,用v[L,R]表示。 例如1 1 1 2 2这五个数所组成的区间的价值为4。 现在小Ho想知道在所有的的v[L,R](1 <= L <= R <= n)中,第k小的值是多少。 Input 第一行一个数T...
  • RMQ问题的三种解法 ...=n),返回数列A中下标在[i,j]里的最小(大)值,也就是说,RMQ问题是指求区间最值的问题 主要方法及复杂度(处理复杂度和查询复杂度)如下: 1.朴素(即搜索) O(n)-O(n) 2.线段树(se...
  • RMQ求区间最值

    2012-03-27 10:49:10
    RMQ (Range Minimum/Maximum Query)问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j),返回数列A中下标在[i,j]里的最小(大)值,也就是说,RMQ问题是指求区间最值的问题  主要方法及复杂度(处理...
  • RMQ 区间最值查询算法

    千次阅读 2012-09-07 01:31:22
    朴素(即搜索),复杂度为O(n)线段树能在对数时间内在数组区间上进行更新与查询。预处理 O(n), 查询 O(logn) 定义线段树在区间[i, j] 如下:  第一个节点维护着区间 [i, j] 的信息。  if i 可知
  • ST表就是一个用来解决rmq(区间最值)问题的算法。  ST表不支持在线修改。  预处理时间复杂度O(nlogn),查询时间O(1)。  ST表算法详解(求最小值):  用mn[i][j]表示从j到j+2^i-1的最小值(长度显然为2^i)...
  • 找出数组A[],任意区间[i,j]的最小值 /* RMQ问题 区间最值查询 */ #include using namespace std; #define MAX 100 //方法1 //M[i][j]表示区间i,j最值的索引 //构造M复杂度O(n^2) void RMQ1(int M[][MAX],int ...
  • 题目:Codeforces 487B. Strip(#278Div.1 B题...方法:线段树求区间最值,在线段树进行动态规划,线段树懒操作 复杂度:O(nlogn),n为数列元素个数 此题所需方法巧妙,很有助于算法提高,有助于提高线段树基本写法
  • 1.RMQ (Range Minimum/Maximum Query)问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j说,RMQ问题是指求区间最值的问题。 2. 主要方法及复杂度如下: 1、朴素(即搜索),O(n)-O(qn) online。 ...
  • ST(实质是动态规划) 是一个用来解决rmq(区间最值)问题的算法 ST不支持在线修改, 离线查询 预处理时间复杂度O(nlogn), 查询时间为O(1)。 构建ST表 用mn[i][j]记录 [i, i+2j-1]的最值(长度为2j) 因此对于任意mn[i]...
  • 给出n个(key, val)正整数对,现需保证这棵树上任意一条边的两个端点的key值的最大公约数不为1,询问这棵树所有节点的sum之和最大可能是多少。如果这棵树不存在任意一个合法形态,输出-1。 输入 输入...
  • 同时,对于任意的 [i,j]∈[L,R][i,j]\in [L,R][i,j]∈[L,R],若 Ai​​,在区间右移时,最值永远也不会落在 AiA_iAi​ ,因此 AiA_iAi​ 比 AjA_jAj​ 先失效。这个性质与单调队列性质相符。 2.2.4 代码 例题:...
  • 线段树模板(区间最值) #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef ...
  • 给定一个长度为N的数组A,ST算法能在O(N*log(N))时间预处理后,以O(1)的时间复杂度在线回答“数列A中下标在l~r之间的数的最大值是都少”这样的区间问题。 一个序列的子区间个数显然有O(N^2) 个,根据倍增思想,我们...
  • 就是在一个给定的区间(不能修改)内,求任意 left 到 right 的这子区间内的最大值,对于这种问题,一般会用线段树或者ST表解决,但如果这个查询的次数极大,线段树就会显得乏力,所以就了解一下ST表的求解。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,750
精华内容 1,100
关键字:

任意区间上的最值