人类智障科技

· · 个人记录

分块优化 BST（根号重构）

其原理大概就是根据 BST 在随机数据下单次操作复杂度为 O(\log n)，而递增等构造数据下会被卡至 O(n)。于是我们可以每隔 q\over k 次操作进行 k 次这样的处理（默认 n,q 同阶）：

这样的话，两次操作之间，如果数据保持递增（即每次插入操作都增加一层深度），所有时刻最大的深度（也即最大的时间复杂度）就大概是 O(\log n + {n\over k})。如果我们忽略这个 \log 的话，就是 O({n\over k})。因此，所有正常的查询、插入操作的复杂度之和为 O({n^2\over k})。

那么全局为 O({n^2\over k}+k\cdot n\log n)，由均值不等式可得当 k 取 \sqrt{n\over {\log n}} 时最优，复杂度为 O(n\sqrt{n\log n})。

代码很丑啊。但是关于朴素 BST 的部分没有任何改动，所以只看 main 函数就行了。

//这个科技真的很智障 qwq
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int siz[N],val[N],lc[N],rc[N],cnt[N];
int n,q;
int root = 1;
void insert(int& o, int v) {
  if (!o) {
    val[o = ++n] = v;
    cnt[o] = siz[o] = 1;
    lc[o] = rc[o] = 0;
    return;
  }
  siz[o]++;
  if (val[o] == v) {
    cnt[o]++;
    return;
  }
  if (val[o] > v) insert(lc[o], v);
  if (val[o] < v) insert(rc[o], v);
}
int deletemin(int& o) {
  if (!lc[o]) {
    int u = o;
    o = rc[o];
    return u;
  } else {
    int u = deletemin(lc[o]);
    siz[o] -= cnt[u];
    return u;
  }
}
void del(int& o, int v) {
  siz[o]--;
  if (val[o] == v) {
    if (cnt[o] > 1) {
      cnt[o]--;
      return;
    }
    if (lc[o] && rc[o]) {
      int t = deletemin(rc[o]);
      lc[t] = lc[o];
      rc[t] = rc[o];
      siz[t] = siz[o];
      o = t;
    }
    else o = lc[o] + rc[o];
    return;
  }
  if (val[o] > v) del(lc[o], v);
  if (val[o] < v) del(rc[o], v);
}
int queryrnk(int o, int v) {
  if (val[o] == v) return siz[lc[o]] + 1;
  if (val[o] > v){
    if(lc[o]) return queryrnk(lc[o], v);
    else return 0;
  }
  if (val[o] < v){
    if(rc[o]) return queryrnk(rc[o], v) + siz[lc[o]] + cnt[o];
    else return siz[lc[o]]+cnt[o];
  }
  return 0;
}
int querykth(int o, int k) {
  if (siz[lc[o]] >= k) return querykth(lc[o], k);
  if (siz[lc[o]] < k - cnt[o]) return querykth(rc[o], k - siz[lc[o]] - cnt[o]);
  return val[o];
}
int getnum(int v,int k){
    if(!v) return 0;
    if(val[v]==k) return cnt[v];
    if(val[v]<k) return getnum(rc[v],k);
    if(val[v]>k) return getnum(lc[v],k);
}
int rd(){
    char c = 0;
    int res = 0,f = 1;
    while(!isdigit(c)){
        c = getchar();
        if(c=='-') f = -1;
    }
    while(isdigit(c)){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res*f;
}
// here,we designed decompose on BST
int K,cur;
vector<int>ta,tb;
int main(){
    q = rd();
    K = sqrt(q*1.0/((log2(q)+0.5)))+0.5;
    insert(root,1e9);
    root = 1;
    insert(root,-1e9);
    root = 1;
    for(int _=0;_<q;++_){
        cur++;
        int op = rd();
        int x = rd();
        if(op==1){
            insert(root,x);
            ta.push_back(x);
        }
        if(op==2){
            del(root,x);
            tb.push_back(x);
        }
        if(op==3){
            printf("%d\n",queryrnk(1,x)-1);
        }
        if(op==4){
            printf("%d\n",querykth(1,x+1));
        }
        if(op==5){
            int t = queryrnk(1,x);//x 的排名"%d\n",querykth(1,t-1));
            else printf("%d\n",querykth(1,t));
        }
        if(op==6){
            int t = queryrnk(1,x);
            if(getnum(1,x)) printf("%d\n",querykth(1,t+getnum(1,x)));
            else printf("%d\n",querykth(1,t+1));
        }
        root = 1;
        //work here!
        if(cur*K>=q && n*log2(n)>q){
            cur = 0;
            for(int qq=1;qq<=n;++qq) val[qq] = 0;
            n = 0;
            insert(root,1e9);
            root = 1;
            insert(root,-1e9);
            root = 1;           
            random_shuffle(ta.begin(),ta.end());
            for(auto c:ta){
                insert(root,c);
                root = 1;
            }
            for(auto c:tb){
                del(root,c);
                root = 1;
            }
        }
    }
    return 0;
}

这份代码在 -O2 下可以通过普通平衡树，且最大点可以卡进 500 毫秒。然而，不开的情况下会 T 飞。