线段树50分求调,样例二输出10

P1253 扶苏的问题

jntm233 @ 2024-04-23 20:40:26


#include<bits/stdc++.h>
using namespace std;
//#define x first
#define y second
#define no cout<<"NO\n";
#define yes cout<<"YES\n";
#define A cout<<"Alice\n";
#define B cout<<"Bob\n";
#define cll(x) cout<<(x)<<endl;
#define ccl(x) cout<<(x)<<" ";
#define range(a) (a).begin(),(a).end()
#define fall(a) for(auto i:(a))cout<<i<<" ";cout<<"\n";
#define homo 1145141919810
#define vec vector
#define que queue
#define deq deque
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define _max *max_element
#define _min *min_element
#define man int main()
#define whatcanisay ll t;cin>>t;while(t--)solve();
#define manbaout return 0;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lep(i,a,b) for(int i=(a);i>=(b);i--)
using ll=long long;
using ld=long double;
using plst=pair<ll,string>;
using pll=pair<ll,ll>;
ll n,m;
//ll fa[114514];
//ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
//ll lcm(ll a,ll b){return a*b/gcd(a,b);}
//ll find(ll x){return x==fa[x]?x:fa[x]=find(fa[x]);}
//ll dp[1919810];
const int N=1000001;
const int inf=1e9;
const ll mod=998244353;
//ll vis[214514];
ll a[N],vis[N];
struct node{
    ll l,r;
    ll maxv;
    ll sum,tag;//求和与懒标记
}tree[N<<2];
inline void push_up(ll id){
    tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
    tree[id].maxv=max(tree[id<<1].maxv,tree[id<<1|1].maxv);
}
inline void push_add(ll id,ll k){
    tree[id].sum+=k*(tree[id].r-tree[id].l+1);
    tree[id].maxv+=k;
    tree[id].tag+=k;
}
inline void build(ll id,ll l,ll r){
    tree[id].l=l,tree[id].r=r,tree[id].tag=0;
//  tree[id].cnt=r-l+1;
    if(l==r){
        tree[id].sum=a[l];
        tree[id].maxv=a[l];
//      tree[id].cnt=vis[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    push_up(id);
//  tree[id].cnt=tree[id<<1].cnt+tree[id<<1|1].cnt;
}
inline void push_down(ll id){//向下传递懒标记
    if(!tree[id].tag)return;
    push_add(id<<1,tree[id].tag);
    push_add(id<<1|1,tree[id].tag);
    tree[id].tag=0;
}
inline void update(ll id,ll l,ll r,ll x){
    //区间修改
    if(tree[id].l>=l&&tree[id].r<=r)return push_add(id,x);
    ll mid=tree[id].l+tree[id].r>>1;
    push_down(id);
    if(l<=mid)update(id<<1,l,r,x);
    if(r>mid)update(id<<1|1,l,r,x);
    push_up(id);
}
//ll ans=0;
ll query(ll id,ll l,ll r){
    //  ll ans=0;
    if(l<=tree[id].l&&tree[id].r<=r)return tree[id].maxv;
    ll mid=(tree[id].l+tree[id].r)>>1,ans=-LONG_LONG_MAX;
    push_down(id);
    if(l<=mid)ans=max(query(id<<1,l,r),ans);
    if(r>mid)ans=max(query(id<<1|1,l,r),ans);//修改的全部在右
    return ans;
}
inline void change(ll id,ll l,ll r,ll x){
    if(l<=tree[id].l&&tree[id].r<=r){
        tree[id].maxv=x;
//      push_down(id);
//      push_up(id);
        return push_down(id);
    }
    ll mid=tree[id].l+tree[id].r>>1;
    push_down(id);
    if(l<=mid)change(id<<1,l,r,x);
    if(r>mid)change(id<<1|1,l,r,x);
    push_up(id);
}
void solve(){
    cin>>n>>m;
    rep(i,1,n)cin>>a[i];
//  rep(i,1,n)cin>>vis[i];
    build(1,1,n);
    while(m--){
        ll op;cin>>op;
        if(op==2){
            ll l,r,x;cin>>l>>r>>x;
            update(1,l,r,x);
        }else if(op==3){
            ll l,r;cin>>l>>r;
            cll(query(1,l,r))
        }else{
            ll l,r,x;cin>>l>>r>>x;
            change(1,l,r,x);
        }
    }

}

man{ 

    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    //  whatcanisay manbaout
}```

by WindDance @ 2024-04-29 00:21:46

操作1有可能改为0,标记初始化为一个别的值,判空的时候判那个值,不能直接判0


|