首页 > 其他分享 >线段树

线段树

时间：2024-09-06 17:48:03浏览次数：10  
标签：return jia int 线段 tree mid sum

查找区间最大最小值

查看代码 

#include<bits/stdc++.h>//维护最大最小值
#define int long long
using namespace std;
int n,q;
int tree1[4000000],tree2[4000000],a[1000000];
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree1[p]=a[l];
        tree2[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree1[p]=max(tree1[p*2],tree1[p*2+1]);
    tree2[p]=min(tree2[p*2],tree2[p*2+1]);
}
int calc1(int p,int l,int r,int x,int y)
{
    if(x<=l&&y>=r)
    {
        return tree1[p];
    }
    int mid=(l+r)/2;
    int ans=-LLONG_MAX;
    if(x<=mid)ans=max(ans,calc1(p*2,l,mid,x,y));
    if(y>mid)ans=max(ans,calc1(p*2+1,mid+1,r,x,y));
    return ans;
}
int calc2(int p,int l,int r,int x,int y)
{
    if(x<=l&&y>=r)
    {
        return tree2[p];
    }
    int mid=(l+r)/2;
    int res=LLONG_MAX;
    if(x<=mid)res=min(res,calc2(p*2,l,mid,x,y));
    if(y>mid)res=min(res,calc2(p*2+1,mid+1,r,x,y));
    return res;
}
signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int y,z;
        cin>>y>>z;
        cout<<calc1(1,1,n,y,z)-calc2(1,1,n,y,z)<<endl;
    }
    return 0;
}

区间修改和

查看代码 
 #include<bits/stdc++.h>//区间修改和
