线段树的板子和题目

1.单点修改，区间求和

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
struct node{
    int l,r;
    ll s;
}tree[maxn];
int a[maxn];
void push_up(int p){
    tree[p].s=tree[p*2].s+tree[p*2+1].s;
}
void build(int p,int l,int r){//p为当前节点编号，x,y为区间的左右端点 ,v是权值 
    tree[p].l=l;
    tree[p].r=r;
/*节点 
            1
        2       3
     4    5   6    7
*/
/*
                 [1,13]
                 
        [1,7]             [8,13]
        
   [1,4]     [5,7]  [8,10]     [11,13]
   
[1,2]  [3,4].......  

*/ 

    if(l==r){
        tree[p].s=a[l];
        return ; 
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    push_up(p);    
} 
void update(int p,int x,int k){
    int L=tree[p].l,R=tree[p].r;
    if(L==R){
        tree[p].s+=k;
        return ;
    }
    if(x<=tree[p*2].r){//左交点 
        update(p*2,x,k);
    }
    else{
        update(p*2+1,x,k);
    }
    push_up(p);
}
// l   r
ll query(int p,int l,int r){
    int L=tree[p].l,R=tree[p].r;
    ll ans=0;
    if(R<l||L>r){
        return 0;
    }
    if(l<=L&&R<=r){
        return tree[p].s;
    }
    if(tree[p*2].r>=l){//当前子左节点 
        ans+=query(p*2,l,r);
    }
    if(tree[p*2+1].l<=r){//当前子右节点 
        ans+=query(p*2+1,l,r);
    }
    return ans;
}
int main(){
    int t;
    cin>>t;
    int kase=1;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        build(1,1,n);
        printf("Case %d:
",kase++);
        char str[10];
        int l,r;
        while(scanf("%s",str)){
            if(str[0]=='E'){
                break;
            }
            scanf("%d%d",&l,&r);
            if(str[0]=='Q'){
                ll z=query(1,l,r);
                printf("%lld
",z);
            }
            else if(str[0]=='A'){
                update(1,l,r);
            }
            else if(str[0]=='S'){
                update(1,l,-r);
            }
        }
    } 
    return 0;
}

View Code

2.区间修改，区间求和

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=3e6+100;
struct node{
    ll l,r;
    ll s;
    ll lazy;
}t[maxn];
ll a[maxn];
int n,m;
void push(int p){
    t[2*p].lazy+=t[p].lazy;//下传标记 
    t[2*p].s+=1ll*(t[2*p].r-t[2*p].l+1)*t[p].lazy;
    
    t[2*p+1].lazy+=t[p].lazy;
    t[2*p+1].s+=1ll*(t[2*p+1].r-t[2*p+1].l+1)*t[p].lazy;
    
    t[p].lazy=0;//还原标记 
}
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].s=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    t[p].s=t[2*p].s+t[2*p+1].s;
} 
void update(int p,int l,int r,ll k){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        t[p].s+=1ll*(R-L+1)*k;
        t[p].lazy+=k;
        return ;
    }
    push(p);
    if(l<=t[2*p].r){
        update(2*p,l,r,k);
    } 
    if(r>=t[2*p+1].l){
        update(2*p+1,l,r,k);
    }
    t[p].s=t[2*p].s+t[2*p+1].s; 
}
ll query(int p,int l,int r){ 
    int L=t[p].l,R=t[p].r; 
    if(L>r||R<l){
        return 0; 
    }
    if(l<=L&&r>=R){
        return t[p].s;
    }
    ll ans=0;
    push(p);
    if(l<=t[2*p].r){
        ans+=query(2*p,l,r);
    }
    if(r>=t[2*p+1].l){
        ans+=query(2*p+1,l,r);
    }
    return ans; 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    char str[10];
    int l,r;
    ll k;
    for(int i=1;i<=m;i++){
        scanf("%s",str);
        if(str[0]=='Q'){
            scanf("%d%d",&l,&r); 
            ll ans=query(1,l,r);
            printf("%lld
",ans);
        }
        else if(str[0]=='C'){
            scanf("%d%d%lld",&l,&r,&k);
            update(1,l,r,k);
        }
    }
    return 0;
}

View Code

4.区间乘法和加法

要两个懒惰标记jia,cheng

当进行乘法操作的时候,加法标记也要乘k，就是+k*jia;

下传加法标记的时候就是要用（子节点加法标记*父节点的加发标记+父节点的加法标记）

下传乘法标记的时候就是（子节点的乘法标记*父节点的乘法标记）

区间和的话就是加法标记*区间长度+子结点的加法标记*夫节点的乘法标记

下传标记只是为了下一次操作，和区间求和不一样

void cheng(ll x,ll l,ll r,ll d)
{
    if (l<=t[x].l&&t[x].r<=r)//全部包括 
{//三个值全部都要乘上去

        t[x].date=t[x].date*d%mod;
        t[x].laze=t[x].laze*d%mod;
        t[x].mul=t[x].mul*d%mod;
    } else
    {
        pushdown(x);//向下传递值 
        ll mid=(t[x].l+t[x].r)/2;
        if (l<=mid) cheng(x*2,l,r,d);//继续往下搜
        if (r>mid)cheng(x*2+1,l,r,d);
        t[x].date=(t[x*2+1].date+t[x*2].date)%mod;//更新sum 
    }
    return;
}

void pushdown(ll x)
{
    t[x*2].laze=(t[x*2].laze*t[x].mul+t[x].laze)%mod;//加 
    t[x*2+1].laze=(t[x*2+1].laze*t[x].mul+t[x].laze)%mod;
    t[x*2].mul=(t[x*2].mul*t[x].mul)%mod;//乘 
    t[x*2+1].mul=(t[x*2+1].mul*t[x].mul)%mod;
    t[x*2].date=(t[x].laze*(t[x*2].r-t[x*2].l+1)%mod+t[x*2].date*t[x].mul%mod)%mod;//求和 
    t[x*2+1].date=(t[x].laze*(t[x*2+1].r-t[x*2+1].l+1)%mod+t[x*2+1].date*t[x].mul%mod)%mod;//求和 
    t[x].laze=0;t[x].mul=1; 
}

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map> 
#include <math.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll a[maxn]; 
ll mod;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
struct node{
    ll l;//l:左节点 r:右节点 
    ll r;//dat:当前节点的值 laze_tag:懒标记，记录改变的值，递归传值 
    ll date,laze;
    ll mul;
}t[maxn];//四倍n 
//void f(ll p,ll m,ll k){ 
//    t[p].laze=(t[p].laze*m+k)%mod;//懒标记传递
//    t[p].date+=(k*(t[p].r-t[p].l+1))%mod;//当前值加上所有节点总数*值     
//}
//void fmul(ll p,ll k){
//    t[p].mul=(t[p].mul*k)%mod;
//    t[p].date+=(t[p].date*k)%mod;
//}
//void pushdown(ll p){//传懒标 
//    f(p*2,t[p].mul,t[p].laze);
//    f(p*2+1,t[p].mul,t[p].laze);
//    fmul(p*2,t[p].mul);
//    fmul(p*2+1,t[p].mul);
//     //将懒标记的值传给下面的左右儿子节点
//    t[p].laze=0;
//    t[p].mul=1;
//    //复原懒标记 
//}
void pushdown(ll x)
{
    t[x*2].laze=(t[x*2].laze*t[x].mul+t[x].laze)%mod;//加 
    t[x*2+1].laze=(t[x*2+1].laze*t[x].mul+t[x].laze)%mod;
    t[x*2].mul=(t[x*2].mul*t[x].mul)%mod;//乘 
    t[x*2+1].mul=(t[x*2+1].mul*t[x].mul)%mod;
    t[x*2].date=(t[x].laze*(t[x*2].r-t[x*2].l+1)%mod+t[x*2].date*t[x].mul%mod)%mod;//求和 
    t[x*2+1].date=(t[x].laze*(t[x*2+1].r-t[x*2+1].l+1)%mod+t[x*2+1].date*t[x].mul%mod)%mod;//求和 
    t[x].laze=0;t[x].mul=1; 
}
void js(ll p,ll l,ll r){//建树 
    t[p].l=l;//记录左右节点 
    t[p].r=r;
    t[p].laze=0; 
    t[p].mul=1;
    if(l==r){//到达底部返回值 
        t[p].date=a[l];
        return ;
    }
    ll mid=(l+r)/2;//中点
    js(p*2,l,mid);
    js(p*2+1,mid+1,r);
        //递归初始化
    t[p].date=(t[p*2].date+t[p*2+1].date)%mod;
      //加上左右儿子节点 
}
void pushs(ll p,ll l,ll r,ll v){//区间加减
    if(t[p].l>=l&&t[p].r<=r){//如果区间被包含就修改并打上懒标记 
        t[p].date+=v*(t[p].r-t[p].l+1)%mod;//加上所有值
        t[p].laze+=v%mod;//懒标记修改 
        return ;
    }
    pushdown(p);//查询懒标记，因为下面要递归 
    ll mid=(t[p].l+t[p].r)/2;//取中点
    if(l<=mid){
        pushs(p*2,l,r,v);//修改左边 
    }
    if(r>mid){
        pushs(p*2+1,l,r,v);//修改右边  
    }
    t[p].date=(t[p*2].date+t[p*2+1].date)%mod;//回溯时加上左右儿子节点的值 
} 
//void cheng(ll p,ll l,ll r,ll w){
//    if(l<=t[p].l&&t[p].r<=r){
//        t[p].date=t[p].date*w%mod;
//        t[p].laze=t[p].laze*w%mod;
//        t[p].mul=t[p].mul*w%mod;
//        return ;
//    }
//    pushdown(p);
//    ll mid=(t[p].l+t[p].r)/2;//取中点
//    if(l<=mid){
//        pushs(p*2,l,r,w);//修改左边 
//    }
//    if(r>mid){
//        pushs(p*2+1,l,r,w);//修改右边  
//    }
//    t[p].date=(t[p*2].date+t[p*2+1].date)%mod;
//}
void cheng(ll x,ll l,ll r,ll d)
{
    if (l<=t[x].l&&t[x].r<=r)//全部包括 
{//三个值全部都要乘上去

        t[x].date=t[x].date*d%mod;
        t[x].laze=t[x].laze*d%mod;
        t[x].mul=t[x].mul*d%mod;
    } else
    {
        pushdown(x);//向下传递值 
        ll mid=(t[x].l+t[x].r)/2;
        if (l<=mid) cheng(x*2,l,r,d);//继续往下搜
        if (r>mid)cheng(x*2+1,l,r,d);
        t[x].date=(t[x*2+1].date+t[x*2].date)%mod;//更新sum 
    }
    return;
}
ll outt(ll p,ll l){//单点查询 
    if(t[p].l==l&&t[p].r==l){//找到目标点就返回 
        return t[p].date%mod;
    }
    pushdown(p);//先回复懒标记的值再传递，因为下面可能递归（要判断是否到了底部，就是这里出了问题QwQ）
    ll mid=(t[p].l+t[p].r)/2;//记录中点
    if(l<=mid) return outt(p*2,l)%mod;//找左边
    if(l>mid) return outt(p*2+1,l)%mod;//找右边 
}
ll check(ll p,ll l,ll r,ll x,ll y){
    if(l>=x&&r<=y){
        return t[p].date%mod;
    }
    ll mid=(t[p].l+t[p].r)/2;
    ll ans=0;
    pushdown(p);
    if(x<=mid){
        ans+=check(p*2,l,mid,x,y)%mod; 
    }
    if(mid<y){
        ans+=check(p*2+1,mid+1,r,x,y)%mod;
    }
    return ans%mod;
} 
int main(){
    int n,m; 
       cin>>n>>m>>mod;//读入 
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]); 
    js(1,1,n);//建树
    ll z;
    ll x,y,w; 
    for(int i=1;i<=m;i++){
        scanf("%lld",&z);
        if(z==1){
            scanf("%lld%lld%lld",&x,&y,&w);
            cheng(1,x,y,w);
        }
        else if(z==2){
            scanf("%lld%lld%lld",&x,&y,&w);
            pushs(1,x,y,w);
        }
        else if(z==3){
            scanf("%lld%lld",&x,&y);
            ll ans=check(1,1,n,x,y)%mod;
            printf("%lld
",ans%mod);
        }
    }
    return 0;//华丽丽的结束，可以A掉树状数组2了！！！ 
}

