你有一棵线段树。
你还有一棵线段树。
Uhhhhhh……
你有一颗可持久化线段树

可以访问任意时刻的数据结构。
我们一般对“时间”概念不感兴趣。
不如说是把很多数据版本搓到一起,节省出时空。

可持久化线段树

Prob Hint
lydsy
3524-Poi2014-Couriers 其他数加起来出现的次数都没满足条件的数出现次数多
2588-Count on a tree 树状版本控制 a + b - lca(a,b) - fa[lca(a, b)]
2741-【FOTILE模拟赛】L 31NM会T。需要一个比较喵的分块……很woc的一个题
3932-CQOI2015-任务查询系统 我调了一上午。悄悄问蒟蒻,logN是哪个N
//3933任务查询系统

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
const int N = int(1e5 + 10) << 1, NL = N*25;
struct O{
    int t, p;
    bool operator<(const O& b)const {return t < b.t;}
}oo[N];
int n, m, s[NL], sz, ch[NL][2], rt[N], tt[N], mxp;
ll ws[NL], ans = 1;
int q1, q2;
inline void up(int o) {
    s[o] = s[ch[o][0]] + s[ch[o][1]];
    ws[o] = ws[ch[o][0]] + ws[ch[o][1]];
}
void change(int& o, int p, int l, int r) {
    o = ++sz;
    if (l == r) {
        s[o] = s[p] + q2;
        ws[o] = ll(s[o])*l;
        return;
    }
    memcpy(ch[o], ch[p], sizeof(ch[p]));
    int mid = (l + r) >> 1;
    if (q1 <= mid) change(ch[o][0], ch[p][0], l, mid);
    else change(ch[o][1], ch[p][1], mid + 1, r);
    up(o);
}
ll query(int o, int k, int l, int r) {
    if (l == r) return ll(std::min(k, s[o]))*l;
    int mid = (l + r) >> 1;
    if (k <= s[ch[o][0]]) return query(ch[o][0], k, l, mid);
    else return ws[ch[o][0]] + query(ch[o][1], k - s[ch[o][0]], mid + 1, r);
}
int main() {
//  freopen("input", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int s, e, p, x = 2*i - 1;
        scanf("%d%d%d", &s, &e, &p);
        oo[x].t = s, oo[x].p = p;
        ++x;
        oo[x].t = e + 1, oo[x].p = -p;
        mxp = std::max(mxp, p);
    }
    std::sort(oo + 1, oo + 1 + 2*n);
    for (int i = 1; i <= 2*n; i++) {
        q1 = oo[i].p;
        q2 = q1 > 0 ? 1 : -1;
        q1 = q1 > 0 ? q1 : -q1;
        change(rt[i], rt[i - 1], 1, mxp);
        tt[oo[i].t] = rt[i];
    }
    for (int i = 1; i <= m; i++) if (!tt[i]) tt[i] = tt[i - 1];
    while (m--) {
        int x, a, b, c;
        scanf("%d%d%d%d", &x, &a, &b, &c);
        int k = 1 + (a*ans + b)%c;
        printf("%lld\n", ans = query(tt[x], k, 1, mxp));
    }
}

可持久化并查集

看上去很厉害的样子,其实我们可以用主席树对它嘿嘿嘿。
fa[]放到主席树里再按秩合并即可。

Porb Hint
lydsy
3673-可持久化并查集 嘿嘿嘿
3674-可持久化并查集加强版 嘿嘿嘿嘿

注意一开始build会用去O(2n)个节点,所以nlogn是不够用的。
还有这个代码里没判已经联通的点的合并。如果不判,一个节点和自己不断合并可以破坏秩。
感谢nbc提高了我的姿势水平

//可持久化并查集加强版
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 2e5 + 10, NL = N*20;
int n, m, sz, fa[NL], ch[NL][2], s[NL], rt[N], ans;
void build(int& o, int l, int r) {
    o = ++sz;
    if (l == r) {
        fa[o] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(ch[o][0], l, mid);
    build(ch[o][1], mid + 1, r);
}
int get(int o, int l, int r, int x) {
    if (l == r) return o;
    int mid = l + r >> 1;
    if (x <= mid) return get(ch[o][0], l, mid, x);
    else return get(ch[o][1], mid + 1, r, x);
}
int find(int x, int o) {
    int i = x;
    do {
        x = i;
        i = fa[get(o, 1, n, x)];
    }while (i != x);
    return x;
}
int q1, q2;
void change(int& o, int p, int l, int r) {
    o = ++sz;
    if (l == r) {
        fa[o] = q2;
        return;
    }
    memcpy(ch[o], ch[p], sizeof(ch[p]));
    s[o] = s[p];
    int mid = (l + r) >> 1;
    if (q1 <= mid) change(ch[o][0], ch[p][0], l, mid);
    else change(ch[o][1], ch[p][1], mid + 1, r);
}
int main() {
    scanf("%d%d", &n, &m);
    build(rt[0], 1, n);
    int now = rt[0];
    for (int i = 1; i <= m; i++) {
        int t, x, y;
        scanf("%d%d", &t, &x);
        x ^= ans;
        if (t == 1) {
            scanf("%d", &y);
            y ^= ans;
            x = find(x, now), y = find(y, now);
            int px, py;
            if (s[px = get(now, 1, n, x)] < s[py = get(now, 1, n, y)]) std::swap(x, y);
            else if (s[px] == s[py]) s[px]++;
            q1 = y, q2 = x;
            change(rt[i], now, 1, n);
            now = rt[i];
        }
        else if (t == 2) {
            now = rt[x];
        }
        else {
            scanf("%d", &y);
            y ^= ans;
            printf("%d\n", ans = (find(x, now) == find(y, now)));
        }
        rt[i] = now;
    }
}