#define int long long
using namespace std;
int n,q,ff;
int tree[4000100],a[4000100],lazy[4000100];
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p]=tree[p*2]+tree[p*2+1];
}
void pushdown(int p,int l,int r)
{
    if(lazy[p]==0) return;
    int mid=(l+r)/2;
    tree[2*p]+=(mid-l+1)*lazy[p];
    lazy[2*p]+=lazy[p];
    tree[2*p+1]+=(r-mid)*lazy[p];
    lazy[2*p+1]+=lazy[p];
    lazy[p]=0;
}
void change(int p,int l,int r,int x,int y,int z)
{
    if(y<l||x>r)return;
    if(x<=l&&r<=y)
    {
        tree[p]+=(r-l+1)*z;
        lazy[p]+=z;
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    change(p*2,l,mid,x,y,z);
    change(p*2+1,mid+1,r,x,y,z);
    tree[p]=tree[p*2]+tree[p*2+1];
}
int calc(int p,int l,int r,int x,int y)
{
    if(y<l||x>r)return 0;
    if(x<=l&&y>=r)
    {
        return tree[p];
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    //if(y<=mid)return calc(p*2,l,mid,x,y);
    //if(x>mid)return calc(p*2+1,mid+1,r,x,y);
    //return calc(p*2,l,mid,x,mid)+calc(p*2+1,mid+1,r,mid+1,y);
    return calc(p*2,l,mid,x,y)+calc(p*2+1,mid+1,r,x,y);
}
signed main()
{
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    scanf("%lld %lld",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        char c;
        scanf("%s",&c);
        if(c=='1')
        {
            int x,y,z;
            scanf("%lld %lld %lld",&x,&y,&z);
            change(1,1,n,x,y,z);
        }
        else
        {
            int y,z;
            scanf("%lld %lld",&y,&z);
            printf("%lld\n",calc(1,1,n,y,z));
        }
    }
    return 0;
}

查找区间元素和，区间元素平方和， 将区间[l,r]内的每一个元素都乘上x，将区间[l,r]内的每一个元素都加上x

查看代码 
 #include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,ff;
int a[400010],lazy[400010];
struct node{
    int sum;
    int jia;
    int cheng;
    int ping;
}tree[4000000];
void build(int p,int l,int r)
{
    tree[p].jia=0;
    tree[p].cheng=1;
    if(l==r)
    {
        tree[p].sum=a[l];
        tree[p].ping=a[l]*a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
    tree[p].ping=tree[p*2].ping+tree[p*2+1].ping;
}
void pushdown(int p,int l,int r)
{
    int mid=(l+r)/2;
    tree[2*p].jia*=tree[p].cheng;
    tree[2*p+1].jia*=tree[p].cheng;
    tree[2*p].cheng*=tree[p].cheng;
    tree[2*p+1].cheng*=tree[p].cheng;
    tree[2*p].sum*=tree[p].cheng;
    tree[2*p+1].sum*=tree[p].cheng;
    tree[2*p].ping*=tree[p].cheng*tree[p].cheng;
    tree[2*p+1].ping*=tree[p].cheng*tree[p].cheng;
    tree[p].cheng=1;
    if(tree[p].jia)
    {
         tree[2*p].jia+=tree[p].jia;
         tree[2*p+1].jia+=tree[p].jia;
         tree[2*p].ping+=2*tree[p].jia*tree[2*p].sum+(mid-l+1)*tree[p].jia*tree[p].jia;
         tree[2*p+1].ping+=2*tree[p].jia*tree[2*p+1].sum+(r-(mid+1)+1)*tree[p].jia*tree[p].jia;
         tree[2*p].sum+=(mid-l+1)*tree[p].jia;
         tree[2*p+1].sum+=(r-(mid+1)+1)*tree[p].jia;
         tree[p].jia=0;
    }
}
void changejia(int p,int l,int r,int x,int y,int z)
{
    if(y<l||x>r)return;
    if(x<=l&&r<=y)
    {
        tree[p].jia+=z;
        tree[p].ping+=2*z*tree[p].sum+(r-l+1)*z*z;
        tree[p].sum+=(r-l+1)*z;
        return;
    }
    if(tree[p].jia||tree[p].cheng!=1)pushdown(p,l,r);
    int mid=(l+r)/2;
    if(x<=mid)changejia(p*2,l,mid,x,y,z);
    if(y>mid)changejia(p*2+1,mid+1,r,x,y,z);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
    tree[p].ping=tree[p*2].ping+tree[p*2+1].ping;
}
void changeche(int p,int l,int r,int x,int y,int z)
{
    if(y<l||x>r)return;
    if(x<=l&&r<=y)
    {
        tree[p].cheng*=z;
        tree[p].jia*=z;
        tree[p].ping*=z*z;
        tree[p].sum*=z;
        return;
    }
    if(tree[p].jia||tree[p].cheng!=1)pushdown(p,l,r);
    int mid=(l+r)/2;
    if(x<=mid)changeche(p*2,l,mid,x,y,z);
    if(y>mid)changeche(p*2+1,mid+1,r,x,y,z);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
    tree[p].ping=tree[p*2].ping+tree[p*2+1].ping;
}
int calc1(int p,int l,int r,int x,int y)
{
    if(y<l||x>r)return 0;
    if(x<=l&&y>=r)
    {
        return tree[p].sum;
    }
    if(tree[p].jia||tree[p].cheng!=1)pushdown(p,l,r);
    int mid=(l+r)/2;
    int ans=0;
    if(x<=mid)ans+=calc1(2*p,l,mid,x,y);
    if(y>mid)ans+=calc1(2*p+1,mid+1,r,x,y);
    return ans;
}
int calc2(int p,int l,int r,int x,int y)
{
    if(y<l||x>r)return 0;
    if(x<=l&&y>=r)
    {
        return tree[p].ping;
    }
    if(tree[p].jia||tree[p].cheng!=1)pushdown(p,l,r);
    int mid=(l+r)/2;
    int ans=0;
    if(x<=mid)ans+=calc2(2*p,l,mid,x,y);
    if(y>mid)ans+=calc2(2*p+1,mid+1,r,x,y);
    return ans;
}
signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int c,x,y,z;
        cin>>c>>x>>y;
        if( c == 1)
            cout<<calc1(1,1,n,x,y)<<endl;

        if( c == 2)
            cout<<calc2(1,1,n,x,y)<<endl;
        if( c == 3)
        {
            cin>>z;
            changeche(1,1,n,x,y,z);
        }
        if( c == 4)
        {
            cin>>z;
            changejia(1,1,n,x,y,z);
        }
    }
    return 0;
}

标签：return,jia,int,线段,tree,mid,sum
From： https://www.cnblogs.com/violet-hty/p/18400720

相关文章

  • 变种线段树 提高篇
    可持久化线段树注意，它的全称为可持久化权值线段树。例题\(1\)：可持久化线段树2首先我们考虑几个暴力：对于每次询问，找出区间中的所有数，直接排序求第\(k\)小。这样做的时间复杂度为\(O(nq\logn)\)的。对于每次询问，建出一棵权值线段树，然后权值线段树上二分查找即可。发现......
  • 线段树分治
    前置知识：可撤销化并查集注意：可撤销化并查集的作用和删边不一样，其只能撤销最近的一次操作。既然只需撤销，那么只需在合并并查集时用个vector记录下合并的哪两个点，撤销时就直接还原就行了。这里要强调一下，可撤销化并查集不能路径压缩，只能启发式合并。代码intf[MAXN],sz[MAXN......
  • codeforces做题记录（1924B）& 回顾线段树
    1924B.SpaceHarbour题意：n个点排成一行，其中某些点上面建有港湾，港湾有一个权值，对每个点我们定义点的权值为“左边（包括自己）第一个港湾上的权值\(\times\)到右边（包括自己）第一个港湾的距离”（保证在一开始1号和n号点上都有港湾）。有q次操作：操作1给定x和v，表示在x点上建立权值为v的......
  • 优化半群结构的线段树信息维护
    今天在做区间历史和。感觉给每个标记一个含义实在太抽象了，遂听从白神建议学习矩阵维护信息和优化半群结构。前置知识：大魔法师，用矩阵维护轮换信息。我们发现区间历史和事实上是对“历史和”变量被“和”变量轮换加法的结果，不知道为什么以前没反应过来和大魔法师有关。区间加和区......
  • 线段覆盖问题
    1.线段不覆盖问题给出\(n\)个线段，选择尽量多的线段使得线段无重叠，问最多可以选多少条线段。解析考虑贪心，将线段按右端点从小到大排序，如果这条线段的左端点大于上一条线段的右端点那就选择这条线段。为什么这么贪是对的呢，因为将右端点排序可以使右边剩余的空间尽量大，那么剩余......
  • Luogu P4425 转盘 题解 [ 黑 ] [ 线段树 ] [ 贪心 ] [ 递归 ]
    转盘：蒟蒻的第一道黑，这题是贪心和线段树递归合并的综合题。贪心破环成链的trick自然不用多说。首先观察题目，很容易发现一个性质：只走一圈的方案一定最优。这个很容易证，因为再绕一圈回来标记前面的和等前面的标记完之后继续走是等价的，并且再绕一圈甚至可能更劣。于是，我们只用走......
  • 线段树
    线段树区间加区间和区间乘法的懒标记优先级高于加法，且会对加法懒标记造成影响voidpush_up(node&u,node&l,node&r){ u.sum=l.sum+r.sum;//}voidpushup(vector<node>&tr,intu){push_up(tr[u],tr[u<<1],tr[u<<1|1]);}voidpush_down(vector<node......
  • 【数据结构】【模板】李超线段树
    李超线段树定义可以看看洛谷的模板题目：作用优化动态规划，如果可以将一个动态规划的转移式子转化为\(y=kx+b\)的形式，那么我们可以边转移边将\(y=kx+b\)这条线段放入李超线段树，然后在下次转移时，直接调用下次计算出来的\(x\)位置上的最大值或最小值。（结合题目理解......
  • Luogu P4588 数学运算 题解 [ 绿 ] [ 线段树 ]
    LuoguP4588数学运算。虽然是一个很典的题，但里面的思想还是比较值得记录的。假做法一开始看到此题还以为是乘法逆元的模板题，但看到\(m\)与\(M\)不互质，就知道这种做法是假的了。注意exgcd虽然能求模数为合数的逆元，但是要是两数不互质就什么算法都搞不了了。因此，本题不能......
  • 线段树模版：从入门到入坟
    线段树模版：从入门到入坟线段树——单点修改1.求区间最值#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=200010;typedeflonglongll;structnode{ intminx; intl,r;}tr[N*4];inta[N];voidupdate(intp){ tr[p].minx=min(tr[......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99