题解：P12446 [COTS 2025] 答好位 / Vrsta
min_inf
·
·
题解
考虑如果需要回答的是最大怎么做。维护一个单调栈，加入一个点的时候询问当前栈顶 j 到新元素 i 这段区间，如果 p_j<p_i 那么次大就应该是 j（因为他原来是最大），遇到第一个 p_j>p_i 次大就变成 i 了，存下每个位置的单调栈就可以用 2n 次询问回答出最大的问题。
然后考虑拓展一下这个单调栈，把所有会更新次大的元素也加入。称更新最大的元素为第一类，更新次大的为第二类。
考虑加入 i 时单调栈怎么变化：设 p 为左侧第一个大于 i 的，p 右侧的第一类元素全部变为第二类，第二类元素全都删掉，然后删除 p 到左边下一个第一类元素之间第二类元素的一个后缀，最后加入第一类元素 i。
```cpp
cin>>n;
vector<pair<int,bool>> stk;
stk.emplace_back(1,0);
rep(i,2,n){
vector<int> rm;
while(!stk.empty()){
if(stk.back().sec){
stk.pop_back();
continue;
}
if(ask(stk.back().fir,i)==i)break;
rm.push_back(stk.back().fir);
stk.pop_back();
}
if(!stk.empty()){
int p=stk.back().fir;
stk.pop_back();
while(!stk.empty()&&stk.back().sec&&ask(stk.back().fir,i)!=stk.back().fir)
stk.pop_back();
stk.emplace_back(p,0);
}
reverse(allc(rm));
for(auto p:rm)stk.emplace_back(p,1);
stk.emplace_back(i,0);
rs[i]=stk;
}
cout<<'!'<<endl;
cin>>m;
while(m--){
int l,r;cin>>l>>r;
stk=rs[r];
int p=0,q=0;
while(!stk.empty()&&stk.back().fir>=l){
auto [x,tp]=stk.back();stk.pop_back();
if(tp)q=x;else q=p,p=x;
}
cout<<q<<'\n';
}
```