美文网首页线段树
线段树

线段树

作者: Gitfan | 来源:发表于2017-03-16 10:13 被阅读0次

    http://blog.csdn.net/liuledidai/article/details/9964697

    ( 1 )线段树功能: 单点替换 区间最值
    I Hate It

    #include <cstdio>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 222222;
int MAX[maxn<<2];
void PushUP(int rt) {
MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l,int r,int rt) {  //rt当前节点编号
    if (l == r)//l==r,说明rt节点是叶子节点
    {           //由于先build左子树,再build右子树,所以最终会先写完左边的叶子节点,再写完右边的叶子节点
        scanf("%d",&MAX[rt]);
        return ;
    }
    int m = (l + r) >> 1;
    build(l , m , rt << 1);//rt*2
    build(m + 1 , r , rt << 1 | 1);//rt*2+1( rt*2 是偶数,rt<<1|1=rt*2+1)
    PushUP(rt);
}
void update(int p,int sc,int l,int r,int rt)
{
    if (l == r) {
        MAX[rt] = sc;
        return ;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p , sc , l , m , rt << 1);
    else update(p , sc , m + 1 , r , rt << 1 | 1);
    //PushUP(rt);
     MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
int query(int L,int R,int l,int r,int rt)//l r为线段树的完美区间,l mid为左子树区间, mid+1,r为右子树区间
{                                        //L , R是当前查询区间,它可能不是完美的,有可能包含左子树区间的一部分或者右子树的一部分
    if(L==l&&R==r) return MAX[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if(m>=R) return query(L,R,l,m,rt<<1);
    else if(m+1<=L) return query(L,R,m+1,r,rt<<1|1);
    else return max(query(L,m,l,m,rt<<1),query(m+1,R,m+1,r,rt<<1|1));
}
int main() {
    int n , m;
    while (~scanf("%d%d",&n,&m)) {
        build(1 , n , 1);
        while (m --) {
            char op[2];
            int a , b;
            scanf("%s%d%d",op,&a,&b);
            if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));
            else update(a , b , 1 , n , 1);
        }
    }
    return 0;
}

    （ 2）线段树功能:update:单点增减 query:区间求和
    敌兵布阵

    #include <cstdio>
#include <algorithm>
#include<cstring>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN=50010;
int sum[MAXN<<2];
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&sum[rt]);
        return;
    }
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int pos,int val,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]+=val;
        return;
    }
    if(pos<=mid) update(pos,val,l,mid,rt<<1);
    else update(pos,val,mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int query(int L,int R,int l,int r,int rt)
{
    if(L==l&&R==r) return sum[rt];
    if(R<=mid) return query(L,R,l,mid,rt<<1);
    else if(mid+1<=L) return query(L,R,mid+1,r,rt<<1|1);
    else return query(L,mid,l,mid,rt<<1)+query(mid+1,R,mid+1,r,rt<<1|1);
}
int main()
{
    int t,n,L,R,val,pos;
    char order[10];
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d",&n);
        build(1,n,1);
        printf("Case %d:\n",cas);
        while(true)
        {
            scanf("%s",order);
            if(strcmp(order,"End")==0) break;
            else if(strcmp(order,"Query")==0)
            {
                scanf("%d%d",&L,&R);
                printf("%d\n",query(L,R,1,n,1));
            }
            else if(strcmp(order,"Add")==0)
            {
                scanf("%d%d",&pos,&val);
                update(pos,val,1,n,1);
            }
            else
            {
                scanf("%d%d",&pos,&val);
                update(pos,-val,1,n,1);
            }
        }
    }
    return 0;
}

    求逆序数+离散化
    （ 3 ）线段树功能:update:单点增减 query:区间求和
    参考文档
    Ultra-QuickSort
    题意:
    求解一个序列的逆序数

    #include <cstdio>
