P10516 数据结构 题解

· · 题解

数据结构题解

以下假定 n,m,V 同阶。

势能线段树。注意到若无二操作，有效一操作至多会进行 O(\sqrt n) 次，也就是可以对每个位置暴力修改。对于线段树上每个区间记录区间最小值，若当前区间最小值不大于 k 则对其子树递归修改。直到找到每个单点，暴力修改即可。

二操作单点修改总共只会更新至多 O(n) 个数，给一操作的总修改数增加 O(n\sqrt n) 次，时间复杂度是正确的。

区间和用单点修改线段树的写法即可。

注意要特判 t=0 的情况。

一操作至多进行 O(n\sqrt n) 次单点修改，总时间复杂度为 O(n\sqrt n\log n)，实际达不到上界。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<ctime>
#include<random>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=1e5+10;
int n,m,a[N],b[N];
struct Tree{
    #define ls (p<<1)
    #define rs (p<<1|1)
    #define mid ((l+r)>>1)
    int sum[N<<2],minn[N<<2];
    inline void pushup(int p){
        sum[p]=sum[ls]+sum[rs];
        minn[p]=min(minn[ls],minn[rs]);
    }
    void build(int p,int l,int r){
        if(l==r){
            sum[p]=a[l]+b[l];
            minn[p]=a[l]*b[l];
            return;
        }
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }
    void update(int L,int R,int p,int l,int r,int k,int t){
        if(minn[p]>k)return;
        if(l==r){
            a[l]+=t;
            b[l]+=t;
            sum[p]=a[l]+b[l];
            minn[p]=a[l]*b[l];
            return;
        }
        if(L<=mid)update(L,R,ls,l,mid,k,t);
        if(R>mid) update(L,R,rs,mid+1,r,k,t);
        pushup(p);
    }
    void modify(int pos,int p,int l,int r,int x,int y){
        if(l==r){
            a[pos]=x;
            b[pos]=y;
            sum[p]=a[l]+b[l];
            minn[p]=a[l]*b[l];
            return;
        }
        if(pos<=mid)modify(pos,ls,l,mid,x,y);
        if(pos>mid) modify(pos,rs,mid+1,r,x,y);
        pushup(p);
    }
    int query(int L,int R,int p,int l,int r){
        if(L<=l&&r<=R)
            return sum[p];
        int res=0;
        if(L<=mid)res+=query(L,R,ls,l,mid);
        if(R>mid) res+=query(L,R,rs,mid+1,r);
        return res;
    }
    #undef ls
    #undef rs
    #undef mid
}T;
signed main()
{
    //freopen("020.in","r",stdin);
    //freopen("020.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
        b[i]=read();
    T.build(1,1,n);
    while(m--){
        int opt=read();
        if(opt==1){
            int l=read(),r=read(),k=read(),t=read();
            if(!t)continue;
            T.update(l,r,1,1,n,k,t);
        }
        if(opt==2){
            int pos=read(),x=read(),y=read();
            T.modify(pos,1,1,n,x,y);
        }
        if(opt==3){
            int l=read(),r=read();
            cout<<T.query(l,r,1,1,n)<<'\n';
        }
    }
    return 0;
}