题解：AT_arc210_b [ARC210B] Remove Median Operations

· · 题解

结论题，感觉出的很巧妙。

我们尝试按照题意模拟一下操作。

每次将序列 B 中的一个元素插入序列 A 中，并删除序列 A 的中位数。
由于序列 A 的长度 n 是偶数，所以删除的数一定是在序列 A 中大小排名为 \frac{n}{2}+1 的数。
由此推出，被删除的元素在序列 A 和序列 B 中的整体排名一定既不属于前 \frac{n}{2} 也不属于后 \frac{n}{2}。

我们一共进行了 m 次插入和删除操作，而序列 A 和序列 B 的总体长度为 n+m。
这意味着在序列 A 和序列 B 中整体排名既不属于前 \frac{n}{2} 也不属于后 \frac{n}{2} 的数只有 m 个！
显然，我们把这些数都给删除了，所以剩下的数就是序列 A 和序列 B 中大小排名在前 \frac{n}{2} 和后 \frac{n}{2} 的数。

我们需要维护一个序列的前 \frac{n}{2} 个数和后 \frac{n}{2} 个数之和的同时支持单点修改，值域线段树可以胜任这些操作。

:::info[代码]

//为什么要攀登？因为山就在那里。 
#include<bits/stdc++.h>
#define mrx 0x7f7f7f7f7f7f7f7f
#define int long long
using namespace std;
inline int read(){
    int num=0,flag=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        num=(num<<3)+(num<<1)+(ch^48);
        ch=getchar();
    }
    return num*flag;
}
inline void write(int num){
    if(num<0) putchar('-'),num=-num;
    if(num>9) write(num/10);
    putchar(num%10+'0');
}
inline void print(int num){
    write(num);
    putchar('\n');
}
inline void out(int num){
    write(num);
    putchar(' ');
}
int ksm(int a,int b,int mod){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod,b>>=1;
    }
    return ans;
}
const int MIN=1,MAX=1e9;
int n,m,_;
int a[200010];
int b[200010];
struct line_tree{
    int ls,rs;
    int sum;
    int num;
}tree[400010*32];
int dfn,rt;
void pushup(int id){
    tree[id].sum=tree[tree[id].ls].sum+tree[tree[id].rs].sum;
    tree[id].num=tree[tree[id].ls].num+tree[tree[id].rs].num;
}
void add(int k,int m,int &id,int L=MIN,int R=MAX){
    if(!id) id=++dfn;
    if(L==R) return tree[id].num+=m,tree[id].sum+=k*m,void();
    int mid=(L+R)>>1;
    if(k<=mid) add(k,m,tree[id].ls,L,mid);
    else add(k,m,tree[id].rs,mid+1,R);
    pushup(id);
}
int query_front_sum(int k,int id,int L=MIN,int R=MAX){
    if(!id) return 0;
    if(L==R) return min(k,tree[id].num)*L;
    int mid=(L+R)>>1,res=0;
    if(tree[tree[id].ls].num<=k) res+=tree[tree[id].ls].sum+query_front_sum(k-tree[tree[id].ls].num,tree[id].rs,mid+1,R);
    else res+=query_front_sum(k,tree[id].ls,L,mid);
    return res;
}
int query_back_sum(int k,int id,int L=MIN,int R=MAX){
    if(!id) return 0;
    if(L==R) return min(k,tree[id].num)*L;
    int mid=(L+R)>>1,res=0;
    if(tree[tree[id].rs].num<=k) res+=tree[tree[id].rs].sum+query_back_sum(k-tree[tree[id].rs].num,tree[id].ls,L,mid);
    else res+=query_back_sum(k,tree[id].rs,mid+1,R);
    return res;
}   
signed main(){
    n=read(),m=read(),_=read();
    for(int i=1;i<=n;i++) a[i]=read(),add(a[i],1,rt);
    for(int i=1;i<=m;i++) b[i]=read(),add(b[i],1,rt);
    while(_--){
        int op=read(),x=read(),y=read();
        if(op==1){
            add(a[x],-1,rt);
            a[x]=y;
            add(a[x],1,rt);
        }else{
            add(b[x],-1,rt);
            b[x]=y;
            add(b[x],1,rt);
        }
        int ans=query_front_sum(n/2,rt)+query_back_sum(n/2,rt);
        print(ans);
    }
    return 0;
}

:::