#include<cstdlib>
#include<string.h>
#include <algorithm>
#define maxn  500010
using namespace std;
int segTree[maxn<<2],aa[maxn];
struct Node
{
    int val,id;
}arr[maxn];
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return segTree[rt];
    int mid=(l+r)>>1;
    int ret=0;
    if(L<=mid) ret+=query(L,R,l,mid,rt<<1);
    if(R>=mid+1) ret+=query(L,R,mid+1,r,(rt<<1)|1);
    return ret;
}
void update(int index,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]++;
        return;

    }
    int mid=(l+r)>>1;
    if(index<=mid) update(index,l,mid,rt<<1);
    else update(index,mid+1,r,(rt<<1)|1);
    segTree[rt]=segTree[rt<<1]+segTree[(rt<<1)|1];
}
int cmp(const void *a,const void * b)
{
    return (*(Node *)a).val-(*(Node *)b).val;
}
int main() {
    int n,i;
    while(scanf("%d",&n)!=EOF,n)
    {
        memset(segTree,0,sizeof(segTree));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&arr[i].val);
            arr[i].id=i;
        }
        qsort(arr+1,n,sizeof(Node),cmp);
        for(int i=1;i<=n;i++)
            aa[arr[i].id]=i;
        long long  sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=query(aa[i],n,1,n,1);
            update(aa[i],1,n,1);
        }
        printf("%lld\n",sum);
    }

}

    Minimum Inversion Number

    #include <cstdio>
#include<cstdlib>
#include<string.h>
#include <algorithm>
#define maxn  5005
using namespace std;
int segTree[maxn<<2],arr[maxn];
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return segTree[rt];
    int mid=(l+r)>>1;
    int ret=0;
    if(L<=mid) ret+=query(L,R,l,mid,rt<<1);
    if(R>=mid+1) ret+=query(L,R,mid+1,r,(rt<<1)|1);
    return ret;
}
void update(int index,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]++;
        return;

    }
    int mid=(l+r)>>1;
    if(index<=mid) update(index,l,mid,rt<<1);
    else update(index,mid+1,r,(rt<<1)|1);
    segTree[rt]=segTree[rt<<1]+segTree[(rt<<1)|1];
}
int main() {
    int n,i;
    while(scanf("%d",&n)!=EOF)
    {
        memset(segTree,0,sizeof(segTree));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&arr[i]);
        }
        int  sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=query(arr[i],n-1,0,n-1,1);
            update(arr[i],0,n-1,1);
        }
        int ret=sum;
        for(int i=1;i<=n;i++)
        {
            sum+=n-arr[i]-arr[i]-1;
            ret=min(sum,ret);
        }
        printf("%lld\n",ret);
    }
}

    ( 4 ) 题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子
    思路:每次找到最大值的位子,然后减去L
    线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了)

    把每行看成线段树的叶子记录每片叶子的剩余空间,而根节点中保存的是叶子节点最大的剩余空间,每次判断给定的宽度从根节点能否插入,若左子数可以插则优先插入左子树,这样就可以保证每次插入都插在最上面。

    Billboard

    #include <cstdio>
