P1774

在这道题里，树状数组的做法是离散化以后对每一个 $i=1,2,...n$ 查询比它大的数。

但是为什么模板求前缀和的树状数组查询 $query$ 能直接套在里面？如题解的下面两种写法

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define IV inline void
#define II inline int
#define A printf("A")
using namespace std;
const int N=5e5+2;int c[N],a[N],b[N],n;ll ans;
bool cmp(int x,int y){return a[x]<a[y];}
IV add(int x){while(x<=n){++c[x],x+=(x&-x);};return;}
II ask(int x){int s=0;while(x){s+=c[x],x-=(x&-x);};return s;}
int main(){
    scanf("%d",&n);
    for(RI i=1;i<=n;++i){scanf("%d",&a[i]);b[i]=i;}
    stable_sort(b+1,b+n+1,cmp);
    for(RI i=1;i<=n;++i)a[b[i]]=i; 
    for(RI i=n;i>=1;--i){ans+=ask(a[i]-1);add(a[i]);}
    printf("%lld\n",ans); 
    return 0;
} 

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,a[maxn],p[maxn],tree[maxn]; //tree为树状数组
long long ans=0;
bool cmp(int x,int y) //离散化快排
{
  return a[x]<a[y];
}
int lowbit(int x)
{
  return x&(-x);
}
void update(int x,int d)
{
  while(x<=n)
  {
    tree[x]+=d;
    x+=lowbit(x);
  }
}
long long query(int x)
{
  long long ret=0;
  while(x>0)
  {
    ret+=tree[x];
    x-=lowbit(x);
  }
  return ret;
}
int main()
{ //本题数据量过大，需要离散化处理
  scanf("%d",&n);
  for(int i=1; i<=n; i++) 
  {
    scanf("%d",&a[i]);
    p[i]=i; //p记录节点编号
  } //很多人20分就是因为这里，尽量用stable_sort，不改变原序列中的元素位置（当两元素相等时）
  stable_sort(p+1,p+n+1,cmp);
  for(int i=1; i<=n; i++) a[p[i]]=i; //离散化
  for(int i=n; i>=1; i--) //倒序循环
  {
    ans+=query(a[i]-1); //查询比自己小且在自己后面的数有几个
    update(a[i],1); //值为a[i]的数的个数+1
  }
  printf("%lld\n",ans); //同样，别往long long
  return 0;
}