有个问题,这题如果我用线段树做为什么只有25分?

P1908 逆序对

cz_Huang @ 2024-11-23 22:52:42

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll g=5e5+5;

ll n,a[g];

struct segTree
{
    struct Node{
        ll l,r;
        ll num;
    } tr[g*4];
    void Build(ll pos,ll l,ll r)
    {
        tr[pos].l=l;
        tr[pos].r=r;
        if(l==r)
        {
            tr[pos].num=a[l];
            return;
        }
        ll mid=l+r>>1;
        Build(pos<<1,l,mid);
        Build(pos<<1|1,mid+1,r);
        tr[pos].num=max(tr[pos<<1].num,tr[pos<<1|1].num);
    }
    int Query(ll pos,ll x,ll dl)
    {
        if(tr[pos].num<x&&tr[pos].l>dl)
        {
            return tr[pos].r-tr[pos].l+1;
        }
        if(tr[pos].l==tr[pos].r) return 0;
        int dt=0;
        ll mid=(tr[pos].l+tr[pos].r)>>1;
        if(mid>dl) dt+=Query(pos<<1,x,dl);
        if(tr[pos].r>dl) dt+=Query(pos<<1|1,x,dl);  
        return dt;
    }
} ST;

int main(void)
{
    ll ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    ST.Build(1,1,n);
    for(int i=1;i<n;i++) 
    {
        ans+=ST.Query(1,a[i],i);
    }
    cout<<ans;
}

by cz_Huang @ 2024-11-23 22:53:51

我的代码确实忽略了重复数这个细节,不过想知道的还是线段树怎么还会tle


by estimate_error @ 2024-11-27 16:06:34

@cz_Huang可能是线段树常数比较大


|