题解 - [THUPC2019]大碗宽面

detect · 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;
}