题解：P12446 [COTS 2025] 答好位 / Vrsta

考虑如果需要回答的是最大怎么做。维护一个单调栈，加入一个点的时候询问当前栈顶

j

到新元素

i

这段区间，如果

p_j<p_i

那么次大就应该是

j

（因为他原来是最大），遇到第一个

p_j>p_i

次大就变成

i

了，存下每个位置的单调栈就可以用

2n

次询问回答出最大的问题。

然后考虑拓展一下这个单调栈，把所有会更新次大的元素也加入。称更新最大的元素为第一类，更新次大的为第二类。

考虑加入

i

时单调栈怎么变化：设

p

为左侧第一个大于

i

的，

p

右侧的第一类元素全部变为第二类，第二类元素全都删掉，然后删除

p

到左边下一个第一类元素之间第二类元素的一个后缀，最后加入第一类元素

i

。

p

右边的部分和最大的做法一样，左边的部分显然也可以直接查次小是不是左端点来检查。每个元素最多被弹栈两次，每次加入最多在边界浪费两次询问，所以不会超过

4n

次询问。

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';
}

题解：P12446 [COTS 2025] 答好位 / Vrsta

文章操作

相关推荐

评论

题解：P12446 [COTS 2025] 答好位 / Vrsta