完整代码1

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
int n,m;
ll mod;
struct node{
    int l,r;
    ll sum;
    ll lazyj;
    ll lazyc;
}t[maxn];
ll a[maxn]; 
void push_up(int p){
    t[2*p].lazyj=((t[2*p].lazyj*t[p].lazyc)%mod+t[p].lazyj)%mod;
    t[2*p+1].lazyj=((t[2*p+1].lazyj*t[p].lazyc)%mod+t[p].lazyj)%mod;
    
    t[2*p].lazyc=(t[2*p].lazyc*t[p].lazyc)%mod;
    t[2*p+1].lazyc=(t[2*p+1].lazyc*t[p].lazyc)%mod;
    
    t[2*p].sum=(t[p].lazyj*(t[2*p].r-t[2*p].l+1)%mod+(t[2*p].sum*t[p].lazyc)%mod)%mod;
    t[2*p+1].sum=(t[p].lazyj*(t[2*p+1].r-t[2*p+1].l+1)%mod+(t[2*p+1].sum*t[p].lazyc)%mod)%mod;
    
    t[p].lazyj=0;
    t[p].lazyc=1;
    
}
void jiafa(int p,int l,int r,ll k){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        t[p].sum+=k*(t[p].r-t[p].l+1)%mod;
        t[p].lazyj+=k%mod;
        return ;
    }
    push_up(p);
    if(l<=t[2*p].r){
        jiafa(2*p,l,r,k);
    } 
    if(r>=t[2*p+1].l){
        jiafa(2*p+1,l,r,k);
    }
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
}
void chengfa(int p,int l,int r,ll k){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        t[p].sum=(t[p].sum*k)%mod;
        t[p].lazyc=(t[p].lazyc*k)%mod;
        t[p].lazyj=(t[p].lazyj*k)%mod; 
        return ;
    }
    push_up(p);
    if(l<=t[2*p].r){
        chengfa(2*p,l,r,k);
    } 
    if(r>=t[2*p+1].l){
        chengfa(2*p+1,l,r,k);
    }
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
}
void jianshu(int p,int l,int r){
    t[p].l=l,t[p].r=r;    
    t[p].lazyc=1;
    t[p].lazyj=0;
    if(l==r){
        t[p].sum=a[l];
        return ;
    }
    int mid=(l+r)/2;
    jianshu(p*2,l,mid);
    jianshu(p*2+1,mid+1,r);
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
} 
ll query(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        return t[p].sum%mod;
    }    
    ll ans=0;
    push_up(p);
    if(l<=t[2*p].r){
        ans+=query(2*p,l,r)%mod;
    }
    if(r>=t[2*p+1].l){
        ans+=query(2*p+1,l,r)%mod;
    }
    return ans%mod;
}
int main(){
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    jianshu(1,1,n);
    int op,l,r;
    ll k;
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%lld",&l,&r,&k);
            chengfa(1,l,r,k); 
        }
        else if(op==2){
            scanf("%d%d%lld",&l,&r,&k);
            jiafa(1,l,r,k);
        }
        else{
            scanf("%d%d",&l,&r);
            ll ans=query(1,l,r);
            printf("%lld
",ans%mod);
        }
    }
    return 0;
}

