rt.

下面这东西会 WA80pts，但是只要把 quy[Q+100] 就能过。就挺神奇，求个解释。

Record

#include <bits/stdc++.h>
using namespace std;
double _st = clock();
const int N = 1e5 + 5, V = 1e6 + 5, Q = 1e5 + 5, sqrtN = 1e3 + 5;
int n, m, a[N], dcc, low[N], dfn[N<<1], _dfn, _id, siz[N<<1], ans[Q];
vector<int> G[N], tr[N<<1];
stack<int> st;
void tarjan (int u) {
	st.push(u), low[u] = dfn[u] = ++_dfn;
	for (int v : G[u])
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				++_id; static int t;
				while (t != v)
					t = st.top(), st.pop(),
					tr[_id].push_back(t),
					tr[t].push_back(_id);
				tr[_id].push_back(u),
				tr[u].push_back(_id);
			}
		} else
			low[u] = min(low[u], dfn[v]);
}
int bel[N], blk, id[N], lsh[N];
struct block {
    int a[N], t[sqrtN][2];
    void add (int x, int y) {
        if (a[x]) t[bel[x]][a[x]&1]--;
        a[x] += y;
        if (a[x]) t[bel[x]][a[x]&1]++;
    }
    int ask (int x, bool opt) {
		int res = 0;
        for (int i = 1; i < bel[x]; i++) res += t[i][opt];
        for (int i = (bel[x]-1)*blk + 1; i <= x; i++)
            if (a[i]) res += (a[i]&1) == opt;
        return res;
    }
} t;
struct querys {
    int opt, l, r, y, id;
    bool operator < (querys xx) const { return bel[l] != bel[xx.l] ? l < xx.l : (bel[l] & 1 ? r < xx.r : r > xx.r); }
} quy[Q];
void dfs (int u, int fa) {
    if (u <= n) id[dfn[u] = ++_dfn] = u, siz[u] = 1;
    for (int v : tr[u]) if (v != fa)
        dfs(v, u), siz[u] += siz[v];
}
void add (int x) {
	t.add(a[id[x]], 1);
}
void del (int x) {
	t.add(a[id[x]], -1);
}
int main () {
	#ifdef LOCAL
	freopen("_1.in", "r", stdin);
	freopen("_1.out", "w", stdout);
	#else
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	#endif
	cin >> n >> m, blk = sqrt(n);
	for (int i = 1; i <= n; i++) cin >> a[i], lsh[i] = a[i], bel[i] = (i-1)/blk+1;
	_id = n;
	for (int i = 1, u, v; i <= m; i++)
		cin >> u >> v,
		G[u].push_back(v),
		G[v].push_back(u);
    sort(lsh+1, lsh+n+1);
    int lim = unique(lsh+1, lsh+n+1) - lsh-1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(lsh+1, lsh+lim+1, a[i]) - lsh;
	tarjan(1), _dfn = 0, dfs(1, 0);
	int q; cin >> q;
    for (int i = 1, x; i <= q; i++)
		cin >> quy[i].opt >> x >> quy[i].y,
		quy[i].y = upper_bound(lsh+1, lsh+lim+1, quy[i].y) - lsh - 1,
		quy[i].l = dfn[x], quy[i].r = dfn[x] + siz[x] - 1, quy[i].id = i;
    sort(quy+1, quy+q+1);
    for (int i = 1, l = 1, r = 0; i <= q; i++) {
        while (l > quy[i].l) add(--l);
        while (r < quy[i].r) add(++r);
        while (l < quy[i].l) del(l++);
        while (r > quy[i].r) del(r--);
        ans[quy[i].id] = t.ask(quy[i].y, quy[i].opt);
    }
	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
	cerr << (clock()-_st)/CLOCKS_PER_SEC << 's';
	return 0;
}
*/