123789456ye @ 2019-05-29 22:30:52
代码如下
#include<bits/stdc++.h>
using namespace std;
#define N 500005
struct num
{
long long id,value;
bool operator < (const num &p) const
{
return value<p.value;
}
}nu[N];
int c[N],n;
long long ans;
int lowbit(int i)
{
return i&(-i);
}
int getsum(int x)
{
int sum=0;
for(int i=x; i; i-=lowbit(i))
sum+=c[i];
return sum;
}
void modify(int x,int delta)
{
for(int i=x; i<=n; i+=lowbit(i))
c[i]+=delta;
}
inline int read()
{
char ch=getchar();
int x=0,f=1;
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("0out.txt","w",stdout);
n=read();
for(int i=1; i<=n; i++)
{
nu[i].value=read();
nu[i].id=i;
}
sort(nu+1,nu+1+n);
for(int i=1;i<=n;i++)
{
modify(nu[i].id,1);
ans+=i-getsum(nu[i].id);
}
printf("%lld\n",ans);
return 0;
}by 123789456ye @ 2019-05-29 22:31:32
打错了，是40分WA
by 灵光一闪 @ 2019-05-29 22:52:23
@123789456ye 我竟不如一个蓝名……，自闭ing……
by 铃宕 @ 2019-05-29 22:53:48
用归并排序不是更 有趣 简单吗
by 铃宕 @ 2019-05-29 22:54:34
看不懂 下一个
by Lone_Star @ 2019-05-29 23:11:32
@123789456ye 每个数字
by 123789456ye @ 2019-05-30 08:24:20
@Flamire 已离散化.数据规模在5*10^5内.
by 归程 @ 2019-06-11 23:14:25
@123789456ye本蒟蒻也用的树状数组，发现一个坑，直接排序有可能会有一部分一样的数据会挂
bool cmp(const P&a,const P&b)
{
if(a.w!=b.w)return a.w<b.w;
else return a.id<b.id;
}//这样是可以的但
bool cmp(const P&a,const P&b)
{return a.w<b.w;}//这样就会wa,正好40分by 樱花飞舞 @ 2019-06-23 19:51:20
@归程 谢谢，我也是这里错的。
出题人真恶心。
by ACCCCC @ 2019-07-04 11:10:16
@归程 为啥呀，我感觉这个不会有啥影响吧。我是先按值排序，再按照原来的位置调过来。
bool cmp1(Node a,Node b){
return a.v<b.v;
}
bool cmp2(Node a,Node b){
return a.pos<b.pos;
}by ACCCCC @ 2019-07-04 11:13:59
@归程 懂了懂了，相同数据确实没处理好