专栏文章

题解：AT_arc210_b [ARC210B] Remove Median Operations

iidle_onlooker
AT_arc210_b题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2votv
此快照首次捕获于
2025/12/01 19:40
3 个月前
此快照最后确认于
2025/12/01 19:40
3 个月前
查看原文
结论题，感觉出的很巧妙。
我们尝试按照题意模拟一下操作。
每次将序列 BB 中的一个元素插入序列 AA 中，并删除序列 AA 的中位数。
由于序列 AA 的长度 nn 是偶数，所以删除的数一定是在序列 AA 中大小排名为 n2+1\frac{n}{2}+1 的数。
由此推出，被删除的元素在序列 AA 和序列 BB 中的整体排名一定既不属于前 n2\frac{n}{2} 也不属于后 n2\frac{n}{2}。
我们一共进行了 mm 次插入和删除操作，而序列 AA 和序列 BB 的总体长度为 n+mn+m。
这意味着在序列 AA 和序列 BB 中整体排名既不属于前 n2\frac{n}{2} 也不属于后 n2\frac{n}{2} 的数只有 mm 个！
显然，我们把这些数都给删除了，所以剩下的数就是序列 AA 和序列 BB 中大小排名在前 n2\frac{n}{2} 和后 n2\frac{n}{2} 的数。
我们需要维护一个序列的前 n2\frac{n}{2} 个数和后 n2\frac{n}{2} 个数之和的同时支持单点修改，值域线段树可以胜任这些操作。
代码CPP
//为什么要攀登？因为山就在那里。 
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...