2 条题解
-
1
要硬说的话其实不需要关流也能过,但是懒标记一定要写对。同时注意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
线段树的区间修改和单点查询
这题要关同步流,不然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
- 上传者