线段树专题 POJ3468 A Simple Problem with Integers
with 专题 线段 Problem Simple Integers
2023-09-11 14:14:43 时间
题意:n个点。m个操作。两种操作类型。C X Y K 表示区间[x,y]上每一个点值加k。Q X Y 求区间[x,y]的和
分析:线段树区间求和,裸模板
注意:结果会超int,要用long long 表示,假设是在hust上交结果要用%I64d。poj的话则用%lld
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include<vector> #pragma comment(linker,"/STACK:1024000000,1024000000") using namespace std; const int maxn = 1e5+5; long long sum[maxn*4]; long long lazy[maxn*4]; int num[maxn]; void up(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void down(int l,int r,int rt){ if(!lazy[rt]) return; int mid=(l+r)/2; lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; sum[rt<<1]+=lazy[rt]*(mid-l+1); sum[rt<<1|1]+=lazy[rt]*(r-mid); lazy[rt]=0; } void build(int l,int r,int rt){ lazy[rt]=sum[rt]=0; if(l==r){ sum[rt]=num[l]; return; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); up(rt); } void update(int L,int R,int k,int l,int r,int rt){ if(L<=l&&r<=R){ lazy[rt]+=k; sum[rt]+=(r-l+1)*k; return; } down(l,r,rt); int mid=(l+r)>>1; if(L<=mid) update(L,R,k,l,mid,rt<<1); if(R>mid) update(L,R,k,mid+1,r,rt<<1|1); up(rt); } long long query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) return sum[rt]; down(l,r,rt); int mid=(l+r)>>1; long long ret = 0; if(L<=mid) ret+=query(L,R,l,mid,rt<<1); if(R>mid) ret+=query(L,R,mid+1,r,rt<<1|1); up(rt); return ret; } int main() { int n,q; while(scanf("%d%d",&n,&q)!=EOF){ for(int i=1;i<=n;i++) scanf("%d",&num[i]); build(1,n,1); while(q--){ char c; int x,y,k; scanf(" %c",&c); if(c=='C'){ scanf("%d%d%d",&x,&y,&k); update(x,y,k,1,n,1); } else{ scanf("%d%d",&x,&y); printf("%lld\n",query(x,y,1,n,1)); } } } }
相关文章
- Cause: com.mysql.jdbc.exceptions.jdbc4.MySQLSyntaxErrorException: ..... this is incompatible with sql_mode=only_full_group_by
- [Unit testing RxJS] Test error handling with marbles
- [Unit testing] Simplify Assertions on Error Messages with toMatchInlineSnapshot
- [Functional Programming] Match Function Requirements with Lodash Partial and Flip
- [Webpack] Analyze a Production JavaScript Bundle with webpack-bundle-analyzer
- [Python] Indexing An Array With Another Array with numpy
- hudson.AbortException: No files found in path D:testprojectproject2testoutput with configured filemask: output.xml
- [React Testing] Test your Custom Hook Module with react-hooks-testing-library
- [React Router v4] Use Regular Expressions with Routes
- [Ramda] Handle Errors in Ramda Pipelines with tryCatch
- [Angular 2] Set Values on Generated Angular 2 Templates with Template Context
- How to Install GVM Trial With VMware Workstation Player/Pro
- 【46】报错Mask is not defined for output layer with width ‘52‘. Define at pipeline build time using:‘ se
- 问题解决之-This system is not registered with RHN终极解决办法以及yum卸载后重装解决方法