AcWing 1215. 小朋友排队
原题链接
中等
作者:
无双飞怪
,
2024-04-19 11:47:11
,
所有人可见
,
阅读 2
//前一步动的是i 这一步肯定加到了sum[a[j].y]里(可以这么想:因为分治两个数列肯定都是递增的 只有往后动了指针才能
//让这个数变大)
//下一步动谁sum算到谁的身上(对以下都适用 不管是普通的比a[i]和a[j]的大小还是最下面的收尾-->最后只能i或j移动)
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
PII a[N];
PII tmp[N];
int sum[N];
long long res;
void merge(int l,int r)
{
if(l>=r) return;
int mid=l+r>>1;
merge(l,mid),merge(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j]) //一直移动到a[j]>a[i]才停
{
sum[a[i].y]+=j-mid-1;//这里是因为有等号 所以不能+1 //这里暂有问题 我认为<和<=应该分开判断 但分开又不对
tmp[k++]=a[i++];
}
else //a[i]>a[j] 说明i后面的都比j大 j之前是否比i小我不知道 但i后面的一定比j大 这是确定的 上面的if同理
//注:1~mid和mid+1~r 未必mid+1~r就一定比1~mid大 这两步分治是独立的 不存在任何大小关系 (只有内部的1~mid递增和mid+1~r递增是确定的)
//a[i]<=a[j]的情况完全可以看成是a[i]>a[j]与之交换的结果(前者在后 后者在前)(只排确定的大小关系)
//因为下一步移动的就是j 所以算的是j (此时i完全就是固定的)
{
sum[a[j].y]+=mid-i+1;
tmp[k++]=a[j++];
}
}
while(i<=mid) sum[a[i].y]+=r-(mid+1)+1,tmp[k++]=a[i++];//这里注意不能写sum[a[j].y]+=mid-i+1 虽然i<=mid等价于
//a[i]>a[j]但是不能直接套用sum[a[j].y]+=mid-i+1; 因为这一步的上一步是a[i]>a[j]然后算到了sum[a[j].y]里
// 而且这一步往后j都是固定的 总不能一直加到sum[a[j].y]上吧?(把i~mid中的所有都加到了sum[a[j].y]上 结果会变大)
//可以这么理解:下一步动的是i 所以加到了i上
//再注意:此时j=r+1 所以mid+1~r之间有j-mid-1个数(j-(mid+1)-1+1)
while(j<=r) sum[a[j].y]+=mid-i+1,tmp[k++]=a[j++];
for(int i=l,j=0;i<=r;i++,j++)
a[i]=tmp[j];
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].x,a[i].y=i;
merge(0,n-1);
for(int i=0;i<n;i++) res+=(long long)(1+sum[i])*sum[i]/2;//这一步一定要注意 :强制转换成long long
cout<<res;
return 0;
}