【luogu P8375】游戏（思维）（线段树）

给你 n 个点排成一列，前面 k 个是特殊点，而且每个特殊点会连一条有向边向下一个特殊点（如果下一个不是特殊点就不连）。
然后每次会加一条有向边，然后问你在什么时候开始出现了一个环包含了特殊点。

首先要知道普通图加边动态判环好像是 NP 还是 NP-hard 的，所以我们考虑它有的特殊性质。
也就是前面的一段边。

那我们发现只要前面的那些特殊点能从 i i i 走到 j j j 而且 i ⩾ j igeqslant j i⩾j 即可。
那我们考虑对于每个点维护 L i , R i L_i,R_i Li​,Ri​ 分别表示到能到它的编号最大的特殊点，和它能到的编号最小的特殊点。
那不难看出如果你在加边 x → y xrightarrow y x→y 的时候发现 L x ⩾ R y L_xgeqslant R_y Lx​⩾Ry​ 那就找到环了。
（只用看这个位置是因为如果别的地方满足了它之前一定没有满足，那它一定是走这里满足的，所以这里一定也是会满足的）

那问题就是你要怎么维护，通过势能分析我们会发现如果硬要维护每个位置的 L , R L,R L,R 一定是不行的。
那我们考虑怎么维护，其实我们会发现上面那个条件可以看做是自己的区间是否是空的，有这么一个想法就是因为你只需要保证这个区间空或否即可。
那就有一个想法就是你给这个区间弄一棵线段树之类的（不用真的建出来），然后每次只有当更新的值超过了中间线，你才更新左右端点。
那这样每个点的区间弄 log ⁡ n log n logn 次，那每次都修改至多 n log ⁡ n nlog n nlogn 也就可以通过了。

#include
#include

using namespace std;

const int N = 3e5 + 100;
int n, k, L[N], R[N];
//L[i] 到它的最大   R[i] 能到的最小 
vector  G[N], G_[N];
bool fin;

void init(int n_, int k_) {
	n = n_; k = k_; fin = 0;
	for (int i = 1; i <= n; i++) G[i].clear(), G_[i].clear();
	for (int i = 1; i <= n; i++) {
		if (i <= k) L[i] = R[i] = i;
			else L[i] = 0, R[i] = k + 1; 
	}
}

void check(int x, int y);

void update(int x) {
	for (int i = 0; i < G[x].size(); i++) check(x, G[x][i]);
	for (int i = 0; i < G_[x].size(); i++) check(G_[x][i], x);
}

void check(int x, int y) {
	if (L[x] >= R[y]) {fin = 1; return ;}
	int midx = (L[x] + R[x]) >> 1, midy = (L[y] + R[y]) >> 1;
	if (L[x] > midy) L[y] = midy + 1, update(y);
	if (midx >= R[y]) R[x] = midx, update(x);
	return ;
}

int add_teleporter(int u, int v) {
	u++; v++; G[u].push_back(v); G_[v].push_back(u);
	check(u, v); return fin;
}