Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

树状数组区间更新区间查询

Posted by 770605294 at 2017-03-20 23:32:05 on Problem 3468
#include<stdio.h>
#define ll long long
ll l,r,v,n,m,c1[100010],c2[100010];char s[2];
void add(ll k,ll val){for (ll i=k;i<=n;i+=i&(-i))c1[i]+=val,c2[i]+=k*val;}
ll get(ll k){ll sum=0;for (ll i=k;i;i-=i&(-i))sum+=(k+1)*c1[i]-c2[i];return sum;}
int main(){scanf("%lld%lld",&n,&m);for (ll i=1;i<=n;add(i,v),add(i+1,-v),i++)scanf("%lld",&v);for (ll i=1;i<=m;i++){scanf("%s %lld%lld",&s,&l,&r);if (s[0]=='C')scanf("%lld",&v),add(l,v),add(r+1,-v);else printf("%lld\n",get(r)-get(l-1));}}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator