权值线段树玄关求条

RT

在第是一个点的14211个数据周围出了错误

#include <bits/stdc++.h>

using namespace std;

const int N = 500000 ; 

struct T{
    int ls,rs,app;
    T(){ls=rs=app=0;}
}t[4*N+10];

int n,pos[N+10],idex,maxn,root;
long long a[N+10],b[N+10],ans;

int init()
{
    sort(b+1,b+1+n);
    int len=unique(b+1,b+1+n)-(b+1);
    for(int i=1;i<=n;i++)
    {
        int k=lower_bound(b+1,b+1+n,a[i])-b;
        pos[i]=k; 
    }
    return len;
}

inline void updata(int x,int l,int r,int &now)
{
    if(now==0)now=++idex;
    if(l==r)
    {
        t[now].app++;
    }
    else
    {
        int mid=(l+r)>>1;
        if(x<=mid)updata(x,l,mid,t[now].ls);
        else updata(x,mid+1,r,t[now].rs);
        t[now].app=t[t[now].ls].app+t[t[now].rs].app;
    }
    return;
}

inline int query(int q,int w,int l,int r,int now)
{
    if(now==0)return 0;
    if(q<=l&&r<=w)return t[now].app;
    else
    {
        int mid=(l+r)>>1;
        int res=0;
        if(q<=mid)res+=query(q,w,l,mid,t[now].ls);
        if(w>mid)res+=query(q,w,mid+1,r,t[now].rs);
        return res; 
    }
}

int main()
{
    //freopen("P1908_11.in","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    maxn=init();
    for(int i=1;i<=n;i++)
    {
        updata(pos[i],1,maxn,root);
        if(pos[i]!=maxn)ans+=query(pos[i]+1,maxn,1,maxn,root);
    }
    cout<<ans<<endl;
    return 0;
}