HDU3015(树状数组+离散)详解版

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long 
using namespace std;
struct node
{
    ll x,h;
}T[100005];
int n,c[100005],c1[100005];
bool cmp(node s1,node s2){
    return s1.x<s2.x;
}
bool cmp1(node s1,node s2){
    return s1.h<s2.h;
}
int lowbit(int x){
    return x&(-x);
}
void insert(int x,int num,int *s)  //s为对应的传递过来的数组 
{
    while(x<=n){
        s[x]+=num;
        x+=lowbit(x);
    }
}
int sum(int x,int *s)
{
    int ans=0;
    while(x){
        ans+=s[x];
        x-=lowbit(x);
    }
    return ans;
} 
int main()
{
   while(~scanf("%d",&n))
   {
    for(int i=1;i<=n;i++)
    scanf("%lld %lld",&T[i].x,&T[i].h);
    sort(T+1,T+n+1,cmp);   //按照从小到大的把x顺序排序 
    int ji=T[1].x;
    T[1].x=1;
    for(int i=2;i<=n;i++)
    {
        if(T[i].x==ji)
            T[i].x=T[i-1].x;
        else{
            ji=T[i].x;
            T[i].x=i;
        }
    } 
    int jilu=T[n].x;             //记录最大的数下边用 
    sort(T+1,T+n+1,cmp1);   //按照高度进行排序 
    ji=T[1].h;
    T[1].h=1; 
    for(int i=2;i<=n;i++)
    {
        if(T[i].h==ji)
            T[i].h=T[i-1].h;
        else{
            ji=T[i].h;
            T[i].h=i;
        }
    }
    ll ans=0;
    sort(T+1,T+n+1,cmp1);  //第三次进行排序
    memset(c,0,sizeof(c)); 
    memset(c1,0,sizeof(c1)); 
    for(int i=1;i<=n;i++)
    {
        insert(T[i].x,T[i].x,c);//记录所有比这个数小的和   //这个是把每个等级的数放到对应的位置上
        insert(T[i].x,1,c1);//记录所有比这个数小的个数 每个点上记为1 
    } 
    //上边的这个for循环处理之后如果是有的数的话对应的点上就有了 
    //然后再对应每个数找出后边 
    int xiao,da;              //xiao 表示比对应的数a 小反之亦然 
    for(int i=1;i<n;i++)
    {
        xiao=sum(T[i].x-1,c1)*T[i].x-sum(T[i].x-1,c);   //找出比这个数小的个数*这个数-比这个数小的所有数之和 
        da=(sum(jilu,c)-sum(T[i].x,c))-(sum(jilu,c1)-sum(T[i].x,c1))*T[i].x;  //找出比这个数大的数的和-这个数 * 比这个数大的个数
        ans+=(xiao+da)*T[i].h;
        insert(T[i].x,-T[i].x,c);  //把这个用过的数从删除
        insert(T[i].x,-1,c1);//把这个数位置上减去1 
    }
    printf("%lld\n",ans);
   }
   return 0;
}