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大学生程序设计竞赛训练》暑期课面向全球招生!

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

Posted by 1769157748 at 2020-03-31 15:51:29 on Problem 3468
In Reply To:WA用树状数组 qwq 有大佬帮忙看一下吗 Posted by:qqcoder at 2019-12-17 17:58:37
> #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