记录编号	394004	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]地图	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	2.169 s
提交时间	2017-04-12 17:45:00	内存使用	27.03 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 10;
const int MAXM = 1e6 + 10;
const int MAXB = 1e3 + 10;

#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	
	while (not is_num(tmp)) tmp = getchar();
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return res;
}

struct Edge {
	int to, ne;
	Edge() {}
	Edge(int to_, int ne_) { to = to_, ne = ne_; }
} e[MAXN << 2];
int head[MAXN], ecnt;
inline void add_edge(int fr, int to) {
	e[++ecnt] = Edge(to, head[fr]), head[fr] = ecnt;
	e[++ecnt] = Edge(fr, head[to]), head[to] = ecnt;
}

struct Question {
	int id, l, bl, r, y, type;
	Question() {}
	Question(int id_, int l_, int y_, int type_) { id = id_, l = l_, y = y_, type = type_; }
	
	bool operator < (const Question &b) const { return bl == b.bl ? r < b.r : bl < b.bl; }
} qs[MAXN];

int n, m, q;
int dfn[MAXN], ncnt; // tree to seq
vector <int> rings[MAXN]; // for tree
int rcnt;
int num_bsz, num_bcnt;
int node_bsz, node_bcnt;
int blk_sum[MAXB][2]; // for seq
int num_belong[MAXM]; // for seq
int node_belong[MAXN]; // for seq
int cnt[MAXM]; // for seq
int global_ans[MAXN]; 
int v[MAXN]; // for tree
int intree[MAXN]; // seq to tree
int size[MAXN];
int stack[MAXN], stop;
int max_v;

void tarjan(int now, int fa, int fa_e) {
	dfn[now] = ++ncnt;
	
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (to == fa and fa_e == (i & 1 ? i + 1 : i - 1)) continue;
		
		if (not dfn[to]) stack[++stop] = i, tarjan(to, now, i), stop--;
		else if (dfn[to] < dfn[now]) {
			rings[++rcnt].push_back(0), rings[rcnt].push_back(i);
			
			for (int j = stop; j >= 1; j--) {
				if (e[stack[j]].to == to) break;
				rings[rcnt].push_back(stack[j]);
			}
		}
	}
}

void check() {
	for (int now = 1; now <= max(n, ncnt); now++) {
		printf("now = %d sons:\n", now);
		for (int i = head[now]; i; i = e[i].ne) {
			int to = e[i].to;
			printf("%d ", to);
		}
		printf("\n");
	}
}

inline void handle() {
	// check();
	// printf("--------------------\n");
	tarjan(1, 0, 0);
	dfn[0] = MAXN;
	
	int rt;
	for (int i = 1; i <= rcnt; i++) {
		int sz = rings[i].size() - 1;
		rt = 0;
		
		for (int j = 1; j <= sz; j++) {
			int &tar = rings[i][j];
			int to = e[tar].to;
			
			if (dfn[to] < dfn[rt]) rt = to;
			
			e[tar].to = 0;
			if (tar & 1) e[tar + 1].to = 0;
			else e[tar - 1].to = 0;
			
			rings[i][j] = to;
		}
		
		add_edge(++n, rt);
		
		for (int j = 1; j <= sz; j++) {
			if (rings[i][j] != rt) add_edge(n, rings[i][j]);
		}
	}
	// check();
}

void dfs(int now, int fa) {
	size[now] = 1;
	dfn[now] = ++ncnt;
	intree[ncnt] = now;
	
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (to == fa or to == 0) continue;
		
		dfs(to, now);
		size[now] += size[to];
	}
}

inline void add(int tar) {
	int tar_v = v[tar];
	if (tar_v == 0) return;
	if (cnt[tar_v]++ == 0) blk_sum[num_belong[tar_v]][1]++;
	else {
		if (cnt[tar_v] & 1) blk_sum[num_belong[tar_v]][1]++, blk_sum[num_belong[tar_v]][0]--;
		else blk_sum[num_belong[tar_v]][1]--, blk_sum[num_belong[tar_v]][0]++;
	}
}

inline void del(int tar) {
	int tar_v = v[tar];
	if (tar_v == 0) return;
	if (--cnt[tar_v] == 0) blk_sum[num_belong[tar_v]][1]--;
	else {
		if (cnt[tar_v] & 1) blk_sum[num_belong[tar_v]][1]++, blk_sum[num_belong[tar_v]][0]--;
		else blk_sum[num_belong[tar_v]][1]--, blk_sum[num_belong[tar_v]][0]++;
	}
}

inline void cal(int tar) {
	int type = qs[tar].type;
	int top = qs[tar].y;
	int now = 1, res = 0;
	
	while (now * num_bsz <= top)
		res += blk_sum[now][type], now++;
	now--;
	
	for (int i = now * num_bsz + 1; i <= top; i++) if (cnt[i] and (not ((cnt[i] ^ type) & 1))) res++;
	global_ans[qs[tar].id] = res;
}

inline void make_block() {
	ncnt = 0;
	dfs(1, 0);
	int now_cnt;
	
	node_bsz = sqrt(1.0 * n), now_cnt = 1, node_bcnt = 1;
	for (int i = 1; i <= ncnt; i++) {
		if (now_cnt == node_bsz + 1) node_bcnt++, now_cnt = 1;
		node_belong[i] = node_bcnt;
		now_cnt++;
	}
	
	num_bsz = sqrt(1.0 * max_v), now_cnt = 1, num_bcnt = 1;
	for (int i = 1; i <= max_v; i++) {
		if (now_cnt == num_bsz + 1) num_bcnt++, now_cnt = 1;
		num_belong[i] = num_bcnt;
		now_cnt++;
	}
}

inline void read() {
	n = get_num(), m = get_num();
	for (int i = 1; i <= n; i++) v[i] = get_num(), max_v = max(v[i], max_v);
	
	int x, y, type;
	for (int i = 1; i <= m; i++) {
		x = get_num(), y = get_num();
		add_edge(x, y);
	}
	
	q = get_num();
	for (int i = 1; i <= q; i++) {
		type = get_num(), x = get_num(), y = get_num();
		qs[i] = Question(i, x, y, type);
	}
}

inline void solve() {
	handle();
	make_block();
	
	for (int i = 1; i <= q; i++) {
		qs[i].l = dfn[qs[i].l];
		qs[i].bl = node_belong[qs[i].l];
		qs[i].r = qs[i].l + size[intree[qs[i].l]] - 1;
	}
	sort(qs + 1, qs + q + 1);
	int now_l = 1, now_r = 1;
	add(1);
	
	for (int i = 1; i <= q; i++) {
		int l = qs[i].l, r = qs[i].r;
		while (now_l < l) del(intree[now_l++]);
		while (l < now_l) add(intree[--now_l]);
		while (r < now_r) del(intree[now_r--]);
		while (now_r < r) add(intree[++now_r]);
		
		cal(i);
	}
	
	for (int i = 1; i <= q; i++) printf("%d\n", global_ans[i]);
}

int main() {
#ifdef LOCAL
	freopen("test.in", "r", stdin);
#endif
	freopen("map_2016.in", "r", stdin);
	freopen("map_2016.out", "w", stdout);
	read();
	solve();
	return 0;
}