weiyangchen @ 2021-08-02 10:53:20
#include<bits/stdc++.h>
#define lson i<<1
#define rson i<<1|1
#define M 40005
using namespace std;
inline int read()
{
char chr=getchar();
int f=1,ans=0;
while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)){ans=ans*10;ans+=chr-'0';chr=getchar();}
return ans*f;
}
int n;
struct Node
{
int l,r,v;
}t[M<<2];
int a[M],b[M];
void push_up(int i)
{
t[i].v=t[lson].v+t[rson].v;
}
void build(int i,int l,int r)
{
t[i].l=l;
t[i].r=r;
t[i].v=0;
if(l==r)
{
return;
}
int mid=t[i].l+t[i].r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
void updata(int i,int x)
{
if(t[i].l==t[i].r)
{
++t[i].v;
return;
}
int mid=t[i].l+t[i].r>>1;
if(x<=mid)
updata(lson,x);
else
updata(rson,x);
push_up(i);
}
int query(int i,int l,int r)
{
if(l<=t[i].l&&t[i].r<=r)
return t[i].v;
int mid=t[i].l+t[i].r>>1;
int x=0;
if(l<=mid)
x+=query(lson,l,r);
if(mid<r)
x+=query(rson,l,r);
return x;
}
int main()
{
n=read();
int ans=0;
build(1,1,M);
for(int i=1;i<=n;++i)
a[i]=read(),b[i]=a[i];
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i)
{
int pos=lower_bound(b+1,b+n+1,a[i])-b;
a[i]=pos;
}
for(int i=1;i<=n;++i)
{
int x=a[i];
ans+=query(1,x+1,M);
updata(1,x);
}
printf("%d",ans);
return 0;
}
我该怎么办?
by caimingming @ 2021-08-17 20:10:10
数据范围是5e5吧,你M是4e4啊,而且没用long long
by weiyangchen @ 2021-08-18 10:46:19
蟹蟹大佬