3 条题解

  • 1
    @ 2026-1-11 19:03:51

    要硬说的话其实不需要关流也能过,但是懒标记一定要写对。同时注意N的范围,我第一次开小了导致RE

    #include<iostream>
    using namespace std;
    #define lc p<<1
    #define rc p<<1|1
    #define N 200005
    long long arr[N];
    
    struct node
    {
        long long l,r,sum,add;
    }tr[N*4];
    
    void PushUp(int p)
    {
        tr[p].sum=tr[lc].sum+tr[rc].sum;
    }
    
    void PushDown(long long p)
    {
        if(tr[p].add)
        {
            tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1);
            tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1);
            tr[lc].add+=tr[p].add;
            tr[rc].add+=tr[p].add;
            tr[p].add=0;
        }
    }
    
    void Update(long long p,int x,int y,long long k) //区间添加。
    {
        if(x<=tr[p].l&&tr[p].r<=y)
        {
            tr[p].sum+=k*(tr[p].r-tr[p].l+1);
            tr[p].add+=k;
            return ;
        }
        long long m=(tr[p].l+tr[p].r)>>1;
        PushDown(p);
        if(x<=m) Update(lc,x,y,k);
        if(y>m) Update(rc,x,y,k);
        PushUp(p);
    }
    
    long long Query(long long p,long long l,int r)  //查询
    {
        if(l<=tr[p].l&&tr[p].r<=r)
        {
            return tr[p].sum;
        }
        long long m=(tr[p].l+tr[p].r)>>1;
        PushDown(p);
        long long sum=0;
        if(l<=m) sum+=Query(lc,l,r);
        if(r>m) sum+=Query(rc,l,r);
        return sum;
    }
    
    void Build(long long p,long long l,long long r)
    {
        tr[p]={l,r,arr[l],0};
        if(l==r) return ;
        long long m=(l+r)>>1;
        Build(lc,l,m);
        Build(rc,m+1,r);
        PushUp(p);
    }
    
    long long n,m,op,x,y,k;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>arr[i];
        Build(1,1,n);
        while(m--)
        {
            cin>>op;
            switch (op)
            {
                case 1:
                    cin>>x>>y>>k;
                    Update(1,x,y,k);
                    break;
            
                case 2:
                    cin>>x;
                    long long res=Query(1,x,x);
                    cout<<res<<"\n";
                    break;
            }
        }
        return 0;
    }
    
    • 1
      @ 2025-5-11 1:52:29

      线段树的区间修改和单点查询

      这题要关同步流,不然cin过不了

      #include<bits/stdc++.h>
      using namespace std;
      const int N=2e5+9;
      #define int long long
      int n,a[N],m,x,l,r,op;
      struct t{
          int l,r,data,add;//注意懒标记的使用
      }tree[4*N];
      
      void pushup(int k){//向上更新
        
      tree[k].data=tree[2*k].data+tree[2*k+1].data;
      }
      void update(int k){//向下更新,传递懒标记
          if(!tree[k].add) return;
          tree[2*k].data+=(tree[2*k].r-tree[2*k].l+1)*tree[k].add;
          tree[2*k+1].data+=(tree[2*k+1].r-tree[2*k+1].l+1)*tree[k].add;
          tree[2*k].add+=tree[k].add;
          tree[2*k+1].add+=tree[k].add;
          tree[k].add=0;
      }
      void change(int k,int l,int r,int x){
          if(l<=tree[k].l&&tree[k].r<=r){
              tree[k].data+=(tree[k].r-tree[k].l+1)*x;
              tree[k].add+=x;
              return;
          }
          update(k);
          int mid=(tree[k].l+tree[k].r)>>1;
          if(l<=mid) change(2*k,l,r,x);
          if(r>mid) change(2*k+1,l,r,x);
          pushup(k);
      }
      int query(int k,int idx){
          if(tree[k].l==tree[k].r) return tree[k].data;
          update(k);
          int mid=(tree[k].l+tree[k].r)>>1;
          return (idx<=mid) ? query(2*k,idx) : query(2*k+1,idx);
      }
      void build(int k,int l,int r){
          tree[k]={l,r,a[l],0};
          if(l==r) return;
          int mid=(l+r)>>1;
          build(2*k,l,mid);
          build(2*k+1,mid+1,r);
          pushup(k);
      }
      signed main(){
          ios::sync_with_stdio(false); cin.tie(0);
          cin>>n>>m;
          for(int i=1;i<=n;i++) cin>>a[i];
          build(1,1,n);
          while(m--){
              cin>>op;
              if(op==1){
                  cin>>l>>r>>x;
                  change(1,l,r,x);
              }else{
                  cin>>x;
                  cout<<query(1,x)<<'\n';
              }
          }
          return 0;
      }
      
      • 0
        @ 2026-6-3 14:42:09
        #include<bits/stdc++.h>
        using namespace std;
        using ll=long long;
        const int N=5e5+10;
        int a[N],c[N];
        int n,m;
        int lowbit(int x){
            return x&-x;
        }
        void update(int x,int val){
            for(int i=x;i<=n;i+=lowbit(i)){
                c[i]+=val;
            }
        }
        ll sum(int x){
            ll ans=0;
            for(int i=x;i;i-=lowbit(i)){
                ans+=c[i];
            }
            return ans;
        }
        int main()
        {
            cin>>n>>m;
            for(int i=1;i<=n;i++){
                cin>>a[i];
                update(i,a[i]-a[i-1]);
            }
            while(m--){
                int op;
                cin>>op;
                if(op==1){
                    int x,y,k;
                    cin>>x>>y>>k;
                    update(x,k);
                    update(y+1,-k);
                }else{
                    int x;
                    cin>>x;
                    cout<<sum(x)<<endl;
                }
            }
        }
        
        • 1

        信息

        ID
        58
        时间
        1000ms
        内存
        256MiB
        难度
        普及
        标签
        递交数
        181
        已通过
        54
        上传者