#include<cstdlib>
#include<string.h>
#include <algorithm>
#define maxn  900010
using namespace std;
int segTree[maxn],w,h,n;
void build(int l,int r,int rt)
{
    segTree[rt]=w;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
int query(int need,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]-=need;
        return l;
    }
    int ans,mid=(l+r)>>1;
    if(segTree[rt<<1]>=need) ans=query(need,l,mid,rt<<1);
    else ans=query(need,mid+1,r,rt<<1|1);
    segTree[rt]=max(segTree[rt<<1],segTree[rt<<1|1]);
    return ans;
}
int main() {
    int i,need;
    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        h=min(h,n);
        build(1,h,1);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&need);
            if(segTree[1]<need) printf("-1\n");
            else printf("%d\n",query(need,1,h,1));
        }
    }
}

    https://scut.online/problem.php?id=77
    ( 5 ) 题意：有两个操作：
    1、将区间[ L,R ]里的所有数变为原来的一半。
    2、询问区间 [ L,R ]的数之和，结果对1000000007取模。
    n,m(n,m≤100000），n为点的个数，编号为1-n，m为操作次数
    线段树功能：区间更新，区间求和。注意一个可以优化的地方：在query和update操作中，如果segTree[rt]==0，则不必递归下去了；不然容易超时。

    #include<stdio.h>
#include <string.h>
using namespace std;
#define maxn 100010
typedef long long LL;
LL segTree[maxn<<2];
const LL mod=1000000007;
//void pushUp(int rt)
//{
//    segTree[rt]=(segTree[rt<<1]+segTree[(rt<<1)|1])%mod;
//}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%lld",&segTree[rt]);
        return;
    }
    int mid=l+((r-l)>>1);
    build(l,mid,rt<<1);
    build(mid+1,r,(rt<<1)|1);
    segTree[rt]=(segTree[rt<<1]+segTree[(rt<<1)|1])%mod;
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return segTree[rt];
    if(L<=l&&r<=R&&segTree[rt]==0) return 0;
    int mid=l+((r-l)>>1);
    LL sum=0;
    if(mid>=L) sum=(sum+query(L,R,l,mid,rt<<1))%mod;
    if(mid+1<=R) sum=(sum+query(L,R,mid+1,r,(rt<<1)|1))%mod;
    return sum;
}
void update(int L,int R,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]>>=1;
        return;
    }
    if(L<=l&&r<=R&&segTree[rt]==0) return;
    int mid=l+((r-l)>>1);
    if(L<=mid) update(L,R,l,mid,rt<<1);
    if(mid+1<=R) update(L,R,mid+1,r,(rt<<1)|1);
    segTree[rt]=(segTree[rt<<1]+segTree[(rt<<1)|1])%mod;
}
int main()
{
    int t,L,R;
    char op[5];
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        build(1,n,1);
        for(int i=1;i<=m;i++)
        {
            scanf("%s%d%d",op,&L,&R);
            if(op[0]=='A')
            {
                printf("%lld\n",query(L,R,1,n,1));
            }
            else
            {
                update(L,R,1,n,1);
            }
        }
    }
}

    ( 6 ) 线段树功能：update :区间增减 query:区间求和
    题目大意：给定N个数的序列，有Q个操作。
    操作分两种：
    1、将某个区间内的所有数都加上某个数。
    2、计算某个区间的所有数之和并输出。

    方法一:逐点更新

    我们有一个朴素的思路,更新区间时对区间内的所有点逐个更新

    #include <cstdio>
#include <algorithm>
#include<cstring>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN=100010;
long long sum[MAXN<<2];
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int L,int R,int l,int r,int rt,long long val)
{
    if(l==r)//对区间内的所有点逐个更新
    {
        sum[rt]+=val;
        return;
    }
    if(R<=mid) update(L,R,l,mid,rt<<1,val);
    else if(mid+1<=L) update(L,R,mid+1,r,rt<<1|1,val);
    else
    {
        update(L,mid,l,mid,rt<<1,val);
        update(mid+1,R,mid+1,r,rt<<1|1,val);
    }
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
long long query(int L,int R,int l,int r,int rt)
{
    if(L==l&&R==r) return sum[rt];
    if(R<=mid) return query(L,R,l,mid,rt<<1);
    else if(mid+1<=L) return query(L,R,mid+1,r,rt<<1|1);
    return query(L,mid,l,mid,rt<<1)+query(mid+1,R,mid+1,r,rt<<1|1);
}
int main()
{
    int n,m,L,R;
    long long val;
    char op[5];
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",op);
        if(op[0]=='Q')
        {
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(L,R,1,n,1));
        }
        else
        {
            scanf("%d%d%lld",&L,&R,&val);
            update(L,R,1,n,1,val);
        }
    }
    return 0;
}

    但是,对每个点逐个进行更新,相当于暴力无疑,这样会很容易超时的,而且也体现不出线段树的优势!!!
    所以需要进行延迟更新,延迟更新指等到调用update时或者查询时才更新节点的孩子的值

    方法二 :延迟更新法

    A Simple Problem with Integers

    #include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100010;
