145 条题解
-
-35
用线段树+标记永久化即可
#include <cstdio> #define mid L + (R-L >> 1) const int maxn = 1e5+5; int n, a[maxn], m; int sl, sr, add; struct segtree{ int sum[maxn<<2], tag[maxn<<2]; inline int lc(int o){return o<<1;} inline int rc(int o){return o<<1|1;} void build(int o, int L, int R){ if(L == R){sum[o] = a[L];return;} int M = mid; build(lc(o), L, M); build(rc(o), M+1, R); sum[o] = sum[lc(o)] + sum[rc(o)]; } void maintain(int o, int L, int R){ if(R>L){ sum[o] = sum[lc(o)] + sum[rc(o)]; sum[o] += tag[o] * (R-L+1); } else { sum[o] += tag[o]; tag[o] = 0; } } void updata(int o, int L, int R){ if(sl <= L && R <= sr)tag[o] += add; else{ int M = mid; if(sl <= M)updata(lc(o), L, M); if(sr > M)updata(rc(o), M+1, R); } maintain(o, L, R); } int query(int o, int L, int R, int tags){ if(sl <= L && R <= sr)return sum[o] + tags * (R-L+1); else { int M = mid, res = 0; if(sl <= M)res += query(lc(o), L, M, tags+tag[o]); if(sr > M)res += query(rc(o), M+1, R, tags+tag[o]); return res; } } } sol; signed main(){ n = 1; int a, b; scanf("%d%d", &a, &b); sol.build(1, 1, n); add=a; sl=1; sr=1; sol.updata(1, 1, 1); add=b; sol.updata(1, 1, 1); printf("%d\n", sol.query(1, 1, n, 0)); return 0; }
当然,树状数组也可以,并且更快
#include <iostream> using namespace std; const int n = 1; int a, b; int c[500005]; inline int lowbit(int x){ return x & (-x); } inline int sum(int x){ int ans=0; for(int i=x;i>0;i-=lowbit(i)) ans+=c[i]; return ans; } void add(int x,int y){ for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y; } int main(){ cin>>a>>b; add(1, a); add(1, b); printf("%d\n", sum(1)); return 0; }
信息
- ID
- 56
- 时间
- 1000ms
- 内存
- 1024MiB
- 难度
- 1
- 标签
- 递交数
- 9038
- 已通过
- 4026
- 上传者