treap 代码
```
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
template<class Read>void in(Read &x){
x=0;
int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
f|=(ch=='-');
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x=f?-x:x;
return;
}
int n,m,top,root,a[2000005],f[2000005],s[2000005][2],w[2000005],val[2000005];
inline void pushup(int x){
f[x]=f[s[x][0]]+f[s[x][1]]+1;
}
void rotate(int &x,int c){
int id=s[x][c];
s[x][c]=s[id][c^1];
s[id][c^1]=x;
pushup(x);
pushup(id);
x=id;
}
void ins(int &x,int c){
if(x==0){
x=++top;
f[x]=1;
w[x]=c;
val[x]=rand();
return;
}
f[x]++;
if(c<=w[x]){
ins(s[x][0],c);
if(val[s[x][0]]<val[x])rotate(x,0);
}
else{
ins(s[x][1],c);
if(val[s[x][1]]<val[x])rotate(x,1);
}
}
void del(int &x,int c){
if(w[x]==c){
if(s[x][0]*s[x][1]==0){
x=s[x][0]+s[x][1];
return;
}
if(val[s[x][0]]<val[s[x][1]]){
rotate(x,0);
del(s[x][1],c);
}
else{
rotate(x,1);
del(s[x][0],c);
}
pushup(x);
return;
}
if(c<w[x])del(s[x][0],c);
else del(s[x][1],c);
pushup(x);
}
int query(int x,int c){
if(f[s[x][0]]==c-1)return w[x];
if(c<=f[s[x][0]])return query(s[x][0],c);
else return query(s[x][1],c-f[s[x][0]]-1);
}
int main(){
in(n);in(m);
for(int i=1;i<=n;i++)in(a[i]);
puts("0");
ins(root,a[1]);
for(int i=2;i<=n;i++){
if(i-1>m)del(root,a[i-1-m]);
printf("%d\n",query(root,1));
ins(root,a[i]);
}
return 0;
}
```
by Waddles @ 2019-10-31 22:28:47
~~是您太强了~~
by HaveFun @ 2019-10-31 22:29:03
@[Song_of_long_voyage](/space/show?uid=119120) 把s改成```s[2000005][3]```试一下
by qbu666666 @ 2019-10-31 22:31:17
~~话说这题不是单调队列吗~~
by ctt2006 @ 2019-10-31 22:31:42
您强到卡了我的界面
by wwz20050323 @ 2019-10-31 22:31:56
@[AT是女孩子](/space/show?uid=157598) 还是Temmm
by Waddles @ 2019-10-31 22:32:44
@[Song_of_long_voyage](/space/show?uid=119120) 不要把数组（的某一维）开成$ 2^k $，会降低运行效率
For example:
```cpp
const int maxn=1<<10;
int a[maxn][maxn];
```
就没有
```cpp
const int maxn=1<<10;
int a[maxn+1][maxn+1];
```
快
by qbu666666 @ 2019-10-31 22:33:21
~~其他的我就不能帮您了，没学Treap~~
by qbu666666 @ 2019-10-31 22:33:52
@[Song_of_long_voyage](/space/show?uid=119120) ~~但是这真的不是一个单调队列吗，您可能写丑了~~
by qbu666666 @ 2019-10-31 22:34:34
@[AT是女孩子](/space/show?uid=157598) 第一次听说emmm，长见识了
~~（好像是窝孤陋寡闻）~~
by Waddles @ 2019-10-31 22:34:36