被自创题卡了3天3夜没想明白

10 2
-954902377 -224762699 -652264904 -706466142 -460110438 -27127982 -973883558 -387211944 674277713 -182483790
U 7 -524606695
U 8 -116578835
Q 4 9

-460110438

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int MXN = 300010;
struct Event {
    int t;
    int p;
    int v;
    int L, R;
    int k;
    int i;
};

int n, m;
int A[MXN];
int ans[MXN];
vector<int> ns;
vector<Event> evs;
class ftree {
private:
    vector<int> t;
    int s;
public:
    ftree(int n):s(n){t.resize(n+1,0);}
    void update(int i,int d){
        while(i<=s){
            t[i]+=d;
            i+=i&-i;
        }
    }
    int query(int i){
        int sum=0;
        while(i){
            sum+=t[i];
            i-=i&-i;
        }
        return sum;
    }
    int rq(int L,int R){
        return query(R)-query(L-1);
    }
};
int gid(int x){
    return lower_bound(ns.begin(),ns.end(),x)-ns.begin();
}
void solve(vector<Event>& evs,int L,int R,ftree& f){
    if(evs.empty()) return;
    if(L==R){
        for(auto& e:evs)
            if(e.t==2) ans[e.i]=L;
        return;
    }
    int mid=(L+R)/2;
    vector<Event> levs, revs;
    for(auto& e:evs){
        if(e.t==0||e.t==1){
            if(e.v<=mid){
                f.update(e.p+1,e.t==0?1:-1);
                levs.push_back(e);
            }
            else revs.push_back(e);
        }
        else{
            int cnt=f.rq(e.L+1,e.R+1);
            if(e.k<=cnt) levs.push_back(e);
            else{
                e.k-=cnt;
                revs.push_back(e);
            }
        }
    }
    for(auto& e:evs)
        if(e.t!=2&&e.v<=mid) f.update(e.p+1,e.t==0?-1:1);
    solve(levs,L,mid,f);
    solve(revs,mid+1,R,f);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>A[i];
        ns.push_back(A[i]);
    }
    int qid=0;
    for(int i=0;i<n;i++)
        evs.push_back({0,i,A[i],-1,-1,-1,-1});
    for(int i=0;i<m;i++){
        char op;cin>>op;
        if(op=='U'){
            int idx,x;cin>>idx>>x;
            evs.push_back({1,idx,A[idx],-1,-1,-1,-1});
            evs.push_back({0,idx,x,-1,-1,-1,-1});
            A[idx]=x;
            ns.push_back(x);
        }
        else if(op=='Q'){
            int l,r;cin>>l>>r;
            int len=r-l+1;
            int k=(len+1)/2;
            evs.push_back({2,-1,-1,l,r,k,qid++});
        }
    }
    sort(ns.begin(),ns.end());
    ns.erase(unique(ns.begin(),ns.end()),ns.end());
    int D=ns.size();
    for(auto& e:evs)
        if(e.t!=2) e.v=gid(e.v);
    ftree f(n);
    vector<Event> iev=evs;
    solve(iev,0,D-1,f);
    for(int i=0;i<qid;i++)
        cout<<ns[ans[i]]<<'\n';
    return 0;
}