完整代码2

例题1：

例题2：就是把区间中的值变成同一个值，这个还带区间加法，区间重赋值，区间求和（就是让区间中的值先乘上0最加上某一个值）

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
const int mod=20007; 
int n,m;
struct node{
    int l,r;
    ll sum;
    ll lazyj;
    ll lazyc;
}t[maxn];
ll a[maxn]; 
void push_up(int p){
    t[2*p].lazyj=((t[2*p].lazyj*t[p].lazyc)%mod+t[p].lazyj)%mod;
    t[2*p+1].lazyj=((t[2*p+1].lazyj*t[p].lazyc)%mod+t[p].lazyj)%mod;
    
    t[2*p].lazyc=(t[2*p].lazyc*t[p].lazyc)%mod;
    t[2*p+1].lazyc=(t[2*p+1].lazyc*t[p].lazyc)%mod;
    
    t[2*p].sum=(t[p].lazyj*(t[2*p].r-t[2*p].l+1)%mod+(t[2*p].sum*t[p].lazyc)%mod)%mod;
    t[2*p+1].sum=(t[p].lazyj*(t[2*p+1].r-t[2*p+1].l+1)%mod+(t[2*p+1].sum*t[p].lazyc)%mod)%mod;
    
    t[p].lazyj=0;
    t[p].lazyc=1;
    
}
void jiafa(int p,int l,int r,ll k){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        t[p].sum+=k*(t[p].r-t[p].l+1)%mod;
        t[p].lazyj+=k%mod;
        return ;
    }
    push_up(p);
    if(l<=t[2*p].r){
        jiafa(2*p,l,r,k);
    } 
    if(r>=t[2*p+1].l){
        jiafa(2*p+1,l,r,k);
    }
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
}
void chengfa(int p,int l,int r,ll k){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        t[p].sum=(t[p].sum*k)%mod;
        t[p].lazyc=(t[p].lazyc*k)%mod;
        t[p].lazyj=(t[p].lazyj*k)%mod; 
        return ;
    }
    push_up(p);
    if(l<=t[2*p].r){
        chengfa(2*p,l,r,k);
    } 
    if(r>=t[2*p+1].l){
        chengfa(2*p+1,l,r,k);
    }
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
}
void jianshu(int p,int l,int r){
    t[p].l=l,t[p].r=r;    
    t[p].lazyc=1;
    t[p].lazyj=0;
    if(l==r){
        t[p].sum=a[l];
        return ;
    }
    int mid=(l+r)/2;
    jianshu(p*2,l,mid);
    jianshu(p*2+1,mid+1,r);
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
} 
ll query(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        return t[p].sum%mod;
    }    
    ll ans=0;
    push_up(p);
    if(l<=t[2*p].r){
        ans+=query(2*p,l,r)%mod;
    }
    if(r>=t[2*p+1].l){
        ans+=query(2*p+1,l,r)%mod;
    }
    return ans%mod;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i]=0;
    }
    jianshu(1,1,n);
    int op,l,r;
    ll k;
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%lld",&l,&r,&k);
            chengfa(1,l,r,0);
            jiafa(1,l,r,k); 
        }
        else if(op==2){
            scanf("%d%d%lld",&l,&r,&k);
            jiafa(1,l,r,k);
        }
        else{
            scanf("%d%d",&l,&r);
            ll ans1=query(1,l,r); 
            cout<<ans1%mod<<endl;
        } 
    }
    return 0;
}

