http://codeforces.com/problemset/problem/175/F

tree.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define P (p << 1)
#define M ((L + R) >> 1)
#define INF 0xDEADBEE

using namespace std;
const int N = 100005;

struct SegmentTree {
	int n, *st, *lz;
	SegmentTree(int n): n(n) {
		st = new int[n << 2];
		lz = new int[n << 2];
		memset(st, 0, sizeof(int) * (n << 2));
		memset(lz, -1, sizeof(int) * (n << 2));
	}
	~SegmentTree() {
		delete[] st, lz;
	}
	void add(int i) {
		update(i, i + 1, query(i, i + 1) + 1);
	}
	void update(int a, int b, int x) {
		update(a, b - 1, x, 1, 0, n - 1);
	}
	inline void push(int p, int L, int R) {
		if (lz[p] != -1) {
			st[p] = lz[p] * (R - L + 1);
			if (L != R) {
				lz[P] = lz[P|1] = lz[p];
			}
			lz[p] = -1;
		}
	}
	inline void pull(int p) {
		st[p] = st[P] + st[P|1];
	}
	void update(int a, int b, int x, int p, int L, int R) {
		push(p, L, R);
		if (b < L || R < a) return;
		if (a <= L && R <= b) {
			lz[p] = x;
			push(p, L, R);
			return;
		}
		update(a, b, x, P, L, M);
		update(a, b, x, P|1, M+1, R);
		pull(p);
	}
	int query(int a, int b) {
		return query(a, b - 1, 1, 0, n - 1);
	}
	int query(int a, int b, int p, int L, int R) {
		push(p, L, R);
		if (b < L || R < a) return 0;
		if (a <= L && R <= b) return st[p];
		int q = query(a, b, P, L, M) + query(a, b, P|1, M+1, R);
		pull(p); return q;
	}
};

int n, m;
int good[N], gpos[N], chain[N];
int *evil[N], egrp[N], epos[N], last[N];
int mlife[N]; // life death mega array
int st[N << 2]; bool lz[N << 2];
SegmentTree *death[N];
// always choose life

inline void push(int p, int L, int R) {
	if (lz[p]) {
		if (L == R) {
			if (st[p] == mlife[L])
				mlife[L] = st[p] = 0;
			else {
				st[p] = 0;
				death[L]->update(0, last[L], 0);
			}
		}
		if (L != R) {
			st[p] = 0;
			lz[P] = lz[P|1] = true;
		}
		lz[p] = false;
	}
}

inline void pull(int p) {
	st[p] = st[P] + st[P|1];
}

void add_life(int i, int p = 1, int L = 0, int R = m - 1) {
	push(p, L, R);
	if (L == R) {
		st[p] = min(++mlife[i], death[good[i]]->query(0, last[i]));
	}
	else {
		if (i <= M) add_life(i, P, L, M);
		else add_life(i, P|1, M+1, R);
		pull(p);
	}
}

void res(int i, int p = 1, int L = 0, int R = m - 1) {
	push(p, L, R);
	if (L == R) {
		st[p] = min(mlife[i], death[good[i]]->query(0, last[i]));
	}
	else {
		if (i <= M) res(i, P, L, M);
		else res(i, P|1, M+1, R);
		pull(p);
	}
}

inline void systemize(int u) {
	res(gpos[u]);
}

void reset(int a, int b, int p = 1, int L = 0, int R = m - 1) {
	push(p, L, R);
	if (b-1 < L || R < a) return;
	if (a <= L && R <= b-1) {
		lz[p] = 0;
		push(p, L, R);
		return;
	}
	reset(a, b, P, L, M);
	reset(a, b, P|1, M+1, R);
	pull(p);
}

int query(int a, int b, int p = 1, int L = 0, int R = m - 1) {
	push(p, L, R);
	if (b-1 < L || R < a) return 0;
	if (a <= L && R <= b-1) return st[p];
	int q = query(a, b, P, L, M) + query(a, b, P|1, M+1, R);
	pull(p); return q;
}

vector<int> getpath(int a, int aa, int bb, int b, int L0, int R0, int L1, int R1, bool straight) {
	int gnomes = 0;
	int path = 0;
	int ea = egrp[a];
	int eb = egrp[b];
	int ga = gpos[aa];
	int gb = gpos[bb];
	SegmentTree *da = death[ea];
	SegmentTree *db = death[eb];
	gnomes += da->query(L0, R0);
	gnomes += db->query(L1, R1);
	path += R0 - L0 + R1 - L1;
	
	if (!straight) swap(ga, gb);
		
	if (ga < gb) { // straight path
		gnomes += query(ga, gb);
		path += gb - ga;
	} else { // circular path
		gnomes += query(ga, n) + query(0, gb);
		path += n - ga + gb;
	}
	
	vector<int> lex;
	lex.push_back(gnomes);
	lex.push_back(path);
	if (L0 != R0)
		lex.push_back(evil[ea][L0 + 1]);
	if (ga != gb)
		lex.push_back(good[(ga + 1) % n]);
	if (L1 != R1)
		lex.push_back(evil[eb][L1 + 1]);
	return lex;
}

