卷王 @ 2022-08-18 18:56:52
我按深进里的代码思路自己打了一遍,结果只有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;
}
by Eason2009 @ 2022-08-18 20:02:19
@holdyhao_Genius 确实是query那里寄了,帮您改了一下query函数,自己对照一下罢
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(); //快读
#define maxn 500001 //定义数据范围
int n,a[maxn],w[maxn*4]; //输入变量、输入的数组、权值线段树
int 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 ql,int qr)
{
if(r<ql||l>qr||l>r) return 0;
if(l>=ql&&r<=qr) return w[u];
int mid=(l+r)>>1;
return query(u<<1,l,mid,ql,qr)+query(u<<1|1,mid+1,r,ql,qr);
}
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);
}
signed 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,n);
update(1,1,n,a[j]);
}
printf("%lld",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;
}
by Eason2009 @ 2022-08-18 20:03:20
@holdyhao_Genius 线段树区间询问我的建议是不要用其他奇奇怪怪的写法,就用我的这种。
by 卷王 @ 2022-08-18 20:05:13
@Eason2009 嗯,我用了一个效率很快的方法:https://www.luogu.com.cn/record/84264506