区间重赋值不带区间加法（直接通过改变懒标就行）

传送门

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
struct node{
    int l,r;
    int dazy;
    int sum;
}t[maxn];
void push_up(int p){
    if(t[p].dazy){//必须的 
        t[2*p].dazy=t[p].dazy;
        t[2*p+1].dazy=t[p].dazy;
        t[2*p].sum=(t[2*p].r-t[2*p].l+1)*t[p].dazy;
        t[2*p+1].sum=(t[2*p+1].r-t[2*p+1].l+1)*t[p].dazy;
        t[p].dazy=0;
    }
}
void jianshu(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].dazy=0;//注意 
    if(l==r){
        t[p].sum=1;
        return ;    
    }
    int mid=(l+r)/2;
    jianshu(2*p,l,mid);
    jianshu(2*p+1,mid+1,r);
    t[p].sum=t[2*p+1].sum+t[2*p].sum;
}
void update(int p,int l,int r,int k){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        t[p].dazy=k;
        t[p].sum=(R-L+1)*k;
        return ;
    }
    push_up(p);
    if(l<=t[2*p].r){
        update(2*p,l,r,k);
    }
    if(r>=t[2*p+1].l){
        update(2*p+1,l,r,k);
    }
    t[p].sum=t[2*p+1].sum+t[2*p].sum;
}
int query(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        return t[p].sum;
    }
    push_up(p);
    int ans=0;
    if(l<=t[2*p].r){
        ans+=query(2*p,l,r);
    }
    if(r>=t[2*p+1].l){
        ans+=query(2*p+1,l,r);
    }
    return ans;
}
int main(){
    int t,n,m;
    scanf("%d",&t);
    int kase=0;
    while(t--){
        scanf("%d%d",&n,&m);
        jianshu(1,1,n);
        int l,r,k;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&l,&r,&k);
            update(1,l,r,k);
        }
        int ans=query(1,1,n);
        printf("Case %d: The total value of the hook is %d.
",++kase,ans); 
    }
}

