主席树

· · 个人记录

P3834 【模板】可持久化线段树 1（主席树）

前缀和差分什么的搞搞，搞出来区间的集合后二分即可。当然，要用可持久化权值线段树实现。

记得开大数组！

void modify(int L, int R, int pos, int &cur, int lstcur) {
    cur = ++ttot;
    ls[cur] = ls[lstcur], rs[cur] = rs[lstcur];//暂且先都连上，一会儿再改
    sum[cur] = sum[lstcur] + 1;
    if (L == R) return ;
    int mid = (L + R) >> 1;
    if (pos <= mid) modify(L, mid, pos, ls[cur], ls[lstcur]);//传ls[cur]的时候就已经把ls[cur]改了（因为cur = ++ttot)
    else    modify(mid + 1, R, pos, rs[cur], rs[lstcur]);
}

int query(int L, int R, int pos, int lcur, int rcur) {
    if (L == R) return L;
    int tmp = sum[ls[rcur]] - sum[ls[lcur]];
    int mid = (L + R) >> 1;
    if (pos <= tmp) return query(L, mid, pos, ls[lcur], ls[rcur]);
    else    return query(mid + 1, R, pos - tmp, rs[lcur], rs[rcur]);
}

...

int main() {

    ...

    rt[0] = ++ttot;

    ...
}

P2633 Count on a tree

考虑到主席树可以做一些前缀和差分的问题，因此最简单的方法是树上差分。

基础不行啊，调了这么长时间。还得好好敲树链剖分。。。 ## [P3168 [CQOI2015]任务查询系统](https://www.luogu.com.cn/problem/P3168) - 题意：先一波区间加：区间 $[l, r]$ 内添加 $x$ 这个数（l,...,r为一堆可重集合）；再一波单点查：集合 $x$ 的前k小之和。 差分板题。 区间加转化为双点加，单点查转化为查前缀和。 区间查好办，双点加的同时维护个 $siz$ 和 $sum$ 就行了。注意查的时候 ```if (L == R) return k * lsh_h[L];``` 双点加不好办，要用邻接表（应该是吧）。直接看代码吧。 ```cpp sort(opts + 1, opts + 1 + ocnt, cmp); int id = 1, lst = ++ttot; for (register int i = 1; i <= ocnt; ++i) { while (id != opts[i].pos) head[id] = lst, ++id; add(1, tot, opts[i].val, opts[i].type, lst, head[id]); lst = head[id]; } ``` 最后查 $head[x]$即可，就是说 $head[x]$ 相当于之前的 $rt[x]$ 了。 $Code$: ```cpp void add(int L, int R, int pos, int x, int lstcur, int &cur) { cur = ++ttot; ls[cur] = ls[lstcur], rs[cur] = rs[lstcur]; siz[cur] = siz[lstcur] + x, sum[cur] = sum[lstcur] + 1ll * x * lsh_h[pos]; if (L == R) return ; int mid = (L + R) >> 1; if (pos <= mid) add(L, mid, pos, x, ls[lstcur], ls[cur]); else add(mid + 1, R, pos, x, rs[lstcur], rs[cur]); } inline void add_opt() { for (register int i = 1; i <= m; ++i) { opts[i] = (operat){st[i], vl[i], 1}; opts[i + m] = (operat){ed[i] + 1, vl[i], -1}; } sort(opts + 1, opts + 1 + (m << 1), cmp); int id = 1, lst = ++ttot; for (register int i = 1; i <= (m << 1); ++i) { while (id != opts[i].pos) head[id] = lst, ++id; add(1, tot, opts[i].val, opts[i].type, lst, head[id]); lst = head[id]; } } ll ans; ll query(int L, int R, int k, int cur) { if (L == R) return k * lsh_h[L]; int tmp = siz[ls[cur]]; int mid = (L + R) >> 1; if (k <= tmp) return query(L, mid, k, ls[cur]); else return query(mid + 1, R, k - tmp, rs[cur]) + sum[ls[cur]]; } ``` ## 习题 - [P4197 Peaks](https://www.luogu.com.cn/problem/P4197) 难调！但是是克鲁斯卡尔重构树的板子。搞到重构树后，要用到主席树求区间第k大。（~~然后我因此调到即将自闭~~） ## 注意： 主席树的 $add(modify) $ 不要```if (!cur) cur=++ttot;```，而是要```cur=++ttot;```，因为上一层可能错误地改了 $ls[cur], rs[cur]$！！！不要和动态开点线段树弄混了！！ Continued...