G6002 [GESP202309 六级] 小杨的握手问题 题解

知识点：树状数组、顺序对计数、整数范围。

解题思路

按入场顺序处理学号x，用树状数组查询已出现的学号小于x的人数，加入答案，再插入x。

为什么正确

入场前树状数组恰记录已在教室的人，前缀查询精确计算本次新产生的握手，且每次握手只在后入场时统计。

易错点

学号从0开始，树状数组存储下标需加1；查询严格小于x，答案用long long。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>bit(n+2);
    long long ans=0;
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        for(int j=x;j>0;j-=j&-j)ans+=bit[j];
        for(int j=x+1;j<=n;j+=j&-j)bit[j]++;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。