夏晓光(loveJY)的博客

佳衡&华清推荐

orzhq

首先拿到题看到强制在线有点虚...

不过仔细读题发现可以$O(mq)$,30pts好成绩

然后就是怎么离线....不太会啊

直接想正解...(ljh教育)

首先反向边,问题变成从1到每个点的单调递增

$f[i][j]$表示点i只走大于j的边走到i的最小最大边权是什么

然后求这个数组...我们盲猜有大部分值是相同的,所以可以用某些鬼畜手段使他不是$O(n^2)$的

然后你敏锐的发现,对于任何一条边,如果我们是从小到大去插入的,那么我们插入边i一定只会影响v

因为首先我们更新了v的答案,也就是f[v],而我们从v出走又要走比i更大的,所以一定不会再更新下去

那么我们就可以用一个动态开点线段树来搞这个东西,在左端点权值处记下右端点权值,然后相当于查询l,m中最小值是否小于r

code:

#include<iostream>
#include<cstdio>
#include<cstring>
using std::min;
using std::max;
const int MAXN = 3e5 + 7;

int f[MAXN];

namespace seg {
#define mid ((l+r)>>1)
	int root[MAXN], T, ls[MAXN * 30], rs[MAXN * 30], tr[MAXN * 30];
	inline void modify(int &k, int l, int r, int pos, int vl) {
		if(!k) {
			k = ++T;
			tr[k] = MAXN;
		}

		if(l == r) {
			tr[k] = min(tr[k], vl);
			return ;
		}

		if(pos <= mid)modify(ls[k], l, mid, pos, vl);
		else modify(rs[k], mid + 1, r, pos, vl);

		tr[k] = min(tr[ls[k]], tr[rs[k]]);
	}
	inline int query(int k, int l, int r, int L, int R) {
		if(!k)return MAXN;
		if(L <= l && R >= r)return tr[k];

		if(L > mid)return query(rs[k], mid + 1, r, L, R);
		else if(R <= mid)return query(ls[k], l, mid, L, R);
		else return min(query(ls[k], l, mid, L, R), query(rs[k], mid + 1, r, L, R));

	}
}
int n, m, k, w;
int main() {
	scanf("%d%d%d%d", &n, &m, &k, &w);
	memset(f, -1, sizeof(f));
	f[1] = 0;
	seg::tr[0] = MAXN;
	for(int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &v, &u);
		if(~f[u]) {//这个u可别离线啊
			// printf("%d %d %d %d %d\n", u, v, f[u], f[v], i);
			f[v] = max(f[v], u == 1 ? i : f[u]);
			//二者值最大
			seg::modify(seg::root[v], 1, m, f[v], i);
			//最大的r
		}
	}
	int pre = 0;
	for(int qwq = 1, x, l, r; qwq <= k; ++qwq) {
		scanf("%d%d%d", &x, &l, &r);
		if(w)x ^= pre, l ^= pre, r ^= pre;
		if(x == 1) {
			puts("1");
			++pre;
			continue;
		}
		int ans = seg::query(seg::root[x], 1, m, l, m);
		// printf("%d!\n", ans);
		if(ans <= r) {
			puts("1");
			++pre;
			continue;
		} else {
			puts("0");
		}
	}
	return 0;
}