【普通线段树+小小剪枝优化】CF849div4 F

喜欢ヅ旅行 2024-03-27 13:17 89阅读 0赞

[Problem - F - Codeforces][]

**太久太久没写线段树了，昨天 的F直接搬板子，调了半天也没调出来，今天写了一下也是t了很多发才过，感觉线段树还是手写一下比较好，今天去把洛谷官方题单的线段树给写了吧**

题意：

给定一个序列，有两种命令:

当op=1时 把区间\[l,r\]的所有数修改成该数的数位和

当op=2时 查询a\[x\]

思路：

线段树模板题，单点查询单点修改

值得注意的是，这题有一些可能会t的坑

它范围是1e9，说明如果区间加会爆int，所以可能会define int long long

但是define之后就会t

所以可以维护区间最大值，这样就不会爆int，也就不需要define了

或者手写开long long

还有一个就是剪枝，当值小于9时可以不需要修改了

Code：

#include <bits/stdc++.h>
    //#define int long long
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int Inf=-0x3f3f3f3f;
    using namespace std;
    struct Tree{
        int val;
    }tree[mxe<<2];
    int n,q,op,l,r,x;
    int a[mxn];
    int calc(int x){
        int t=x,res=0;
        while(t){
            res+=t%10;
            t/=10;
        }
        return res;
    }
    void pushup(int p,Tree *tree){
        tree[p].val=max(tree[p<<1].val,tree[p<<1|1].val);
    }
    int query(int p,int l,int r,int x,Tree *tree){
        if(l==r&&l==x){
            return tree[p].val;
        }
        int mid=l+r>>1;
        if(x<=mid) return query(p<<1,l,mid,x,tree);
        return query(p<<1|1,mid+1,r,x,tree);
    }
    void modify(int p,int l,int r,int x,int y,Tree *tree){
        if(tree[p].val<=9) return;
        if(l==r&&x<=l&&l<=y){
            tree[p].val=calc(tree[p].val);
            return;
        }
        int mid=l+r>>1;
        if(x<=mid) modify(p<<1,l,mid,x,y,tree);
        if(y>mid) modify(p<<1|1,mid+1,r,x,y,tree);
        pushup(p,tree);
    }
    void build(int p,int l,int r,Tree *tree){
        tree[p].val=0;
        if(l==r){
            tree[p].val=a[l];
            return;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid,tree);
        build(p<<1|1,mid+1,r,tree);
        pushup(p,tree);
    }
    void solve(){
        cin>>n>>q;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n,tree);
        while(q--){
            cin>>op;
            if(op==1){
                cin>>l>>r;
                modify(1,1,n,l,r,tree);
            }else{
                cin>>x;
                cout<<query(1,1,n,x,tree)<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1791/problem/F