正题

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

---

题目大意

给出$n$个二元组$(x_i,y_i)$，求最大的
$$|x_i-x_j|\times min\{|y_i|,|y_j|\}$$

$1\le n\le 2\times 10^6,-10^6\le x_i\le 10^6,-10^9\le y_i\le 10^9,1\le T\le 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\n",ans);}return 0; }

总结

以上是生活随笔为你收集整理的T183637-变异距离（2021 CoE III C）【单调栈】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。