View Code

查询区间最大值和最小值（只是查询）

#include<iostream>
#include<algorithm>
#include<math.h> 
#include<cstring>
using namespace std;
const int maxn=1e6+100;
struct node{
    int l,r;
    int ma,mi;
}t[maxn];
int a[maxn];
int max(int a,int b){
    if(a>b){
        return a;
    }
    return b;
}
int min(int a,int b){
    if(a>b){
        return b;
    }
    return a;
}
void jianshu(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].mi=a[l];
        t[p].ma=a[l];
        return ;
    } 
    int mid=(l+r)/2;
    jianshu(2*p,l,mid);
    jianshu(2*p+1,mid+1,r);
    t[p].ma=max(t[2*p].ma,t[2*p+1].ma);
    t[p].mi=min(t[2*p].mi,t[2*p+1].mi);
}
int query1(int p,int l,int r){//最小值 
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        return t[p].mi;
    } 
    if(r<=t[2*p].r){
        return query1(2*p,l,r);
    }
    else if(l>=t[2*p+1].l){
        return query1(2*p+1,l,r);
    }
    else{
        return min(query1(2*p,l,r),query1(2*p+1,l,r));
    }
}
int query2(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r){
        return t[p].ma;
    } 
    if(r<=t[2*p].r){
        return query2(2*p,l,r);
    }
    else if(l>=t[2*p+1].l){
        return query2(2*p+1,l,r);
    }
    else{
        return max(query2(2*p,l,r),query2(2*p+1,l,r));
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    jianshu(1,1,n);
    int l,r;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        //cout<<query2(1,l,r)<<" "<<query1(1,l,r)<<endl;
        int ans=query2(1,l,r)-query1(1,l,r);
        printf("%d
",ans);
    }
}