#define lson l,md,(rt<<1)
#define rson md+1,r,(rt<<1|1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define md ((l+r)>>1)
LL sum[maxn<<2],lazy[maxn<<2];
void up(int rt)
{
    sum[rt]=sum[ls]+sum[rs];
}
void down(int l,int r,int rt)//延迟标记向下(孩子节点)传递
{
    if(lazy[rt])
    {
        sum[ls]+=(md-l+1)*lazy[rt];//更新左孩子节点的val
        lazy[ls]+=lazy[rt];//延迟标记向左孩子传递,以表明我左孩子节点已经更新了,
//但是!!左孩子的子节点还没更新呢!!!

        sum[rs]+=(r-(md+1)+1)*lazy[rt];//更新右孩子
        lazy[rs]+=lazy[rt];//延迟标记向右孩子传递,以表明我右孩子节点已经更新了,
//但是!!右孩子的子节点还没更新呢!!!

        lazy[rt]=0;//当前节点已经更新过了,所以取消标记
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=0;//初始化为0
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    build(lson);
    build(rson);
    up(rt);
}
void update(int L,int R,int l,int r,int rt,LL val)
{
    if(L==l&&r==R)//如果当前要更新的区间和线段树的完美区间一样
    {//那就把当前的区间给它更新,并更新当前节点lazy标记,表明它的两个孩子还没更新
//举个例子,假设总区间为1-12,现在要求更新6-10;假设现在更新到7-9,
//很明显,7-9是线段树的完美区间,所以对该段整段更新:sum[rt]+=(R-L+1)*val;
//但是!!!它的两个孩子节点还没更新呢,它就return了
//所以为这个节点添加延迟标记,以表明它的孩子节点还没更新:lazy[rt]+=val;
        sum[rt]+=(R-L+1)*val;
        lazy[rt]+=val;
        return;
    }
    down(l,r,rt);//如果当前节点有延迟标记,那么更新一下节点的val以及传递延迟标记给孩子节点

    if(md>=R) update(L,R,lson,val);
    else if(md+1<=L) update(L,R,rson,val);
    else{
        update(L,md,lson,val);
        update(md+1,R,rson,val);
    }
    up(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L==l&&r==R) return sum[rt];
    down(l,r,rt);//如果当前节点有延迟标记,那么更新一下节点的val以及传递延迟标记给孩子节点
    if(md>=R) return query(L,R,lson);
    else if(md+1<=L) return query(L,R,rson);
    return query(L,md,lson)+query(md+1,R,rson);
}
int main() {
    int n,m,L,R;
    LL val;
    char op[5];
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",op);
        if(op[0]=='Q')
        {
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(L,R,1,n,1));
        }
        else
        {
            scanf("%d%d%lld",&L,&R,&val);
            update(L,R,1,n,1,val);
        }
    }
    return 0;
}

    方法三:
    也是延迟更新但是有点不一样,具体请看代码

    #include<cstdio>
#include <algorithm>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN=100010;
long long sum[MAXN*4],mark[MAXN*4];
void build(int l,int r,int rt)
{
    sum[rt]=mark[rt]=0;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int l,int r,int L,int R,int rt,int val)
{
    sum[rt]=sum[rt]+(R-L+1)*val;
    if(l==L&&R==r)
    {
        mark[rt]+=val;
        return;
    }
    if(R<=mid) update(l,mid,L,R,rt<<1,val);
    else if(L>mid) update(mid+1,r,L,R,rt<<1|1,val);
    else
    {
        update(l,mid,L,mid,rt<<1,val);
        update(mid+1,r,mid+1,R,rt<<1|1,val);
    }
}
long long query(int l,int r,int rt,int L,int R)
{
    if(L==l&&R==r) return sum[rt];
    long long ans=(R-L+1)*mark[rt];
    if(R<=mid) ans+=query(l,mid,rt<<1,L,R);
    else if(L>mid) ans+=query(mid+1,r,rt<<1|1,L,R);
    else
    {
        ans+=query(l,mid,rt<<1,L,mid);
        ans+=query(mid+1,r,rt<<1|1,mid+1,R);
    }
    return ans;
}
int main()
{
    int n,m,L,R;
    long long  val;
    char op[5];
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",op);
        if(op[0]=='Q')
        {
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(1,n,1,L,R));
        }
        else
        {
            scanf("%d%d%lld",&L,&R,&val);
            update(1,n,L,R,1,val);
        }
    }
    return 0;
}

    ( 7 ) 线段树功能： update：区间替换 ，query：区间求和
    Just a Hook
    题意：
    一段线段由n条小线段组成，每次操作把一个区间的小线段变成金银铜之一（金的价值为3，银为2，铜为1），最初可当做全为铜；最后求这条线段的总价值。

    #include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100010;
