是treap常数大了，还是我写丑了？

Waddles @ 2019-10-31 22:28:31

by Waddles @ 2019-10-31 22:28:47

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 HaveFun @ 2019-10-31 22:29:03

是您太强了

by Magallan_forever @ 2019-10-31 22:31:17

@Song_of_long_voyage 把s改成s[2000005][3]试一下

by ctt2006 @ 2019-10-31 22:31:42

话说这题不是单调队列吗

by wwz20050323 @ 2019-10-31 22:31:56

您强到卡了我的界面

by Waddles @ 2019-10-31 22:32:44

@AT是女孩子 还是Temmm

by Magallan_forever @ 2019-10-31 22:33:21

@Song_of_long_voyage 不要把数组（的某一维）开成 2^k ，会降低运行效率

For example:

const int maxn=1<<10;
int a[maxn][maxn];

就没有

const int maxn=1<<10;
int a[maxn+1][maxn+1];

快

by Magallan_forever @ 2019-10-31 22:33:52

其他的我就不能帮您了，没学Treap

by Magallan_forever @ 2019-10-31 22:34:34

@Song_of_long_voyage 但是这真的不是一个单调队列吗，您可能写丑了

by Waddles @ 2019-10-31 22:34:36

@AT是女孩子 第一次听说emmm，长见识了 （好像是窝孤陋寡闻）