View Code

区间最大值（带修改）

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100; 
struct node{
    int l,r;
    int m;
}t[maxn];
int a[maxn];
int n,m;
void jianshu(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].m=a[l];
        return ;
    }
    int mid=(l+r)/2;
    jianshu(2*p,l,mid);
    jianshu(2*p+1,mid+1,r);
    t[p].m=max(t[2*p].m,t[2*p+1].m);
}
void update(int p,int pos,int k){
    if(t[p].l==t[p].r){
        t[p].m=k;
        return ;
    }
    if(pos<=t[2*p].r){
        update(2*p,pos,k);
    } 
    else{
        update(2*p+1,pos,k);
    }
    t[p].m=max(t[2*p].m,t[2*p+1].m);
}
int query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r){
        return t[p].m;
    } 
    if(r<=t[2*p].r){
        return query(2*p,l,r);
    }
    else if(l>=t[2*p+1].l){
        return query(2*p+1,l,r);
    }
    else{
        return max(query(2*p,l,r),query(2*p+1,l,r));
    }
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        char str[10];
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        jianshu(1,1,n);
        int l,r;
        int k;
        for(int i=1;i<=m;i++){
            scanf("%s",str);
            if(str[0]=='Q'){
                scanf("%d%d",&l,&r);
                int ans=query(1,l,r);
                printf("%d
",ans); 
            }
            else if(str[0]=='U'){
                scanf("%d%d",&l,&k);
                update(1,l,k);
            }
        }
    }
}

View Code

区间开根号

$2^$

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
template <typename Tp>
void read(Tp &x){//read(n);
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')){
        ch=getchar();
    }
    if(ch=='-'){
        fh=-1;ch=getchar();
    }else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    x*=fh;
}
const int maxn=1e6+100; 
struct node{
    int l,r;
    ll sum;
}t[maxn];
ll a[maxn];
void jianshu(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].sum=a[l];
        return ;
    }
    int mid=(t[p].l+t[p].r)>>1;
    jianshu(p<<1,l,mid);
    jianshu(p<<1|1,mid+1,r);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum; 
}
void update(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    if(L==R){
        t[p].sum=sqrt(t[p].sum);
        return ;
    } 
    if((R-L+1)>=t[p].sum){//区间内都是1 重点 
        return ;
    } 
    if(l<=t[p<<1].r){
        update(p<<1,l,r);
    } 
    if(r>=t[p<<1|1].l){
        update(p<<1|1,l,r);
    } 
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum; 
} 
ll query(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].sum;
    }
    ll ans=0;
    if(l<=t[p<<1].r){
        ans+=query(p<<1,l,r);
    }
    if(r>=t[p<<1|1].l){
        ans+=query(p<<1|1,l,r);
    }
    return ans;
}
int main(){
    int n,m;
    int kase=1;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }     
        jianshu(1,1,n);
        scanf("%d",&m); 
        printf("Case #%d:
",kase++);
        int op,l,r;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&op,&l,&r);
            if(r<l){
                swap(l,r);
            }            
            if(op==0){
                update(1,l,r);
            }
            else{
                printf("%lld
",query(1,l,r));
            }
        }
        printf("
");
    }
    return 0; 
}

