atcoder beginner 331C - Sum of Numbers Greater Than Me (atcoder.jp)这道题求后缀和,差不多是后缀和吧,然后佬用我没写过的一种树状数组直接秒掉,不服不行膜拜学习
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e6+10; int n,sum; int a[maxn],c[maxn]; int lbt(int x) { return x&(-x); } void add(int x,int y) { for(int i=x;i<=1e6;i+=lbt(i)) c[i]+=y; } int query(int x) { int res=0; for(int i=x;i;i-=lbt(i)) res+=c[i]; return res; } signed main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i],add(a[i],a[i]),sum+=a[i]; for(int i=1;i<=n;i++) cout<<sum-query(a[i])<<' '; }