1 solutions
-
1
线段树好题。
问题可以建模为区间加与区间求和,此时问题简化为在区间 加上一个数,再在区间 加上一个数,查询区间 的和。可以使用线段树维护区间加与区间求和操作。#include <bits/stdc++.h> using namespace std; const int N=1e5+5; int t[N<<2],tag[N<<2]; inline int lc(int u){return u<<1;}; inline int rc(int u){return u<<1|1;}; inline void pushup(int u){t[u]=t[lc(u)]+t[rc(u)];} void pushdown(int u,int l,int r){ if(!tag[u]) return; int mid=(l+r)>>1; t[lc(u)]+=tag[u]*(mid-l+1); t[rc(u)]+=tag[u]*(r-mid); tag[lc(u)]+=tag[u]; tag[rc(u)]+=tag[u]; tag[u]=0; } void update(int u,int l,int r,int x,int y,int k){ if(r<x || l>y) return; if(l>=x && r<=y){ t[u]+=k*(r-l+1); tag[u]+=k; return; } pushdown(u,l,r); int mid=(l+r)>>1; update(lc(u),l,mid,x,y,k); update(rc(u),mid+1,r,x,y,k); pushup(u); } int query(int u,int l,int r,int x,int y){ if(r<x || l>y) return 0; if(l>=x && r<=y) return t[u]; pushdown(u,l,r); int mid=(l+r)>>1; return query(lc(u),l,mid,x,y)+query(rc(u),mid+1,r,x,y); } int super_fast_read(){ int x; cin>>x; return x; } void super_fast_write(int x,int k){ if(x==0){ if(k==1) cout<<0; return; } super_fast_write(x/10,k+1); if(k%3==0 && x/10!=0) cout<<','; cout<<x%10; } int main(){ int a=super_fast_read(); int b=super_fast_read(); update(1,1,N-1,1,1,a); update(1,1,N-1,1,1,b); int ans=query(1,1,N-1,1,2); super_fast_write(ans,1); return 0; }
- 1
Information
- ID
- 360
- Time
- 1000ms
- Memory
- 64MiB
- Difficulty
- 10
- Tags
- # Submissions
- 1
- Accepted
- 1
- Uploaded By