鲜花

这题曾经出现在几百年前我们的校内模拟赛中，然而数据量比这里狂野，各种 $\log$ 叠得比天高的做法都被卡掉了。

分析

首先，一个很自然的想法是求出所有不和谐对，然而这样的对数显然可以被卡到 $n^2$，被灭掉了。

然后，我们发现题目只要求出一个所求的不和谐对，所以我们可以不用保留那么多对。考虑不和谐对中右端点相同的某些对，为了其能够套在询问的 $[l,r]$ 区间中，我们显然可以并且需要只保留左端点位置最右的对，因为其他的不和谐对比这个对更大，更难套进去。也就是说，我们只要对每个右端点 $i$ 求出最近的左端点 $j$ 使得 $(j,i)$ 是一对不和谐对，然后保留这些对即可。显然这些对的个数是 $O(n)$ 的。

那怎么求呢？设 $x < i$ 为最后一个点满足 $a_x \ne a_i$，$y < i$ 为最后一个点满足 $b_y \ne b_i$， 这两个东西是好维护的。那么答案 $j$ 必定 $\le \min(x,y)$。如果 $\min(x,y)$ 就是答案，那我们就找到了。可要是不是呢？

别急，我们先画个示意：

$\text{\:i\hspace{0.81cm} ii\hspace{0.81cm}iii}$

$\text{\textcolor{FFFF00}{C}\textcolor{EE0000}{A\ldots AA\ldots A}}$

$\text{\textcolor{66CCFF}{B}X\ldots \textcolor{00FFCC}{D}\textcolor{66ccFF}{B\ldots B}}$

如此所示，首先容易知道此时不可能 $x = y$，不妨设 $x < y$，当 $\min(x,y) = x$ 不是答案时，其肯定是 $b_i = b_x$，即 $\text{(i)}$ 处和 $\text{(iii)}$ 处的情况。然而，这时候，我们把目光投向 $y$ 位置，即 $\text{(ii)}$ 处，发现首先由 $x$ 的定义有 $a_y = a_i \ne a_x$，然后由 $y$ 的定义有 $b_y \ne b_i = b_x$，所以我们得到了 $\text{(i)}$ 处与 $\text{(ii)}$ 处，也就是 $x$ 和 $y$ 两个位置构成一对不和谐对。由于答案的左端点 $< x$，所以答案必定包含 $(x,y)$，劣于 $(x,y)$，而 $(x,y)$ 或其包含的更小对一定在算 $y$ 位置的答案时及之前被算过了，所以我们可以不用管 $i$ 的答案，直接跳过即可。$y < x$ 同理。

处理出所有有用的对后，怎么处理询问呢？由于是个静态问题，没必要上什么 DS。我们只需要用求前缀最大值的方法预处理一个数组 $P_i$，表示前 $i$ 个位置对应的不和谐对的左端点最大值，同时记录出这个最大左端点对应的右端点 $R_i$。询问 $[l,r]$ 时，直接判断是否 $l \le P_r$ 即可，是则输出 $(P_r,R_r)$，否则输出 $(0,0)$。

总复杂度 $O(n)$。

代码

由于我若只了，硬生生把询问写成了离线下来扫描线，不过总复杂度还是 $O(n)$。

#include <bits/stdc++.h>
#define GET (c = getchar_unlocked())
using namespace std;
inline int read(){
	int lty = 0;bool flag = false;
	char c;GET;
	while((c > '9' || c < '0') && c != '-') GET;
	if(c == '-') flag = true,GET;
	while('0' <= c && c <= '9') lty = (lty << 1) + (lty << 3) + (c ^ '0'),GET;
	if(flag) lty = -lty;
	return lty;
}
inline void wr(int x,char c = '\n'){ // no minus
	if(!x){
		putchar('0');putchar(c);
		return;
	}
	int cnt = 0;
	static char buf[105];
	while(x) buf[++cnt] = (x % 10) ^ '0',x /= 10;
	while(cnt) putchar(buf[cnt--]);
	putchar(c);
}
int a[100005];
int b[100005];
int o[100005];
vector<pair<int,int> > q[100005];
int al[100005],ar[100005];
int n,k;
int main(){
	n = read();
	int la = 0,lb = 0;
	for(int i = 1;i <= n;i++){
		a[i] = read(),b[i] = read();
		(a[i] ^ a[i - 1]) && (la = i - 1);
		(b[i] ^ b[i - 1]) && (lb = i - 1);
		int&oo = o[i];
		oo = min(la,lb);
		((a[oo] ^ a[i]) && (b[oo] ^ b[i])) || (oo = 0);
	}
	k = read();
	for(int i = 1;i <= k;i++){
		int l = read(),r = read();
		q[r].emplace_back(i,l);
	}
	int mx = 0,dr = 0;
	for(int i = 1;i <= n;i++){
		(o[i] > mx) && (mx = o[i],dr = i);
		for(auto&p : q[i]){
			 (mx >= p.second) && (al[p.first] = mx,ar[p.first] = dr);
		}
	}
	for(int i = 1;i <= k;i++) wr(al[i],' '),wr(ar[i]);
	return 0;
}