郁闷的小 J------NB树

· · 题解

虽然此题有更好的做法，但是我就是那个 S*。

因为本人过于 stupid，写此题是还不会按值域去干嘛干嘛的。

所以写下了这份线段树维护区间，平衡树维护区间内的数的代码。

先说一下这样与分析时间复杂度。

线段树会将一个区间分为 x 个小区间。

将那些区间的编号为 K 的书的个数统计加起来就行啦。

你问我为什么不能用哈希表，因为就是那个 S*。因为我写的 Hash 如果模数小，那么会爆时间，模数大，数组大，会爆空间。

还不如指针平衡树。

先给份 treap 的代码。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100010];
struct node{
    node *l,*r;
    int val,cnt,siz;
};
struct tree{
    node *root,*null;
    inline tree(){
        null=new node;
        null->l=null->r=null;
        null->val=null->cnt=null->siz=0;
        root=null;
    }
    inline void update(node *p){
        p->siz=p->l->siz+p->r->siz+p->cnt;
    }
    inline void zig(node *&p){
        node *q=p->l;
        if(q==null) return;
        p->l=q->r,q->r=p,p=q;
        update(p->r),update(p);
    }
    inline void zag(node *&p){
        node *q=p->r;
        if(q==null) return;
        p->r=q->l,q->l=p,p=q;
        update(p->l),update(p);
    }
    inline int check(node *p){
        if(p->r->siz*0.6>=double(p->l->siz)) return 1;
        if(p->l->siz*0.6>=double(p->r->siz)) return 2;
        return 0;
    }
    void insert(int x,node *&p){
        if(p==null){
            p=new node;
            p->l=p->r=null;
            p->val=x;
            p->cnt=1;
            p->siz=1;
            return;
        }
        if(x==p->val) p->cnt++;
        else if(x<p->val) insert(x,p->l);
        else insert(x,p->r);
        update(p);
        int d=check(p);
        if(d==1) zag(p);
        if(d==2) zig(p);
    }
    void erase(int val,node *&p){
        if(p==null) return;
        if(val==p->val){
            if(p->cnt>1){
                p->cnt--,update(p);
                return;
            }
            if(p->l!=null || p->r!=null){
                if(p->r==null)
                    zig(p),erase(val,p->r);
                else
                    zag(p),erase(val,p->l);
                update(p);
            }
            else p=null;
            return;
        }
        if(val<p->val) erase(val,p->l);
        else erase(val,p->r);
        int d=check(p);
        if(d==1) zag(p);
        if(d==2) zig(p);
        update(p);
    }
    int count(int x,node *p){
        if(p==null) return 0;
        if(p->val==x) return p->cnt;
        if(x<p->val) return count(x,p->l);
        else return count(x,p->r);
    }
}t[400010];
inline void creat(int l,int r,int root){
    t[root]=tree();
    if(l==r){
        t[root].insert(a[l],t[root].root);
        return;
    }
    int mid=l+r>>1;
    creat(l,mid,root*2);
    creat(mid+1,r,root*2+1);
    for(int i=l;i<=r;i++) t[root].insert(a[i],t[root].root);
}
inline int update(int p,int k,int x=1,int y=n,int root=1){
    if(x==y && p==x){
        int u=t[root].root->val;
        t[root].root->val=k;
        return u;
    }
    int mid=x+y>>1,tot=0;
    if(p<=mid) tot=update(p,k,x,mid,root*2);
    else tot=update(p,k,mid+1,y,root*2+1);
    t[root].erase(tot,t[root].root);
    t[root].insert(k,t[root].root);
    return tot;
}
inline int ask(int l,int r,int k,int x=1,int y=n,int root=1){
    if(l<=x && y<=r) return t[root].count(k,t[root].root);
    int mid=x+y>>1,tot=0;
    if(l<=mid) tot+=ask(l,r,k,x,mid,root*2);
    if(mid<r) tot+=ask(l,r,k,mid+1,y,root*2+1);
    return tot;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline char chread(){
    char ch=getchar();
    while(!isalpha(ch)) ch=getchar();
    return ch;
}
inline void write(int x){
    if(x<10){
        putchar(x%10+'0');
        return;
    }
    write(x/10);
    putchar(x%10+'0');
}
int main() {
    srand(time(0));
    cin>>n>>m;
    for(int i=1;i<=n;i++) a[i]=read();
    creat(1,n,1);
    char ch;
    int l,r;
    while(m--){
        ch=chread();
        l=read(),r=read();
        if(ch=='C') update(l,r),a[l]=r;
        if(ch=='Q'){
            int k;
            cin>>k;
            write(ask(l,r,k));
            putchar('\n');
        }
    }
    return 0;
}

空间 O(n\log n)，时间 O(n\log^2n)。

忽略常数，在 n=10^5 的情况下，时间复杂度为 O(2.56\times 10^7)。

因为树套树常数位两树之积，因为这两位都是大常数选手，所以直接爆炸。

在这种情况下，你知道 treap 靠什么吗？

天，赐，良，机！

机，主要指随机数，次要指评测机。

然后这份代码再也 A 不掉了。

换上替罪羊树，我们继续作战。

虽然替罪羊是个基于暴力的树。

但是常数比我写的很多树都小。

先试下 \alpha=0.75，然后寄了。

没事，\alpha=0.8 可 A。

所以说，平衡树的一些参数对时间很重要。

这是我写的 treap。

这是我写的替罪羊树。