https://www.luogu.com.cn/problem/P2345
树状数组
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define v first
#define x second
const int N = 200010;
pair<ll,ll> a[N];
//int t[N];
int n;
ll s[N],p[N];
ll mn;//=20010;//边界
int lowbit(int x)
{
return x &(-x) ;
}
void adds(int x)//记录数量sum前缀和
{
for(int i=x;i<=mn;i+=lowbit(i)) s[i]++;
}
void addx(int x,int k)//记录坐标x前缀和
{
for(int i=x;i<=mn;i+=lowbit(i)) p[i]+=k;
}
int asks(int x)
{
int sum=0;
for(int i=x;i>=1;i-=lowbit(i)) sum+=s[i];
return sum;
}
int askx(int x)
{
int place=0;
for(int i=x;i>=1;i-=lowbit(i)) place+=p[i];
return place;
}
int main()
{
cin>>n;
int xx,vv;
for(int i=1;i<=n;i++)
{
cin>>vv>>xx;
a[i].v=vv;
a[i].x=xx;
// a[i]={v,xx};
}
sort(a+1,a+1+n);
ll ans=0;
mn=20010;
for(int i=1;i<=n;i++)
{
ll j=a[i].x;//j为当前牛牛的位置
// cout<<"^^^^^^^^^^^^^^^^"<<endl;
// for(int j=1;j<=6;j++)
// {
// cout<<asks(j)<<" "<<askx(j)<<endl;
// }
// cout<<"-------------------------"<<endl;
ans+=a[i].v*( asks(j-1)*j-askx(j-1)+ askx(mn)-askx(j)- j*(asks(mn)-asks(j)) );
// cout<<asks(j-1)<<" "<<askx(j-1)<<" | "<<askx(mn)-askx(j)<<" "<<asks(mn)-asks(j)<<endl;
// cout<<"声音大小"<<a[i].v<<" 所在位置"<< j<<" 当前答案"<<ans<<endl;
adds(j);
addx(j,a[i].x);
}
cout<<ans<<endl;
return 0;
}
逆序对,快排模板
#include<cstdio>
#include<iostream>
using namespace std;
int n,a[500010],c[500010];
long long ans;
void msort(int b,int e)//归并排序
{
if(b==e) //终止条件
return;
int mid=(b+e)/2;
int i=b,j=mid+1,k=b;
msort(b,mid),msort(mid+1,e);
while(i<=mid&&j<=e)//b~i~mid~j~e
{
if(a[i]<=a[j])
c[k++]=a[i++];
else
{ //每有一个右边的<左边
ans+=mid-i+1;//统计答案
c[k++]=a[j++];//j后移一位
}
//数组C为排好序的数组,我们求逆序对的问题,答案与数组C无关
}
while(i<=mid)
c[k++]=a[i++];
while(j<=e)
c[k++]=a[j++];
for(int l=b;l<=e;l++)
a[l]=c[l];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
msort(1,n);
printf("%lld",ans);
return 0;
}
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define v first //我们是按照v排序的,将first设置为v较方便
#define x second
const int N = 100010;
pair<ll,ll> a[N],c[N];
int n;
long long ans;
void msort(int l,int r)//归并排序
{
if(l==r) //终止条件
return;
int mid=(l+r)/2;
msort(l,mid),msort(mid+1,r);
ll s1=0,s2=0;//左边和右边坐标和
for(int i=l;i<=mid;i++)
s1+=a[i].x;
int ll=l;
for(int i=mid+1;i<=r;i++)//右边,遍历每一位i
{
// x是坐标 v是音量
// ll mid i
// 5 4 7 8 (6) 4 5 7
while(ll<=mid&&a[ll].x<a[i].x)//ll为划分的中点,其左边都小于a[i].y,右边都大于或等于a[i].y
{
s2+=a[ll].x;
s1-=a[ll].x;
ll++;
}
ans+=(1ll*a[i].x*(ll-l) -s2 +s1-1ll*a[i].x*(mid-ll+1))*a[i].v;
}
//接下来开始归并排序
int i=l,j=mid+1,k=l;//
while(i<=mid&&j<=r)//l~i~mid~j~r
{
if(a[i].x<=a[j].x)
c[k++]=a[i++];
else
{ //每有一个右边的<左边
// ans+=mid-i+1;//统计答案
c[k++]=a[j++];//j后移一位
}
//数组C为排好序的数组,
}
while(i<=mid)
c[k++]=a[i++];
while(j<=r)
c[k++]=a[j++];
for(int w=l;w<=r;w++)
a[w]=c[w];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int v,xx;
cin>>v>>xx;
a[i]={v,xx};
}
sort(a+1,a+1+n);
msort(1,n);
printf("%lld",ans);
return 0;
}