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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

WA用树状数组 qwq 有大佬帮忙看一下吗

Posted by qqcoder at 2019-12-17 17:58:37 on Problem 3468
#include<cstdio>
#include<iostream>

using namespace std;
const int maxn=1e5+1;
typedef long long ll;

ll N,Q;
ll sum1[maxn],sum2[maxn];
ll a[maxn];
char c;

ll lowbit(ll x){return x&-x;}

void add(ll *arr,ll x,ll c)
{
    while(x<=N)
    {
        arr[x]+=c;
        x+=lowbit(x);
    }
}
ll query(ll *arr,ll x)
{
    ll ans=0;
    while(x)
    {
        ans+=arr[x];
        x-=lowbit(x);
    }
    return ans;
}

int main()
{
    cin>>N>>Q;
    ll x;
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&a[i]);
        //a[i]+=a[i-1];
        add(sum1,i,a[i]-a[i-1]);
        add(sum2,i,i*(a[i]-a[i-1]));
    }
    for(int i=1;i<=Q;i++)
    {
        cin>>c;
        if(c=='Q')
        {
            ll cur=0;
            ll x,y;
            cin>>y>>x;
            //cur=a[y]-a[x-1];
            //cur+=query(b,)
            cur+=(x+1)*query(sum1,x)+query(sum2,y-1);
            cur-=y*query(sum1,y-1)+query(sum2,x);
            cout<<cur<<endl;
        }
        else{
                ll a,b,c;
                cin>>a>>b>>c;
                add(sum1,a,c),add(sum1,b+1,-c);
                add(sum2,a,a*c),add(sum2,b+1,-(b+1)*c);
        }
    }
    return 0;
}

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