Clarke and hunger games

Accepts: 2 Submissions: 54 Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 问题描述

克拉克是一名人格分裂患者。某一天，克拉克fork出了很多个克拉克，居住在nn个社区里。 克拉克由于自己的抖M属性，所以克拉克们决定玩饥饿游戏。 由于克拉克们住在天空之城中，所以他们相互联系靠的是社区之间的桥。 克拉克是非常节约的，两个社区能相互可达时只有一条路径，这样就节约了不少金钱。 饥饿游戏的规则是这样的：每一个社区选出两个人，然后作为供品去参加死亡比赛，最终活下一个人，并终身获得自由，获得无限的荣誉和金钱。 克拉克们想知道选出的人中有多少种组合。两个组合相同当且仅当选出的人都相同。 由于克拉克的抖M属性，克拉克还有qq次操作： 1 \ u \ v1uv：在u, vu,v两个社区之间建桥。如果u, vu,v已经有路径或u=vu=v相连则忽略。 2 \ u \ v2uv：删除u, vu,v两个社区的之间的桥。如果u, vu,v之间没有桥或u=vu=v则忽略。 3 \ h3h：变回到第hh次操作后的状态，当h=0h=0时表示回到初始状态，即社区之间是没有桥的。 4 \ u \ v4uv：询问uu到vv路径上的所有社区（包括uu和vv）每个社区选出人参加比赛的方案数（如果不存在路径输出00），由于方案数太多，所以求出对10^9+710​9​​+7取模的答案。 5 \ u \ s5us：社区uu中的克拉克的数量变为ss。一开始克拉克的社区之间是没有桥的。

输入描述

第一行一个整数T(1 \le T \le 5)T(1≤T≤5)，表示数据的组数。 每组数据第一行有两个整数n, q(1 \le n, q \le 3*10^5)n,q(1≤n,q≤3∗10​5​​)。 第二行有nn个整数，第ii个数a_i(0 \le a_i \le 10^4)a​i​​(0≤a​i​​≤10​4​​)表示第ii个社区的人数。接下来qq行，第ii个询问的第一个数为optopt。 当opt=1opt=1时，后面接着两个整数u_i, v_iu​i​​,v​i​​。 当opt=2opt=2时，后面接着两个整数u_i, v_iu​i​​,v​i​​。 当opt=3opt=3时，后面接着一个整数h_ih​i​​。 当opt=4opt=4时，后面接着两个整数u_i, v_iu​i​​,v​i​​。 当opt=5opt=5时，后面接着两个整数u_i, s_iu​i​​,s​i​​。1 \le u_i, v_i \le n, 0 \le h_i < i, 0 \le s_i \le 10^41≤u​i​​,v​i​​≤n,0≤h​i​​<i,0≤s​i​​≤10​4​​

输出描述

对于每组数据的opt=4opt=4，输出一个整数表示答案。

输入样例

13 51 2 31 1 22 1 23 15 1 34 1 2

输出样例

3

lct，对于回退操作，直接暴力处理，建立一棵操作树，每个操作最多正着，反着执行一次，时间复杂度为2nlog(n)