#define lson l,md,(rt<<1)
#define rson md+1,r,(rt<<1|1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define md ((l+r)>>1)
LL sum[maxn<<2],lazy[maxn<<2];
void up(int rt)
{
    sum[rt]=sum[ls]+sum[rs];
}
void down(int l,int r,int rt)
{
    if(lazy[rt])
    {
        sum[ls]=(md-l+1)*lazy[rt];
        lazy[ls]=lazy[rt];

        sum[rs]=(r-(md+1)+1)*lazy[rt];
        lazy[rs]=lazy[rt];

        lazy[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=0;
    if(l==r)
    {
        sum[rt]=1;
        return;
    }
    build(lson);
    build(rson);
    up(rt);
}
void update(int L,int R,int l,int r,int rt,LL val)
{
    if(L==l&&r==R)
    {
        sum[rt]=(R-L+1)*val;
        lazy[rt]=val;
        return;
    }
    down(l,r,rt);

    if(md>=R) update(L,R,lson,val);
    else if(md+1<=L) update(L,R,rson,val);
    else{
        update(L,md,lson,val);
        update(md+1,R,rson,val);
    }
    up(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L==l&&r==R) return sum[rt];
    down(l,r,rt);
    if(md>=R) return query(L,R,lson);
    else if(md+1<=L) return query(L,R,rson);
    return query(L,md,lson)+query(md+1,R,rson);
}
int main() {
    int t,n,m,L,R;
    LL val;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d%d",&n,&m);
        build(1,n,1);
        while(m--)
        {
            scanf("%d%d%lld",&L,&R,&val);
            update(L,R,1,n,1,val);
        }
        printf("Case %d: The total value of the hook is %lld.\n",cas,query(1,1,1,1,1));
    }
    return 0;
}

    https://vjudge.net/problem/HDU-1698
    ( 7 ) 线段树功能： update：区间变为原来的b次方 ，query：区间乘积
    题意：操作1： l ,r ,b : 把k∈[l,r] 的妹子, 能力值 a​k变成ak^​b
    操作2：l , r : 求累乘 ∏（​l⩽k⩽r）ak
    题解：a​^k ≡ a^(​k mod (p−1)) mod p , p是素数.

    #include<cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100020;
const LL mod=1000000007;
#define lson l,md,(rt<<1)
#define rson md+1,r,(rt<<1|1)
#define md ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
LL sum[maxn<<2],lazy[maxn<<2];
LL pow_mod(LL a,int b)
{
    LL res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
void up(int rt)
{
    sum[rt]=sum[ls]*sum[rs]%mod;
}
void down(int l,int r,int rt)
{
     if(lazy[rt]!=1)
    {
        sum[ls]=pow_mod(sum[ls],lazy[rt]);
        lazy[ls]=lazy[ls]*lazy[rt]%(mod-1);

        sum[rs]=pow_mod(sum[rs],lazy[rt]);
        lazy[rs]=lazy[rs]*lazy[rt]%(mod-1);

        lazy[rt]=1;
    }
}
void update(int L,int R,int l,int r,int rt,int b)
{
    if(L==l&&r==R)
    {
        sum[rt]=pow_mod(sum[rt],b);
        lazy[rt]=lazy[rt]*b%(mod-1);
        return;
    }
    down(l,r,rt);
    if(R<=md) update(L,R,lson,b);
    else if(L>md) update(L,R,rson,b);
    else{
        update(L,md,lson,b);
        update(md+1,R,rson,b);
    }
    sum[rt]=sum[ls]*sum[rs]%mod;
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L==l&&r==R) return sum[rt];
    down(l,r,rt);
    if(R<=md) return query(L,R,lson);
    else if(L>md) return query(L,R,rson);
    return query(L,md,lson)*query(md+1,R,rson)%mod;
}
void build(int l,int r,int rt)
{
    lazy[rt]=1;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return ;
    }
    build(lson);
    build(rson);
    sum[rt]=sum[ls]*sum[rs]%mod;
}
int main() {
    int t,n,m;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        build(1, n, 1);
        while(m--) {
            int op, l, r, b;
            scanf("%d%d%d", &op, &l, &r);
            if(op == 1) {
                scanf("%d", &b);
                update(l,r,1,n,1,b);
            }
            else {
                LL ans = query(l,r,1,n,1);
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}

    相关文章

      网友评论

        本文标题：线段树

        本文链接：https://www.haomeiwen.com/subject/tlcdnttx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        线段树

        关于我们|服务条款|联系我们|线段树|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！