题解：P10516 数据结构

chenyizhen · 2025-08-26 20:58:49 · 题解

题意：

实现区间修改，单点加 val，以及区间查询 sum。

思路：

很明显，对于区间操作，我们选择线段树，具体记录数据如下：

struct segment{
    int l,r;
    //区间左右端点l,r
    int sum,minn;
    //区间和sum，区间最小值minn    
}t[N<<2];

• 对于操作 1，我们要记录区间区间 \min，通过与 k 进行比较判断该区间是否进行修改（特判一下如果 val 值为零就跳过，没必要进行无意的计算）。
• 对于操作 2，只需要找到对应的位置进行修改。
• 对于操作 3，计算统计好的区间 sum。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
inline void read(int &a){
    char ch;int f=1,k=0;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
    a=k*f;
}

struct segment{
    int l,r;
    int sum,minn;
}t[N<<2];

int a[N],b[N],n,m;

void push_up(int p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
    t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn);
}
//建树 
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].minn=a[l]*b[l];
        t[p].sum=a[l]+b[l];
        return ;
    }
    int mid=l+r >>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    push_up(p);
}
//op==1
void modify(int p,int l,int r,int k,int val){
    if(t[p].minn>k) return ;
    if(t[p].l==t[p].r){
        a[t[p].l]+=val,b[t[p].l]+=val;
        t[p].sum=a[t[p].l]+b[t[p].l];
        t[p].minn=a[t[p].l]*b[t[p].l];
        return ;
    }
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) modify(p<<1,l,r,k,val);
    if(r>=mid+1) modify(p<<1|1,l,r,k,val);
    push_up(p);
}

//op==2
void update(int p,int i,int x,int y){
    if(t[p].l==t[p].r){
        a[i]=x,b[i]=y;
        t[p].minn=x*y;
        t[p].sum=x+y;
        return ;
    }
    int mid=t[p].l+t[p].r>>1;
    if(i<=mid) update(p<<1,i,x,y);
    else if(i>=mid+1) update(p<<1|1,i,x,y);
    push_up(p);
}
//op==3
int query(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].sum;
    }
    int mid=t[p].l+t[p].r>>1,res=0;
    if(l<=mid) res+=query(p<<1,l,r);
    if(r>=mid+1) res+=query(p<<1|1,l,r);
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    read(n),read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
    int op;
    build(1,1,n);
    while(m--){
        read(op);
        if(op==1){
            int l,r,k,t;
            read(l),read(r),read(k),read(t);
            if(!t) continue;
            modify(1,l,r,k,t);
        }
        else if(op==2){
            int i,x,y;
            read(i),read(x),read(y);
            update(1,i,x,y);
        }
        else if(op==3){
            int l,r;
            read(l),read(r);
            cout<<query(1,l,r)<<"\n";
        }
    } 
    return 0;
}