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可能是线段树常数比较大