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

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

可持久化线段树

ProbHint
lydsy
3524-Poi2014-Couriers其他数加起来出现的次数都没满足条件的数出现次数多
2588-Count on a tree树状版本控制 a + b - lca(a,b) - fa[lca(a, b)]
2741-【FOTILE模拟赛】L31NM会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[]放到主席树里再按秩合并即可。

PorbHint
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;
	}
}