#include <iostream>#include <cstdio>#include <set>#include <vector>#include <cstring>#include <algorithm>using namespace std;#define LL __int64#define LS(x) node[(x)].ch[0]#define RS(x) node[(x)].ch[1]#define P pair<int ,int>#define X first#define Y second#define PB push_backconst int N = 3 * 1e5 + 5;const int MOD = 1000000007;int a[N];set<P> used;set<P>::iterator it;struct LCT {struct Node {int fa, ch[2];bool rev;int size;void init(LL x) {fa = 0;rev = ch[0] = ch[1] = 0;size = (LL)x * (x - 1) / 2;}} node[N];bool is_root(int x) {return (LS(node[x].fa) != x && RS(node[x].fa) != x);}void down(int x) {if(node[x].rev) {node[LS(x)].rev ^= 1;node[RS(x)].rev ^= 1;swap(LS(x), RS(x));node[x].rev = 0;}}void up(int x) {node[x].size = (LL)a[x] * (a[x] - 1) / 2 * node[LS(x)].size % MOD * node[RS(x)].size % MOD;}void rotate(int x, bool kind) {int fx = node[x].fa;int ffx = node[fx].fa;node[fx].ch[!kind] = node[x].ch[kind];node[node[x].ch[kind]].fa = fx;if(!is_root(fx))node[ffx].ch[RS(ffx) == fx] = x;node[x].fa = ffx;node[x].ch[kind] = fx;node[fx].fa = x;up(fx);}int d_st[N], ds_top;void splay(int x) {ds_top = -1;d_st[++ds_top] = x;for(int i = x; !is_root(i); i = node[i].fa)d_st[++ds_top] = node[i].fa;for(int i = ds_top; i >= 0 ; --i) down(d_st[i]);while(!is_root(x)) {int fx = node[x].fa;int ffx = node[fx].fa;bool rot_x = (LS(fx) == x);bool rot_fx = (LS(ffx) == fx);if(is_root(fx)) rotate(x, rot_x);else {if(rot_x == rot_fx) rotate(fx, rot_fx);else rotate(x, rot_x);rotate(x, rot_fx);}}up(x);}void access(int x) {int last = 0;while(x) {splay(x);RS(x) = last;last = x;x = node[x].fa;}}//access(x); splay(x); 后x在根的位置，此时x只有左子树，没有右子树，打翻转标记就是使得左子树变到右子树上。void make_root(int x) {access(x); splay(x);node[x].rev ^= 1;}int find(int x) {access(x); splay(x);while(LS(x)) x = LS(x);return x;}bool cut(int x, int y) {if(x > y) swap(x, y);it = used.find(P(x, y));if(it == used.end()) return false;make_root(x);access(y); splay(y);LS(y) = node[x].fa = 0;up(y);used.erase(it);return true;}bool link(int x, int y) {if(x > y) swap(x, y);int fx = find(x);int fy = find(y);if(fx == fy) return false;make_root(x);node[x].fa = y;used.insert(P(x, y));return true;}void init(int n) {for(int i = 0; i <= n; ++i)node[i].init(a[i]);node[0].size = 1;}void debug(int n) {for(int i = 0; i <= n; ++i) {cout<<i<<": "<<node[i].size<<' '<<node[i].fa<<' '<<node[i].ch[0]<<' '<<node[i].ch[1]<<endl;}}int get_ans(int x, int y) {int fx = find(x);int fy = find(y);if(fx != fy) return 0;make_root(x);access(y); splay(y); return node[y].size;}void dfs(int);} lct;vector<int> G[N];int opt[N], u[N], v[N];vector<P> ans;void LCT::dfs(int x) {for(int i = 0; i < G[x].size(); ++i) {int y = G[x][i];if(opt[y] == 1) {bool flag = link(u[y], v[y]);dfs(y);if(flag) cut(u[y], v[y]);} else if(opt[y] == 2) {bool flag = cut(u[y], v[y]);dfs(y);if(flag) link(u[y], v[y]);} else if(opt[y] == 4) {//ans[y] = get_ans(u[y], v[y]);ans.PB(P(y, get_ans(u[y], v[y])));dfs(y);} else if(opt[y] == 5) {int tmp = a[u[y]];a[u[y]] = v[y];node[u[y]].size = (LL)v[y] * (v[y] - 1) / 2;access(u[y]); splay(u[y]);dfs(y);a[u[y]] = tmp;node[u[y]].size = (LL)tmp * (tmp - 1) / 2;access(u[y]); splay(u[y]);}}}void gao(int n, int q) {lct.dfs(0);sort(ans.begin(), ans.end());for(int i = 0; i < ans.size(); ++i) {printf("%d\n", ans[i].Y);}}void init(int n, int q) {lct.init(n);//lct.debug(n);for(int i = 0; i <= q; ++i) {G[i].clear();}ans.clear();used.clear();}int main() {int T;scanf("%d", &T);while(T--) {int n, q;scanf("%d%d", &n, &q);a[0] = 0;for(int i = 1; i <= n; ++i) {scanf("%d", &a[i]);}init(n, q);int pre = 0;for(int i = 1; i <= q; ++i) {scanf("%d", &opt[i]);if(opt[i] != 3) {scanf("%d%d", &u[i], &v[i]);G[pre].PB(i);pre = i;} else {scanf("%d", &u[i]);pre = u[i];while(opt[pre] == 3) pre = u[pre];}}gao(n, q);}return 0;}