蒟蒻求助,11点后面全部RE

P1908 逆序对

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

蟹蟹大佬


|