View Code

dfs序+线段树

传送门

题目大意,就是说有一颗树，如果把他的父节点改为一个树，那么他的子节点也会跟着变，为你某一个节点的数

就是先对这个树求一个dfs序，然后就是线段树的区间修改，和单点查询了

#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
const int maxn=1e6+100;
typedef long long ll;
template <typename Tp>
void read(Tp &x){//read(n);
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')){
        ch=getchar();
    }
    if(ch=='-'){
        fh=-1;ch=getchar();
    }else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    x*=fh;
}
inline char read1()//字符串读入挂
{
    register char ch=getchar();
    while(ch<'A'||ch>'M')ch=getchar();
    return ch;
}
struct node{
    int l,r;
    int val;
}t[maxn]; 
struct tu{
    int next;
    int to;
}edge[maxn];
int head[maxn],cnt;
int index=0;
int s[maxn],e[maxn];
bool vis[maxn];
void add(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int u){
    s[u]=++index;
    for(int i=head[u];~i;i=edge[i].next){
        int v=edge[i].to;
        dfs(v);
    }
    e[u]=index;
}
void jianshu(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].val=-1;
    if(l==r){
        return ;
    }
    int mid=(t[p].l+t[p].r)/2;
    jianshu(2*p,l,mid);
    jianshu(2*p+1,mid+1,r);
}
void push_up(int p){
    if(t[p].val>=0){
        t[2*p].val=t[p].val;
        t[2*p+1].val=t[p].val;
        t[p].val=-1;
    }
}
void update(int p,int l,int r,int k){
    if(l<=t[p].l&&t[p].r<=r){
        t[p].val=k;
        return ;
    }
    push_up(p); 
    if(l<=t[2*p].r){
        update(2*p,l,r,k);
    }
    if(r>=t[2*p+1].l){
        update(2*p+1,l,r,k);
    }
//    if(r<=t[2*p].r){
//        update(2*p,l,r,k);
//    } 
//    else if(l>=t[2*p+1].l){
//        update(2*p+1,l,r,k);
//    }
//    else{
//        update(2*p,l,r,k);
//        update(2*p+1,l,r,k);
//    }
}
int query(int p,int x){
    if(t[p].l==t[p].r){
        return t[p].val;
    }
    push_up(p);
    if(x<=t[2*p].r){
        return query(2*p,x);
    } 
    else{
        return query(2*p+1,x);
    }
}
int main(){
    int t;
    cin>>t;
    int kase=0;
    while(t--){
        memset(head,-1,sizeof(head));
        memset(vis,false,sizeof vis);
        cnt=0;
        index=0;
        int n;
        cin>>n;
        int u,v;
        for(int i=1;i<=n-1;i++){
            scanf("%d%d",&u,&v);//v是父节点 
            add(v,u);
            vis[u]=true;
        }
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                dfs(i);
                break;
            }
        }
        jianshu(1,1,n); 
        char str[10];
        int x,k; 
        int m;
        read(m);
        printf("Case #%d:
",++kase);
        for(int i=1;i<=m;i++){
            scanf("%s",str);
            if(str[0]=='C'){
                scanf("%d",&x);
                int ans=query(1,s[x]);
                printf("%d
",ans); 
            }
            else if(str[0]=='T'){
                scanf("%d%d",&x,&k);
                update(1,s[x],e[x],k);
            }
        }
        
    }
}

View Code

二分+线段树

