题解：P8862 「KDOI-03」还原数据

· · 题解

感觉这个题没有青吧，我也能做？

题目

题面

思路

我们发现正着做不好做，前面的定了后面的会顾及不到，所以我们考虑倒着做。

假设现在末尾有一堆操作 1，那么这些操作是可以直接逆回去的，不会对其他的元素有影响。操作完这些之后，就会遇到操作 2。这个时候我们手玩一些小样就会发现最大值一定不可能超过当前操作 2 区间里面的最小值，我们举个例子看看：

3 7 6 4 8

这个区间是被操作 2 操作过后的区间。假设操作 2 的值是 x。那么操作完成后的数组每个值都应该大于等于 x。所以这个 x 肯定不能超过当前区间的最小值，那么这里默认就取最小值，因为这对其他元素和操作是没有影响的。

做法说完了，总结一下这个题就是要做一个区间加减区间查询最小值，那么这个东西线段树做就非常方便。

这题多测记得清空！

代码如下 ::::success[AC code]

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lc x<<1
#define rc x<<1|1
#define mid (l+r>>1)
#define lson lc,l,mid
#define rson rc,mid+1,r

const int N=1e5+10;

struct node{int mi=LLONG_MAX,add=0;}t[N<<2];
int a[N],n,q;

inline void up(int x){t[x].mi=min(t[lc].mi,t[rc].mi);}

inline void down(int x){
    if(!t[x].add) return;
    t[lc].add+=t[x].add,t[lc].mi+=t[x].add;
    t[rc].add+=t[x].add,t[rc].mi+=t[x].add;
    t[x].add=0;
}

inline void build(int x,int l,int r){
    t[x].add=0;
    if(l==r){t[x].mi=a[l];return;}
    build(lson),build(rson);
    up(x);
}

inline void upd(int x,int l,int r,int L,int R,int k){
    if(L<=l&&r<=R){t[x].add+=k,t[x].mi+=k;return;}
    down(x);
    if(L<=mid) upd(lson,L,R,k);
    if(mid<R) upd(rson,L,R,k);
    up(x);
}

inline int query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R) return t[x].mi;
    int res=LLONG_MAX;
    down(x);
    if(L<=mid) res=min(res,query(lson,L,R));
    if(mid<R) res=min(res,query(rson,L,R));
    return res;
}

void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<int> ans;
    vector<array<int,4>> que(q+1);
    for(int i=1;i<=q;i++){
        int op,l,r,x;cin>>op>>l>>r;
        if(op==1) cin>>x,que[i]={op,l,r,x};
        else que[i]={op,l,r};
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=q;i;i--)
        if(que[i][0]==1) upd(1,1,n,que[i][1],que[i][2],-que[i][3]);
        else ans.push_back(query(1,1,n,que[i][1],que[i][2]));
    reverse(ans.begin(),ans.end());
    for(auto x:ans) cout<<x<<' ';
    cout<<endl;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int tc;cin>>tc;
    while(tc--) solve();
}

::::