自动搬运

查看原文

来自洛谷，原作者为

	detect a loser.

搬运于2025-08-24 22:23:43，当前版本为作者最后更新于2020-09-08 23:03:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

看起来非常不可做的题。

寻找突破点，每一个桶先内部排序，中位数变式有

• 如果中位数在t，位置为post,在s中第一个比中位数小的数位置在poss。

有$\frac{|s|+|t|+1}{2}=post+poss$,将其做变形：$|s|-2*poss==2*post-|t|$。

因为必须要是做接近的两个数满足这个关系才成立。

所以不难想到对每一个数按照权值排序，同时记录其$|i|-2*posi$。

任何时刻都只保留每一个桶最大的数，只要有满足上述式子的一对桶就是一组解。

查询值和删除值可以用链表$O(1)$实现。

因为一共只有$N^2$对，所以总时间复杂度为$O(N^2+NMlogM)$

(p.s 链表好难调）

code

#include<bits/stdc++.h>
using namespace std;
inline int getint(){
	int summ=0,f=1;char ch;
	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
	if(ch=='-')f=-1,ch=getchar();
	for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
	return summ*f;
}
const int M=1e4+5,N=505;
int n,m,b[N],cnt;
struct node{
	int val,id;
	friend bool operator < (node x,node y){
		return x.val<y.val;
	}
}a[N*M];
int vl[M*4],ans[M*4],head[M*4],nex[M*4],pre[M*4];
inline void Insert(int val,int pos){
	val+=2*M;
	if(head[val]) pre[head[val]]=pos;
	nex[pos]=head[val];head[val]=pos;
}
inline void Delete(int val,int pos){
	val+=2*M;
	if(nex[pos]) pre[nex[pos]]=pre[pos];
	if(pre[pos]) nex[pre[pos]]=nex[pos];
	if(head[val]==pos) head[val]=nex[pos];
	nex[pos]=pre[pos]=0;
} 
signed main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		n=getint();vl[i]-=n;
		for(int j=1;j<=n;j++) b[j]=getint();
		sort(b+1,b+n+1);
		ans[i]^=(i+i+b[(n+1)>>1]);
		Insert(-n,i);
		for(int j=1;j<=n;j++) a[++cnt].val=b[j],a[cnt].id=i;
	}
	sort(a+1,a+cnt+1);
	for(int i=1;i<=cnt;i++){
		Delete(vl[a[i].id],a[i].id);vl[a[i].id]+=2;Insert(vl[a[i].id],a[i].id);
		for(int j=head[2*M-vl[a[i].id]];j;j=nex[j])
		  if(j!=a[i].id) ans[j]^=(j+a[i].id+a[i].val),ans[a[i].id]^=(j+a[i].id+a[i].val);
		for(int j=head[2*M-vl[a[i].id]+1];j;j=nex[j])
		  if(j!=a[i].id) ans[j]^=(j+a[i].id+a[i].val),ans[a[i].id]^=(j+a[i].id+a[i].val);
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
	return 0;
}