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
ACM ICPC 2018 World Finals

树状数组AC

Posted by 770605294 at 2017-03-20 23:29:48 on Problem 3468
In Reply To:挑战上线段树AC Posted by:MrYX at 2017-03-14 19:28:38
#include<stdio.h>
#define ll long long
ll l,r,v,n,m,c1[100010],c2[100010];
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);
    char s[2];
    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