权值线段树做法 50分 后10个TLE 求助 胶胶~

#include<bits/stdc++.h>
using namespace std;
const double PI=acos(-1);
//#define int long long
#define double long double
#define endl '\n'

const int N=6e5+10;
int a[N];
struct Node
{
    int l, r,sum;

}tr[N * 4];

void pushup(Node &u, Node &l, Node &r)
{

    u.sum = l.sum + r.sum;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void pushdown(int u)
{

}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        // TODO: 懒标记也要加上
        //tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
//      tr[u].v+=d;
        tr[u].sum+=d;
//      tr[u].add+=d;

    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}
//
int query(int root, int L, int R) { //查询数字L到R出现多少次
    if (tr[root].r < L || tr[root].l > R)return 0;
    if (L <= tr[root].l && tr[root].r <= R)return tr[root].sum;
    return query(root<<1, L, R) + query(root<<1|1, L, R);
}
vector<int>vs;
int find(int k){
    return  lower_bound(vs.begin(),vs.end(),k)-vs.begin();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n,m;cin>>n;
    int maxn=-1e9;
    vs.push_back(-(2e9+7));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxn=max(maxn,a[i]);
        vs.push_back(a[i]);
    }
    sort(vs.begin(),vs.end());
    vs.erase(unique(vs.begin(),vs.end()),vs.end());
    build(1,1,n);
    int res=0;
    for(int i=1;i<=n;i++){
        res+=query(1,find(a[i]+1),find(maxn));
        update(1,find(a[i]),find(a[i]),1);
    }
    cout<<res;

    return 0;
}