小w与面试

发表于 |
字数统计: 270 | 阅读时长 ≈ 1
  • Code Level: ※
  • Thinking Level: ※※

Description

给定一个长度为 n 的序列 a，求

Solution

按位计算贡献
当前值ai能对答案造成的贡献为其每一位能造成的贡献之和

  1. 若此位为0，则贡献即为ai之前此位为1的值
  2. 若此位为1，则贡献即为ai之前此位为0的值

用树状数组来维护

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Mx=1e5+5;
int N,A[Mx];ll Ans=0,Tr[22][2][Mx];
void D(int j,int p,int x){for(int i=x;i<Mx;i+=i&-i)Tr[j][p][i]++;}
ll S(int j,int p,int x){ll s=0;for(int i=x;i;i-=i&-i)s+=Tr[j][p][i];return s;}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&A[i]);
    for(int i=N;i>0;i--)
    for(int j=0;j<=20;j++)
    if((1<<j)&A[i]) Ans+=(1<<j)*S(j,0,A[i]-1),D(j,1,A[i]);
    else Ans+=(1<<j)*S(j,1,A[i]-1),D(j,0,A[i]);
    cout<<Ans<<endl;
    return 0;
}