T183637-变异距离（2021 CoE III C）【单调栈】

正题

题目链接:https://www.luogu.com.cn/problem/T183637

---

题目大意

给出(n)个二元组((x_i,y_i))，求最大的

[|x_i-x_j| imes min{|y_i|,|y_j|} ]

(1leq nleq 2 imes 10^6,-10^6leq x_ileq 10^6,-10^9leq y_ileq 10^9,1leq Tleq 10)

---

解题思路

昨天出去了所以没打比赛，这个算法是那个时候口胡的。

首先时间复杂度显然不能带(log)，但是注意到(x)的范围，这是在告诉我们可以拿(x)去排序。

(x)排好序之后，我们发现对于一个位置(j)，我们寻找一个(i<j)使得答案最大那么显然(i)要在从前往后的单调队列里。

这个其实启示了我们，我们可以前后各维护一个单调栈然后在两个栈里面搞。

至于搞法不难发现决定因素是最小的那个，所以我们每次把小的那个弹出顶部就好了。

时间复杂度(O(n))。

然后交上去(T)了好多发，以为是常数的问题，结果换成题解的做法还是(T)了。

最后发现快读还不够，要用那个文件的黑科技读入，出题人真有你的

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cctype>
#define ll long long
using namespace std;
const int N=2e6+10;
int T,n,a[N],sp[N],ss[N],tp,ts;
long long ans;
inline char Getchar()
{
    static char buf[100000],*p1=buf+100000,*pend=buf+100000;
    if(p1==pend)
	{
        p1=buf; pend=buf+fread(buf,1,100000,stdin);
        if (pend==p1) return -1;
    }
    return *p1++;
}
inline int read()
{
	char c;int d=1;int f=0;
	while(c=Getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=Getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
void GetAns(int i,int j)
{ans=max(ans,1ll*(i-j)*min(a[i],a[j]));}
signed main()
{
    T=read();
	while(T--){
		n=read();ans=0;
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			int x=read()+1e6,y=read();
			a[x]=max(a[x],abs(y));
		}
		ts=tp=0;
		for(int i=0;i<=2e6;i++){
			if(!a[i])continue;
			while(ts>0&&a[i]>=a[ss[ts]])ts--;
			ss[++ts]=i;
		}
		for(int i=2e6;i>=0;i--){
			if(!a[i])continue;
			while(tp>0&&a[i]>=a[sp[tp]])tp--;
			sp[++tp]=i;
		}
		int hp=1,hs=1;
		while(ts&&tp){
			GetAns(ss[ts],sp[tp]);
			if(ts>0&&a[ss[ts]]<=a[sp[tp]])ts--;
			else tp--;
		}
		printf("%lld
",ans);
	}
	return 0;
}