2 条题解

  • 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;
      }
      
      • 1

      信息

      ID
      58
      时间
      1000ms
      内存
      256MiB
      难度
      4
      标签
      递交数
      87
      已通过
      25
      上传者