1 条题解
-
1
首先随便用什么东西比如对顶堆或者线段树就能做到。
考虑能否更优。
先考虑两个两个向一个集合中加数,中位数发生变化当且仅当加入的两个数均大于等于或小于等于当前的中位数。
但是这样需要维护某个数的前驱和后继,仍然是的。
因此我们考虑一次处理好所有数的大小关系,然后从后向前考虑删数。
同理我们可以知道,两个两个从一个集合中删数,中位数发生变化当且仅当删除的两个数均大于等于或小于等于当前的中位数。
这样就可以用链表来维护了。复杂度,取(据说这样可以卡进一级缓存所以比较快?)。瓶颈在于基数排序。
赛时基数排序写锅了#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; }建议把开到3000
- 1
信息
- ID
- 124
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 108
- 已通过
- 18
- 上传者