求救！样例和hack过了，其他全错，树状数组+二分+离散（有注释）

Rorou @ 2024-02-09 17:12:39

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int a[N],b[N],n,t[N],c[N];
int lowbit(int x){return x&(-x);}
void add(int x,int k){
    for(int i=x;i<=n;i+=lowbit(i))t[i]+=k;
}
int sum(int x){
    int num=0;
    for(int i=x;i;i-=lowbit(i))num+=t[i];
    return num;
}
int find(int x){
    int p,l=1,r=n,mid,o=x,ans;
    while(l<=r){
        mid=(l+r)/2;
        p=sum(mid);//看原数组中比他先放入且值小于他的数的数量 
        if(o<=p)r=mid-1,ans=mid;
        else l=mid+1;
    }
    return c[ans];
}
bool cmp(int x,int y){//离散化排序 
    return a[x]<a[y];
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];  
        b[i]=i;
    }
    sort(b+1,b+n+1,cmp);//离散化 
    for(int i=1;i<=n;i++){
        c[i]=a[b[i]];//离散b中数值代表的真实值 
    }

    int o=1;
    for(int i=1;i<=n;i++){
        add(b[i],1);
        if(i%2==1){
            cout<<find((i+1)/2)<<"\n";//寻找中位数 
        }
    }
    return 0;
} 

by Pump_kin @ 2024-02-19 21:22:17

@Canthy_zy 直接使用平衡树就可以了

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1000;
#define ls(x) l_son[x]
#define rs(x) r_son[x] 
int rt;
struct FHQ{
    int l_son[N],r_son[N],dat[N],size[N];
    int number[N],tot;
    int make_new(int x){
        size[++tot]=1;
        dat[tot]=rand();
        l_son[tot]=r_son[tot]=0;
        number[tot]=x;
        return tot;
    }
    #define maintain(x) size[x]=size[ls(x)]+size[rs(x)]+1
    void split(int u,int &x,int &y,int val){
        if(!u)return x=y=0,void();
        if(number[u]<=val)x=u,split(rs(u),rs(u),y,val);
        else y=u,split(ls(u),x,ls(u),val);
        maintain(u);
    }
    int merge(int x,int y){
        if(!x||!y)return x+y;
        if(dat[x]<=dat[y]){
            rs(x)=merge(rs(x),y);
            maintain(x);
            return x;
        }
        ls(y)=merge(x,ls(y));
        maintain(y);
        return y;
    }
    void ins(int x){
        int l,r;
        split(rt,l,r,x);
        rt=merge(merge(l,make_new(x)),r);
    }
    int kth(int u,int k){
        int Size=size[ls(u)]+1;
        if(Size==k)return number[u];
        if(Size<k)return kth(rs(u),k-Size);
        return kth(ls(u),k);
    }
}fhq;
int n;
int x;
int main(){
    srand(time(0));
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        fhq.ins(x);
        if(i%2==1){
            cout<<fhq.kth(rt,(i+1)/2)<<'\n';
        }
    }
    return 0;
}

by Rorou @ 2024-02-20 22:32:59

@Zhangxm214 收到，谢谢，我代码错误调出来了，此贴结