求助fhq平衡树最后一个点TLE

liaoz123 @ 2023-04-17 22:27:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+5;
struct node{
    int ls,rs,siz,pri;
    ll val,sum;
}s[N];
int n,m,l,r,p,cnt,root,id[N];
void pushup(int u){s[u].siz=s[s[u].ls].siz+1+s[s[u].rs].siz;s[u].sum=s[s[u].ls].sum+s[s[u].rs].sum+s[u].val;}
void split(int x,ll y,int &l,int &r){
    if(!x){l=r=0;return;}
    if(s[x].val>y){
        r=x;
        split(s[x].ls,y,l,s[x].ls);
    }else{
        l=x;
        split(s[x].rs,y,s[x].rs,r);
    }
    pushup(x);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(s[x].pri>s[y].pri){
        s[x].rs=merge(s[x].rs,y);
        pushup(x);return x;
    }else{
        s[y].ls=merge(x,s[y].ls);
        pushup(y);return y;
    }
}
int add(int x){
    s[++cnt].val=x;s[cnt].sum=x;
    s[cnt].ls=s[cnt].rs=0;s[cnt].pri=rand();
    s[cnt].siz=1;return cnt;
}
void insert(ll x){
    split(root,x,l,r);
    root=merge(merge(l,add(x)),r);
}
void change(int x,ll y){
    int ss=id[x];
    split(root,s[ss].val,l,r);
    split(l,s[ss].val-1,l,p);
    root=merge(merge(l,merge(s[p].ls,s[p].rs)),r);
    insert(y);id[x]=cnt;
}
int main(){
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)insert(0),id[i]=i;
    while(m--){
        char op;int x;ll y;
        cin>>op;scanf("%d%lld",&x,&y);
        if(op=='U')change(x,y);
        else{
            split(root,y,l,r);
            int ss=s[r].siz;
            if(s[l].sum>=(1ll*x-1ll*ss)*y)puts("TAK");
            else puts("NIE");
            root=merge(l,r);
        }
    }
    return 0;
}

by 1zsczsczsc @ 2023-07-09 19:25:46

减小常数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+5;
struct node{
    int ls,rs,siz,pri;
    ll val,sum;
}s[N];
int n,m,l,r,p,cnt,root,id[N];
inline void pushup(int u){s[u].siz=s[s[u].ls].siz+1+s[s[u].rs].siz;s[u].sum=s[s[u].ls].sum+s[s[u].rs].sum+s[u].val;}
void split(int x,ll y,int &l,int &r){
    if(!x){l=r=0;return;}
    if(s[x].val>y){
        r=x;
        split(s[x].ls,y,l,s[x].ls);
    }else{
        l=x;
        split(s[x].rs,y,s[x].rs,r);
    }
    pushup(x);
}
inline int merge(int x,int y){
    if(!x||!y)return x+y;
    if(s[x].pri>s[y].pri){
        s[x].rs=merge(s[x].rs,y);
        pushup(x);return x;
    }else{
        s[y].ls=merge(x,s[y].ls);
        pushup(y);return y;
    }
}
inline int add(int x){
    s[++cnt].val=x;s[cnt].sum=x;
    s[cnt].ls=s[cnt].rs=0;s[cnt].pri=rand();
    s[cnt].siz=1;return cnt;
}
inline void insert(ll x){
    split(root,x,l,r);
    root=merge(merge(l,add(x)),r);
}
inline void change(int x,ll y){
    int ss=id[x];
    split(root,s[ss].val,l,r);
    split(l,s[ss].val-1,l,p);
    root=merge(merge(l,merge(s[p].ls,s[p].rs)),r);
    insert(y);id[x]=cnt;
}
char op[5];int x;ll y;
int main(){
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)insert(0),id[i]=i;
    while(m--)
    {
        scanf("%s%d%lld",op,&x,&y);
        if(op[0]=='U')change(x,y);
        else{
            split(root,y,l,r);
            int ss=s[r].siz;
            if(s[l].sum>=(1ll*x-1ll*ss)*y)puts("TAK");
            else puts("NIE");
            root=merge(l,r);
        }
    }
    return 0;
}