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

小鱼儿 2022-01-07 13:53 236阅读 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 条评论，236人围观）

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

相关阅读

相关代码源线段树模板

线段树1 ![ff281ef2601f426989c2d6b96f1790ac.png][] ![937ca3a4056d4614a44a51df5529ce54.pn

约定不等于承诺〃/ 2024年03月17日 13:59/ 0 赞/ 42 阅读

相关 [模板] 线段树合并

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

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

相关线段树模板

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

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

相关线段树模板

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

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

相关线段树模板（模板）

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

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

相关 //线段树模板

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

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

相关线段树模板+详解

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

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

相关线段树模板

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

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

相关二维线段树模板

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

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

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

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

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