心理阴影题。考试时写了奇怪的线段树分治，在每个线段树节点上维护单调栈在栈内二分……
这题注意到两维分别是 (x,cnt_x)，应该对 (cnt) 比较敏感的是它的自然根号性质，由于 (\sum_{cnt_x}=n)，所以实际上 (cnt_x) 的种类只有 (O(\sqrt n)) 种。我们直接枚举所有这样的对，用一个可删堆来排除掉所有的 bad pair，剩下的最大的拿出来取个 max 就行了。
点击查看代码
const int N=3e5+13;
std::set t[N];
std::map no[N];
int n,m,a[N],b[N],c[N];
int main(){int T;read(T);while(T--){
read(n),read(m);
for(int i=1;i q;while(!q.empty())q.pop();
while(!t[j].empty()&&no[i][*t[j].rbegin()]) q.push(*t[j].rbegin()),t[j].erase(*t[j].rbegin());
if(!t[j].empty()) ans=max(ans,((ll)b[i]+b[*t[j].rbegin()])*(c[i]+c[*t[j].rbegin()]));
while(!q.empty()) t[j].insert(q.front()),q.pop();
}
}
println(ans);
}
return 0;
}
Original: https://www.cnblogs.com/winterfrost/p/cf1637e-solution.html
Author: cunzai_zsy0531
Title: CF1637E Best Pair 题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604318/
转载文章受原作者版权保护。转载请注明原作者出处！