int destroy(int a, int b) {
	// no need to destroy
	if (a == b) return 0;
	
	// gather breakpoints
	int ga = gpos[a], a1 = a, a2 = a, ap = 0, aq = 0;
	int gb = gpos[b], b1 = b, b2 = b, bp = 0, bq = 0;

	// what if we can just traverse the evil path?
	vector<int> ss;
	int s1 = INF;
	int s2 = INF;
	
	if (!~ga && !~gb && egrp[a] == egrp[b]) {
		// same evil!
		int E = egrp[a];
		int ea = epos[a];
		int eb = epos[b];
		s1 = min(ea, eb);
		s2 = max(ea, eb);
		int sp = s2 - s1;
		int sg = death[E]->query(s1, s2);
		ss.push_back(sg);
		ss.push_back(sp);
		
		if (ea < eb) {
			ss.push_back(evil[E][ea + 1]);
			if (ea + 2 <= eb)
				ss.push_back(evil[E][ea + 2]);
		}
		else {
			ss.push_back(evil[E][ea - 1]);
			if (ea - 2 >= eb)
				ss.push_back(evil[E][eb - 2]);
		}
		
	} else {
		ss.push_back(INF);
	}
	
	if (!~ga) {
		int E = egrp[a];
		a1 = evil[E][0];
		aq = last[E];
		a2 = evil[E][aq];
		ap = epos[a];
	}
	
	if (!~gb) {
		int E = egrp[b];
		b1 = evil[E][0];
		bq = last[E];
		b2 = evil[E][bq];
		bp = epos[b];
	}
	// get pair lex
	vector<int> 
		p11 = getpath(a, a1, b1, b, 0, ap, 0, bp, 0),
		p11s = getpath(a, a2, b1, b, 0, ap, 0, bp, 1),
		p12 = getpath(a, a1, b2, b, 0, ap, bp, bq, 0),
		p12s = getpath(a, a1, b2, b, 0, ap, bp, bq, 1),
		p21 = getpath(a, a2, b1, b, ap, aq, 0, bp, 0),
		p21s = getpath(a, a2, b1, b, ap, aq, 0, bp, 1),
		p22 = getpath(a, a2, b2, b, ap, aq, bp, bq, 0),
		p22s = getpath(a, a2, b2, b, ap, aq, bp, bq, 1);
	
	vector<int> mn = min(ss, min(p11, min(p11s, min(p12, min(p12s, min(p21, min(p21s, min(p22, p22s))))))));
	ga = 0, gb = 0;
	int ea = egrp[a];
	int eb = egrp[b];
	if (ss == mn) {
		death[ea]->update(s1, s2, 0);
	} else if (p11 == mn || p11s == mn) {
		if (a != a1) {
			death[ea]->update(0, epos[a], 0);
			systemize(ea);
		}
		if (b != b1) {
			death[eb]->update(0, epos[b], 0);
			systemize(eb);
		}
		ga = a1;
		gb = b1;
		if (p11s == mn) swap(ga, gb);
	} else if (p12 == mn || p12s == mn) {
		if (a != a1) {
			death[ea]->update(0, epos[a], 0);
			systemize(ea);
		}
		if (b != b2) {
			death[eb]->update(epos[b], last[eb], 0);
			systemize(eb);
		}
		ga = a1;
		gb = b2;
		if (p12s == mn) swap(ga, gb);
	} else if (p21 == mn || p21s == mn) {
		if (a != a2) {
			death[ea]->update(epos[a], last[ea], 0);
			systemize(ea);
		}
		if (b != b1) {
			death[eb]->update(0, epos[b], 0);
			systemize(eb);
		}
		ga = a2;
		gb = b1;
		if (p21s == mn) swap(ga, gb);
	} else if (p22 == mn || p22s == mn) {
		if (a != a2) {
			death[ea]->update(epos[a], last[ea], 0);
			systemize(ea);
		}
		if (b != b2) {
			death[eb]->update(epos[b], last[eb], 0);
			systemize(eb);
		}
		ga = a2;
		gb = b2;
		if (p22s == mn) swap(ga, gb);
	}
	ga = gpos[ga];
	gb = gpos[gb];
	
	if (ga < gb) { // straight path
		reset(ga, gb);
	} else { // circular path
		reset(ga, n);
		reset(0, gb, 0);
	}
	// print(mn);
	return mn[0];
}

int main() {
	memset(gpos, -1, sizeof gpos);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d", good + i);
		gpos[good[i]] = i;
	}
	for (int i = 0; i < m; ++i) {
		int k; scanf("%d", &k);
		int *ef = new int[k];
		for (int j = 0; j < k; ++j)
			scanf("%d", &ef[j]);
		if (ef[0] % m != ef[k - 1] - 1)
			reverse(ef, ef + k);
		evil[ef[0]] = ef;
		last[ef[0]] = k - 1;
		death[ef[0]] = new SegmentTree(k - 1);
		for (int j = 0; j < k; ++j) {
			epos[ef[j]] = j;
			egrp[ef[j]] = ef[0];
		}
	}
	char c[2]; int q, a, b;
	scanf("%d\n", &q);
	while (q--) {
		scanf("%s%d%d", c, &a, &b);
		if (c[0] == '+') {
			int ga = gpos[a];
			int gb = gpos[b];
			// cout << a << ' ' << b << endl;
			if (~ga && ~gb) {
				add_life(ga == m - 1 || ga < gb ? ga : gb);
			}
			else if (~ga) {
				// gb is evil
				int E = egrp[b];
				if (E == a) {
					death[E]->add(0);
					systemize(E);
				}
				else {
					death[E]->add(last[E]-1);
					systemize(E);
				}
			} else if (~gb) {
				// ga is evil
				// cout << a << ' ' << b << endl;
				int E = egrp[a];
				if (E == b) {
					death[E]->add(0);
					systemize(E);
				}
				else {
					death[E]->add(last[E]-1);
					systemize(E);
					// cout << death[E]->query(0, last[E]) << endl;
				}
			} else {
				// both evil
				death[egrp[a]]->add(min(epos[a], epos[b]));
				systemize(egrp[a]);
			}
			// cout << "done" << endl;
		} else {
			// query count
			printf("%d\n", destroy(a, b));
		}
		for (int i = 0; i < m; ++i)
			cout << query(i, i + 1) << ' '; cout << endl;
	}
}