权值线段树套fhqtreap求助qwq

回复帖子

@WA王子  2021-06-11 12:58 回复

WA8个点,MLE2个点,代码放在二楼和三楼

@WA王子  2021-06-11 12:58 回复 举报

压行版:

#include<cstdio>
#include<cstdlib>
#include<ctime>
const int maxn=500001;
namespace treap{
int val[maxn],lc[maxn],rc[maxn],s[maxn],cnt;short key[maxn];
inline int newnode(int x){val[++cnt]=x,lc[cnt]=rc[cnt]=0,s[cnt]=1,key[cnt]=std::rand();return cnt;}
inline void pushup(int x){s[x]=s[lc[x]]+s[rc[x]]+1;}
void split(int rt,int&a,int&b,int x) {
    if(!rt){a=b=0;return;}
    if(val[rt]<=x){a=rt;split(rc[a],rc[a],b,x);}else{b=rt;split(lc[b],a,lc[b],x);}pushup(rt);
}
void merge(int&rt,int a,int b) {
    if(!a||!b){rt=a|b;return;}
    if(key[a]>key[b]){rt=a;merge(rc[rt],rc[rt],b);}else{rt=b;merge(lc[rt],a,lc[rt]);}pushup(rt);
}
inline void ins(int&rt,int x){int a,b;split(rt,a,b,x);merge(a,a,newnode(x));merge(rt,a,b);}
inline void del(int&rt,int x){int a,b;split(rt,a,b,x);split(a,a,rt,x-1);merge(rt,a,b);}
inline int query(int&rt,int l,int r){int a,b,ans;split(rt,a,b,r);split(a,a,rt,l-1);ans=s[rt];merge(a,a,rt);merge(rt,a,b);return ans;}
}
const int maxs=13500028;
int tree[maxs],ch[maxs][2],cnt=1,rt,L,R;
inline int newnode(){tree[cnt]=ch[cnt][0]=ch[cnt][1]=0;return cnt;}
inline void init(){rt=1,L=0,R=1e+8;}inline void move(int d){rt=ch[rt][0]?ch[rt][0]:ch[rt][0]=newnode();if(d)L=(L+R>>1)+1;else R=L+R>>1;}
inline void ins(int x,int y){for(init();treap::ins(tree[rt],y),L!=R;move((L+R>>1)<x));}
inline void del(int x,int y){for(init();treap::del(tree[rt],y),L!=R;move((L+R>>1)<x));}
inline int rank(int l,int r,int x){int ans=0;for(init();L!=R;move((L+R>>1)<x))if((L+R>>1)<x)ans+=treap::query(tree[rt],l,r);return ans;}
inline int kth(int l,int r,int k){int tmp=0,x;for(init();L!=R;move(tmp+x>k),tmp+=tmp+x>k?0:x)x=treap::query(tree[rt],l,r);return L;}
inline int pre(int l,int r,int x){int k=rank(l,r,x)-1;return k?kth(l,r,k):-2147483658;}
inline int nxt(int l,int r,int x){int k=rank(l,r,x+1);return k<=treap::query(tree[1],l,r)?kth(l,r,k):2147483647;}
int a[maxn],n,m,x,op,l,r;
int main() {
    std::scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)std::scanf("%d",&a[i]),ins(i,a[i]);
    for(;m;--m){
        std::scanf("%d",&op);
        switch(op){
            case 1:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",kth(l,r,x));break;
            case 2:std::scanf("%d%d",&l,&x);del(a[l],l);ins(x,l);a[l]=x;break;
            case 3:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",rank(l,r,x));break;
            case 4:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",pre(l,r,x));break;
            default:std::scanf("%d%d%d",&l,&r,&x);std::printf("%d\n",nxt(l,r,x));break;
        }
    }
    return 0;
}
@WA王子  2021-06-11 12:59 回复 举报

不压行版(某位神仙帮我调的):

