這道題是一道splay裸題，然而身為蒟蒻的我并不會，所以這道題我維護的是一個大根堆與一個小根堆結合起來的類似沙漏的結構。
本題難點在于詢問的不是最大最小值，而是第K小值，所以我們想到了維護這樣兩個堆，上面是一個大小限定為K-1的大根堆，下面是一個小根堆，每次插入/查詢操作時，保持前K-1大的始終在大根堆內。
插入/查詢函數：

int heap[200005][3],hsize[3]; int m,n,num[200005],temp; void put(int x,int i){heap[++hsize[i]][i]=x;int son=hsize[i],pa=son>>1;while(pa>=1){if(i==1){if(heap[pa][i]>heap[son][i]){int t=heap[pa][i];heap[pa][i]=heap[son][i];heap[son][i]=t;son=pa;pa>>=1;}else break;}else {if(heap[pa][i]<heap[son][i]){int t=heap[pa][i];heap[pa][i]=heap[son][i];heap[son][i]=t;son=pa;pa>>=1;}else break;} } } int get(int i){int rv=heap[1][i];heap[1][i]=heap[hsize[i]--][i];int pa=1,son;while(pa<=(hsize[i]>>1)){if(i==1) son=heap[pa<<1][i]<heap[pa<<1|1][i]?pa<<1:pa<<1|1;else son=heap[pa<<1][i]>heap[pa<<1|1][i]?pa<<1:pa<<1|1;if(i==1){if(heap[pa][i]>heap[son][i]){int t=heap[pa][i];heap[pa][i]=heap[son][i];heap[son][i]=t;pa=son;}else break;}else {if(heap[pa][i]<heap[son][i]){int t=heap[pa][i];heap[pa][i]=heap[son][i];heap[son][i]=t;pa=son;}else break;} }return rv; }

對整體的插入/查詢：

void putt(int x){put(x,1);if(x==heap[1][1]){get(1);put(x,2);int t=get(2);put(t,1);} } int gett(){temp++;int rv=get(1);put(rv,2);return rv; }

附：跑得飛快的代碼：

#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; int read(){int rv=0,fh=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') fh=-1;c=getchar();}while(c>='0'&&c<='9'){rv=(rv<<1)+(rv<<3)+c-'0';c=getchar();}return rv*fh; } int heap[200005][3],hsize[3]; int m,n,num[200005],temp; void put(int x,int i){heap[++hsize[i]][i]=x;int son=hsize[i],pa=son>>1;while(pa>=1){if(i==1){if(heap[pa][i]>heap[son][i]){int t=heap[pa][i];heap[pa][i]=heap[son][i];heap[son][i]=t;son=pa;pa>>=1;}else break;}else {if(heap[pa][i]<heap[son][i]){int t=heap[pa][i];heap[pa][i]=heap[son][i];heap[son][i]=t;son=pa;pa>>=1;}else break;} } } int get(int i){int rv=heap[1][i];heap[1][i]=heap[hsize[i]--][i];int pa=1,son;while(pa<=(hsize[i]>>1)){if(i==1) son=heap[pa<<1][i]<heap[pa<<1|1][i]?pa<<1:pa<<1|1;else son=heap[pa<<1][i]>heap[pa<<1|1][i]?pa<<1:pa<<1|1;if(i==1){if(heap[pa][i]>heap[son][i]){int t=heap[pa][i];heap[pa][i]=heap[son][i];heap[son][i]=t;pa=son;}else break;}else {if(heap[pa][i]<heap[son][i]){int t=heap[pa][i];heap[pa][i]=heap[son][i];heap[son][i]=t;pa=son;}else break;} }return rv; } void putt(int x){put(x,1);if(x==heap[1][1]){get(1);put(x,2);int t=get(2);put(t,1);} } int gett(){temp++;int rv=get(1);put(rv,2);return rv; } int f[200005]; int main(){freopen("in.txt","r",stdin);m=read();n=read();for(int i=1;i<=m;i++){num[i]=read();}for(int i=1;i<=n;i++){f[read()]++;}for(int i=1;i<=m;i++){putt(num[i]);while(f[i]){printf("%d\n",gett());f[i]--;}}/*for(int i=1;i<=10000;i++){put(rand(),2);}for(int i=1;i<=10000;i++){printf("%d ",get(2));}*/fclose(stdin);return 0; }

轉載于:https://www.cnblogs.com/Mr-WolframsMgcBox/p/7868354.html

總結

以上是生活随笔為你收集整理的洛谷 [P1801] 黑匣子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。