动态开点MLE求助

rt

// Problem: P1908 逆序对
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1908
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// By：lmq
// AC Time：2024-03-23 10:44:50

#include <bits/stdc++.h>
#define lmq (tree[i].lc)
#define rmq (tree[i].rc)
#define mid ((tree[i].l+tree[i].r)>>1)
using namespace std;
struct node{
    int l,r,lc,rc;
    long long sum;
};
vector<node> tree;
int n,cnt,a[5000005];
void push_up(int i){
    tree[i].sum=tree[lmq].sum+tree[rmq].sum;
}
void push_down(int i){
    if(lmq)return;
    lmq=++cnt;
    tree.push_back((node){});
    tree[lmq].l=tree[i].l;
    tree[lmq].r=mid;
    rmq=++cnt;
    tree.push_back((node){});
    tree[rmq].l=mid+1;
    tree[rmq].r=tree[i].r;
}
void upd(int i,int k){
    if(tree[i].l==k&&tree[i].r==k){
        tree[i].sum++;
        return;
    }
    push_down(i);
    if(k<=mid)upd(lmq,k);
    else upd(rmq,k);
    push_up(i);
}
int qry(int i,int l,int r){
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    if(tree[i].sum==0)return 0;
    push_down(i);
    long long sum=0;
    if(l<=mid)sum+=qry(lmq,l,r);
    if(r>mid)sum+=qry(rmq,l,r);
    return sum;
}
signed main(){
    cin>>n;
    int mad=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mad=max(mad,a[i]);
    }
    cnt=1;
    tree.push_back((node){});
    tree.push_back((node){});
    tree[1].l=1,tree[1].r=1e9+7;
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=qry(1,a[i]+1,1e9+7);
        upd(1,a[i]);
    }
    cout<<ans;
    return 0;
}