Poj3580 Super Memo（FHQ-Treap）

题面

题解

对于操作$1$，我们可以对于每个节点打一个$add$标记，下放就行了

对于操作2，可以参考这篇题解的上一篇，不赘述

对于操作4，可以将区间裂成两部分，然后再插入合并

对于操作5，可以将区间裂成三部分，删除其中一个部分，合并其他两部分

对于操作6，打一个$min$标记，具体可以看代码。

对于操作3，这个有点复杂，但是手玩可以发现，修改完后只是某两个断开的区间换了位置，只是断点不确定，算一下即可（细节有点多。）

#include <ctime>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 2e5 + 10;

int n, m, lc[N], rc[N], siz[N], val[N], pri[N], rev[N], add[N], mn[N], tot;

inline void rotate(int o) { std::swap(lc[o], rc[o]), rev[o] ^= 1; }

inline void __add(int o, int v) { val[o] += v, mn[o] += v, add[o] += v; }

inline void upt(int o) {

	siz[o] = siz[lc[o]] + siz[rc[o]] + 1, mn[o] = val[o];

	if(lc[o]) mn[o] = std::min(mn[o], mn[lc[o]]);

	if(rc[o]) mn[o] = std::min(mn[o], mn[rc[o]]);

}

inline int node(int x) {

	val[++tot] = x, pri[tot] = rand(), siz[tot] = 1, mn[tot] = x;

	return tot;

}

void pushdown(int o) {

	if(add[o]) {

		if(lc[o]) __add(lc[o], add[o]);

		if(rc[o]) __add(rc[o], add[o]);

		add[o] = 0;

	}

	if(rev[o]) {

		if(lc[o]) rotate(lc[o]);

		if(rc[o]) rotate(rc[o]);

		rev[o] = 0;

	}

}

void split(int o, int k, int &l, int &r) {

	if(!o) { l = r = 0; return ; } pushdown(o);

	if(siz[lc[o]] < k) l = o, split(rc[o], k - siz[lc[o]] - 1, rc[o], r);

	else r = o, split(lc[o], k, l, lc[o]);

	upt(o);

}

int merge(int l, int r) {

	if(!l || !r) return l + r;

	pushdown(l), pushdown(r);

	if(pri[l] < pri[r]) { rc[l] = merge(rc[l], r), upt(l); return l; }

	else { lc[r] = merge(l, lc[r]), upt(r); return r; }

}

int main () {

	read(n), srand(19260817);

	int x, y, l, r, k, rt = 0, D, T;

	for(int i = 1; i <= n; ++i)

		read(x), rt = merge(rt, node(x));

	read(m); char opt[10];

	for(int i = 1; i <= m; ++i) {

		scanf("%s", opt), read(x);

		if(opt[0] == 'A') {

			read(y), read(D);

			split(rt, y, l, r), split(l, x - 1, l, k);

			__add(k, D), rt = merge(merge(l, k), r);

		}

		if(opt[0] == 'R' && opt[3] == 'E') {

			read(y), split(rt, y, l, r), split(l, x - 1, l, k);

			rotate(k), rt = merge(merge(l, k), r);

		}

		if(opt[0] == 'R' && opt[3] == 'O') {

			read(y), read(T);

			T %= (y - x + 1);

			if(!T) continue;

			T = (y - x + 1) - T;

			split(rt, y, l, r), split(l, x - 1, l, k);

			split(k, T, k, D);

			rt = merge(merge(l, merge(D, k)), r);

		}

		if(opt[0] == 'I') read(y), split(rt, x, l, r), rt = merge(merge(l, node(y)), r);

		if(opt[0] == 'D') split(rt, x, l, r), split(l, x - 1, l, k), rt = merge(l, r);

		if(opt[0] == 'M') {

			read(y), split(rt, y, l, r), split(l, x - 1, l, k);

			printf("%d\n",mn[k]), rt = merge(merge(l, k), r);

		}

	}

	return 0;

}

巴特西

Poj3580 Super Memo（FHQ-Treap）

题面

题解

最新文章

热门文章