TLE 25分求助!
  • 板块P1908 逆序对
  • 楼主卷王慢即快
  • 当前回复13
  • 已保存回复13
  • 发布时间2022/8/18 18:56
  • 上次更新2023/10/27 14:44:02
查看原帖
TLE 25分求助!
494699
卷王慢即快楼主2022/8/18 18:56

我按深进里的代码思路自己打了一遍,结果只有1~5AC?????

#include<bits/stdc++.h> //哎,dev-c++好像不能正确排序啊! 
using namespace std;
inline int read(); //快读 
#define maxn 500001 //定义数据范围 
int n,a[maxn],w[maxn*4]; //输入变量、输入的数组、权值线段树 
long long ans=0; //逆序对个数 
inline void init()
{
	static int tmp[maxn];
	for(int i=1;i<=n;i++) tmp[i]=a[i];
	sort(tmp+1,tmp+n+1);
	int *_end=unique(tmp+1,tmp+n+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(tmp+1,_end,a[i])-tmp;
}
inline int query(int u,int l,int r,int v)
{
	if(l>=r) return w[u];
	int mid=(l+r)>>1;
	if(mid<v) return query(u<<1|1,mid+1,r,v); //kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkssssssssssssssssssssssssssssssssssssssssssssssssssssssssssccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc000000000000000000000000000000000000000000000000000000000000000000033333333333333333333333333333333333333333333333333333666
	else return query(u<<1,l,mid,v)+query(u<<1|1,mid+1,r,v);
}
inline void update(int u,int l,int r,int v)
{
	w[u]++;
	if(l==r) return;
	int mid=(l+r)/2;
	if(mid>=v) update(u<<1,l,mid,v);
	else update(u<<1|1,mid+1,r,v);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	init();
	for(int j=1;j<=n;j++)
	{
		ans+=query(1,1,n,a[j]+1);
		update(1,1,n,a[j]);
	}
	printf("%ld",ans);
	return 0;
}
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
2022/8/18 18:56
加载中...