#include<cstdio>
#include<cstdlib>
#include<ctime>
const int maxn=500001;
namespace treap
{
    int val[maxn],lc[maxn],rc[maxn],s[maxn],cnt;short key[maxn];
    inline int newnode(int x)
    {
        val[++cnt]=x,
        lc[cnt]=rc[cnt]=0,
        s[cnt]=1,
        key[cnt]=rand();
        return cnt;
    }
    inline void pushup(int x)
    {
        s[x]=s[lc[x]]+s[rc[x]]+1;
    }
    void split(int rt,int&a,int&b,int x)
    {
        if(!rt){a=b=0;return;}
        if(val[rt]<=x)
            a=rt,split(rc[a],rc[a],b,x);
        else 
            b=rt,split(lc[b],a,lc[b],x);
        pushup(rt);
    }
    void merge(int&rt,int a,int b)
    {
        if(!a||!b){rt=a|b;return;}
        if(key[a]>key[b])
            rt=a,merge(rc[rt],rc[rt],b);
        else
            rt=b,merge(lc[rt],a,lc[rt]);
        pushup(rt);
    }
    inline void ins(int&rt,int x)
    {
        int a,b;
        split(rt,a,b,x);
        merge(a,a,newnode(x));
        merge(rt,a,b);
    }
    inline void del(int&rt,int x)
    {
        int a,b;split(rt,a,b,x);
        split(a,a,rt,x-1);
        merge(rt,a,b);
    }
    inline int query(int&rt,int l,int r)
    {
        int a,b,ans;
        split(rt,a,b,r);
        split(a,a,rt,l-1);
        ans=s[rt];merge(a,a,rt);
        merge(rt,a,b);
        return ans;
    }
}
const int maxs=13500028;
int tree[maxs],ch[maxs][2],cnt=1,rt,L,R;
inline int newnode()
{
    tree[cnt]=ch[cnt][0]=ch[cnt][1]=0;
    return cnt;
}
inline void init()
{
    rt=1,L=0,R=1e+8;
}
inline void move(int d)
{
    rt=ch[rt][0]?ch[rt][0]:ch[rt][0]=newnode();
    if(d)L=(L+R>>1)+1;
    else R=L+R>>1;
}
inline void ins(int x,int y)
{
    for(init();treap::ins(tree[rt],y),L!=R;move((L+R>>1)<x));
}
inline void del(int x,int y)
{
    for(init();treap::del(tree[rt],y),L!=R;move((L+R>>1)<x));
}
inline int rank(int l,int r,int x)
{
    int ans=0;
    for(init();L!=R;move((L+R>>1)<x))
        if((L+R>>1)<x)
            ans+=treap::query(tree[rt],l,r);
    return ans;
}
inline int kth(int l,int r,int k)
{
    int tmp=0,x;
    for(init();L!=R;move(tmp+x>k),tmp+=tmp+x>k?0:x)
        x=treap::query(tree[rt],l,r);
    return L;
}
inline int pre(int l,int r,int x)
{
    int k=rank(l,r,x)-1;
    return k?kth(l,r,k):-2147483658;
}
inline int nxt(int l,int r,int x)
{
    int k=rank(l,r,x+1);
    return k<=treap::query(tree[1],l,r)?kth(l,r,k):2147483647;
}
int a[maxn],n,m,x,op,l,r;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),ins(i,a[i]);
    for(;m;--m)
    {
        scanf("%d",&op);
        switch(op)
        {
            case 1:
                scanf("%d%d%d",&l,&r,&x);
                printf("%d\n",kth(l,r,x));
                break;
            case 2:
                scanf("%d%d",&l,&x);
                del(a[l],l);
                ins(x,l);
                a[l]=x;
                break;
            case 3:
                scanf("%d%d%d",&l,&r,&x);
                printf("%d\n",rank(l,r,x));
                break;
            case 4:
                scanf("%d%d%d",&l,&r,&x);
                printf("%d\n",pre(l,r,x));
                break;
            default:
                scanf("%d%d%d",&l,&r,&x);
                printf("%d\n",nxt(l,r,x));
                break;
        }
    }
    return 0;
}
@WA王子  2021-06-11 13:18 回复 举报

艹,发现主函数内每个操作的编号就错了,但修改完仍然过不了样例

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。