题面

题解

你看这个条件，恰好为 $[l,r]$ 中的节点，信息量太少了啊 ！

在暴力的基础上，一般能想到分治，也就是先确定根，然后你起码知道根两边的区间彼此独立了，如果你再采用“两头往中间枚举”的方法，容易得到复杂度 $O(n\log n)$ 的解。

这个 2n 简直折磨人！还能有什么数据结构解决如此复杂的问题，能比二进制数据结构还强吗？

有，那就是单调栈：

我们像 $O(n)$ 建笛卡尔树那样，用单调栈确定这棵二叉搜索树的结构。每次判断一个点 $x$ 是否弹出时，我们如果假设不弹出，那么 $x$ 的区间是不知道的（通过前面的信息知道了左端点，但是不知道右端点），若 $x$ 点弹出，就说明走到头了，那么右端点一定是当前点 $i$ 的前一个点 $i-1$ ！

然后又可以根据最后一个弹出的点来确定 $i$ 区间的左端点，并在最后一个弹出的点和 $i$ 之间连一条边。复杂度 $O(n)$ 。

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second

#include"interact.h"
void guess(int n) {
	int st[MAXN],tp = 0;
	int l[MAXN];
	for(int i = 1;i <= n;i ++) {
		int p = 0;
		while(tp > 0 && query(st[tp],l[st[tp]],i-1)) {
			if(p) report(st[tp],p);
			p = st[tp --];
		}
		l[i] = i;
		if(p) report(p,i),l[i] = l[p];
		st[++ tp] = i;
	} int p = 0;
	while(tp > 0) {
		if(p) report(st[tp],p);
		p = st[tp --];
	}
	return ;
}