1 条题解

  • 1
    @ 2026-9-22 17:59:41

    首先随便用什么东西比如对顶堆或者线段树就能做到O(Tnlog⁡n)O(Tn \log n)。

    考虑能否更优。

    先考虑两个两个向一个集合中加数,中位数发生变化当且仅当加入的两个数均大于等于或小于等于当前的中位数。

    但是这样需要维护某个数的前驱和后继,仍然是O(log⁡n)O(\log n)的。

    因此我们考虑一次处理好所有数的大小关系,然后从后向前考虑删数。

    同理我们可以知道,两个两个从一个集合中删数,中位数发生变化当且仅当删除的两个数均大于等于或小于等于当前的中位数。

    这样就可以用链表来维护了。复杂度O(Tnlog⁡BV)O(Tn\log_B{V}),BB取256256(据说这样可以卡进一级缓存所以比较快?)。瓶颈在于基数排序。赛时基数排序写锅了

    #include<bits/stdc++.h>
    using namespace std;
    #define pii pair<int,int>
    #define F first
    #define S second
    #define mkp make_pair
    #define psb push_back
    const int N=10100,mod=998244353;
    //Fast IO from wly
    #define MYBUF (1 << 20)
    char buf[MYBUF], *p1, *p2;
    #define gc()                                                               \
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MYBUF, stdin), p1 == p2)   \
           ? EOF                                                               \
           : *p1++)
    inline int rd() {
      int x = 0;
      char c = gc();
      while (c < '0' || c > '9') c = gc();
      for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c ^ '0');
      return x;
    }
    char pbuf[MYBUF], *pp = pbuf;
    inline void pc(const char &c) {
      if (pp - pbuf == MYBUF) fwrite(pbuf, 1, MYBUF, stdout), pp = pbuf;
      *pp++ = c;
    }
    inline void wt(int x) {
      static int sta[35];
      int top = 0;
      do {
        sta[top++] = x % 10, x /= 10;
      } while (x);
      while (top) pc(sta[--top] + '0');
    }
    #undef MYBUF
    
    int T,n,a[N],idx[N];
    const int Base=256;
    int vec[Base+10][N],len[Base+10];
    int fid[N];
    int aft[N],bef[N];
    int ans[N],anstot;
    void del(int x){
    	aft[bef[x]]=aft[x];
    	bef[aft[x]]=bef[x];
    }
    bool cmp(int x,int y){
    	return a[x]<a[y];
    }
    signed main(){
    	T=rd();
    	while(T--){
    		n=rd();anstot=0;
    		for(int i=1;i<=n;i++) a[idx[i]=i]=rd();
    		if(n%2==0) n--;
    		int tot=0;
    		//Sort
    		int nwcnt=0;
    		for(int j=0;j<=3;j++){
    			for(int i=1;i<=n;i++){
    				int nx=((a[idx[i]]>>nwcnt)&255);
    				vec[nx][++len[nx]]=idx[i];
    			}for(int i=0;i<=255;i++){
    				for(int j=1;j<=len[i];j++) idx[++tot]=vec[i][j];
    				len[i]=0;
    			}tot=0;nwcnt=nwcnt+8;
    		}
    		//Done
    		idx[n+1]=n+1;
    		for(int i=1;i<=n;i++){
    			fid[idx[i]]=i;
    			bef[idx[i]]=idx[i-1];
    			aft[idx[i]]=idx[i+1];
    		}aft[0]=idx[1];bef[n+1]=idx[n];
    		ans[++anstot]=a[idx[(n+1)>>1]];
    		int nwmid=idx[(n+1)>>1];
    		for(int i=n;i>=3;i-=2){
    			int x=i,y=i-1;
    			if(abs(fid[x]-fid[nwmid])<abs(fid[y]-fid[nwmid])) swap(x,y);
    			del(x);del(y);
    			if(fid[x]<=fid[nwmid]&&fid[y]<=fid[nwmid]){
    				nwmid=aft[nwmid];
    				if(ans[anstot]!=a[nwmid]) ans[++anstot]=a[nwmid];
    			}else if(fid[x]>=fid[nwmid]&&fid[y]>=fid[nwmid]){
    				nwmid=bef[nwmid];
    				if(ans[anstot]!=a[nwmid]) ans[++anstot]=a[nwmid];
    			}
    		}
    		wt(anstot);pc('\n');
    		while(anstot){
    			wt(ans[anstot--]);pc(' ');
    		}pc('\n');
    	}
    	
    	
    	fwrite(pbuf, 1, pp - pbuf, stdout);
    	return 0;
    }
    

    建议把TT开到3000

    • 1

    信息

    ID
    124
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    108
    已通过
    18
    上传者