传送门

参考博客

有两个操作

1。选择一个瓶子A，遍历A到n-1（下标是从0开始的）如果遇到瓶子就放一朵花，只到花放完或者没有瓶子了。让你输出放花的

开始和结束位置，如果没有放花就是出一行字母

2.就是把A-B中的花都丢弃

这个题目很巧妙，就是线段树中的sum维护的区间内空瓶子的数量，在一个区间内他是单调的，所以可以二分找这个位置

而这个懒惰标记有三种状态就是-1(初始状态），

1标记为1时（把区间内的都清空）因为是t[2*p].sum=(t[2*p].r-t[2*p].l+1)*t[p].flag就都变空了，就是空瓶子为区间长度

2.标记为0时（区间内的都放满）因为是t[2*p].sum=(t[2*p].r-t[2*p].l+1)*t[p].flag就都变满了，就是区间内的空瓶子为0

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
int n,m;
struct node{
    int l;
    int r;
    int sum;//区间内空瓶的数量 
    int flag;//如果是-1就是初始状态，不能下传， 
}t[maxn];
/*
1.标记为1时（把区间内的都清空）因为是t[2*p].sum=(t[2*p].r-t[2*p].l+1)*t[p].flag就都变空了，
就是空瓶子为区间长度

2.标记为0时（区间内的都放满）因为是t[2*p].sum=(t[2*p].r-t[2*p].l+1)*t[p].flag就都变满了，
就是区间内的空瓶子为0
*/ 
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    t[p].flag=-1;
    if(l==r){
        t[p].sum=1;
        return ;
    }
    int mid=(t[p].l+t[p].r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
void push_up(int p){
    if(t[p].flag!=-1){
        t[2*p].flag=t[2*p+1].flag=t[p].flag;
        
        t[2*p].sum=(t[2*p].r-t[2*p].l+1)*t[p].flag;
        t[2*p+1].sum=(t[2*p+1].r-t[2*p+1].l+1)*t[p].flag;
        t[p].flag=-1;
    }
}
void update(int p,int l,int r,int k){//区间修改 
    int L=t[p].l,R=t[p].r;
    if(l<=L&&r>=R){
        t[p].sum=(R-L+1)*k;
        t[p].flag=k;
        return ;
    }
    push_up(p);
    if(l<=t[2*p].r){
        update(2*p,l,r,k);    
    } 
    if(r>=t[2*p+1].l){
        update(2*p+1,l,r,k);
    } 
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
} 
int query(int p,int l,int r){
    int L=t[p].l,R=t[p].r;
    if(l<=L&&r>=R){
        return t[p].sum;
    }
    push_up(p);
    int ans=0;
    if(l<=t[2*p].r){
        ans+=query(2*p,l,r);    
    } 
    if(r>=t[2*p+1].l){
        ans+=query(2*p+1,l,r);
    }  
    return ans;
}
int dive(int x,int num){//开始位置和要插花的个数 
    int l=x,r=n;//区间内空瓶子的数量是单调的 
    int ans;//所以能二分 
    while(l<=r){
        int mid=(l+r)/2;
        if(query(1,x,mid)>=num){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return ans; 
}
int main(){
    int kase;
    cin>>kase;
    while(kase--){
        scanf("%d%d",&n,&m);
        int op,l,r;
        build(1,1,n);
        for(int i=1;i<=m;i++){
            scanf("%d",&op);
            if(op==1){
                int A,F;
                scanf("%d%d",&A,&F);
                A++;//序号加一， 
                int cnt=query(1,A,n);//得到区间[A,n]中空花瓶的个数 
                if(cnt==0){
                    printf("Can not put any one.
");
                }
                else{
                    int L=dive(A,1);//二分左端点(第一个能插花的位置）
                    int R=dive(A,min(F,cnt));
                    update(1,L,R,0);//将区间内的花瓶都装满，把flag=0,下传的时候就把子节点的sum变成0了
                    printf("%d %d
",L-1,R-1); 
                }
            }
            else if(op==2){
                int A,B;
                scanf("%d%d",&A,&B);
                A++;
                B++;
                printf("%d
",B-A+1-query(1,A,B));
                update(1,A,B,1);
            }
        }
        printf("
"); 
    }
     
}

View Code