序列操作（线段树，模板）

小鱼儿 2022-01-07 13:53 190阅读 0赞

n个数，m次操作  
若a==1，求区间b-c最大值  
若a==2，将a\[ b \]改为c

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #define MAXN 200000 
    using namespace std;
    int a[MAXN+5],st[MAXN*4+5]; 
    void bulid(int o,int l,int r)
    {
        if(l==r)
         st[o]=a[l];
        else
        {
            int m=l+((r-l)>>1);
            bulid((o<<1),l,m);
            bulid((o<<1)|1,m+1,r);
            st[o]=max(st[o<<1],st[(o<<1)|1]);
        }
    }
    void exch(int o,int l,int r,int ind,int ans)
    {
        if(l==r)
        {
          st[o]=ans;
          return; 
        }
        else
        {
            int m=l+((r-l)>>1);
            if(ind<=m)
            {
                exch((o<<1),l,m,ind,ans);//|1相当于+1 
            }
            else
            {
                exch((o<<1)|1,m+1,r,ind,ans);
            }   
        }
        st[o]=max(st[o<<1],st[(o<<1)|1]);
    }
    int sear(int o,int l,int r,int ql,int qr)
    {
        if(qr<l||ql>r)return 0;
        if(qr>=r&&ql<=l)return st[o];
        int m=l+((r-l)>>1);
        return max(sear((o<<1),l,m,ql,qr),sear((o<<1)|1,m+1,r,ql,qr));
    }
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
         scanf("%d",&a[i]);
    
        bulid(1,1,n);
    
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(a==1)
             printf("%d\n",sear(1,1,n,b,c));
            else 
             exch(1,1,n,b,c);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/dfsac/p/6819792.html

发表评论取消回复

表情：

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

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

相关阅读

相关 [模板] 线段树合并

线段树合并把若干棵叶子节点总数为 \\(n\\) 的线段树通过某种顺序合并成一棵线段树. 时间复杂度 \\(O(n \\log n)\\). 时间复杂度分析考

深藏阁楼爱情的钟/ 2023年08月17日 17:16/ 0 赞/ 81 阅读

相关线段树模板

P3372 【模板】线段树 1 include<cstdio> include<iostream> using namespace std;

小咪咪/ 2023年08月17日 17:08/ 0 赞/ 63 阅读

相关线段树模板

public class Main { public static void main(String[] args) {

浅浅的花香味﹌/ 2022年10月05日 01:53/ 0 赞/ 113 阅读

相关线段树模板（模板）

参考博客 http://blog.csdn.net/metalseed/article/details/8039326 持续更新。。。 \[外链图片转存失败,源站可能有防盗

野性酷女/ 2022年09月24日 05:19/ 0 赞/ 133 阅读

相关 1277 维护序列（线段树）

1. 问题描述：老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。有长为 N 的数列，不妨设为 a1，a2，…，aN。有如下三种操作形式：把数列中的

水深无声/ 2022年09月09日 00:28/ 0 赞/ 118 阅读

相关 //线段树模板

先摆模板。。。 //线段树模板 struct line \{ int left,right;//左端点、右端点 int n;//记录这条线段出现了多少次，默认

偏执的太偏执、/ 2022年08月14日 04:54/ 0 赞/ 163 阅读

相关线段树模板+详解

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点\[a,b\]，它

淩亂°似流年/ 2022年06月17日 03:42/ 0 赞/ 145 阅读

相关线段树模板

洛谷oj:[点我][Link 1] 线段树区间修改区间查询 include<iostream> include<cstdio> include<cm

小灰灰/ 2022年05月16日 05:39/ 0 赞/ 181 阅读

相关二维线段树模板

-------------------- title: 二维线段树模板 date: 2018-10-31 15:21:44 tags: \- 二维线段树 c

以你之姓@/ 2022年04月22日 02:26/ 0 赞/ 198 阅读

相关序列操作（线段树，模板）

n个数，m次操作若a==1，求区间b-c最大值若a==2，将a\[ b \]改为c include<iostream> include<cstdi

小鱼儿/ 2022年01月07日 13:53/ 0 赞/ 191 阅读