HILO-G 题解

· · 题解

题意：对于每个数进行猜数过程（比大小的过程形成 HI 或者 LO 的结果，而且需要剪枝，剪枝的过程题目中已讲述），求形成的结果串之内子串 HILO 的数量。

提供另外一组样例数据。

思路：观察到暴力一个个去处理 HI 和 LO 的结果，只能过数据随机那一档分数，这个算法也不好处理对于每个数的全局查询一类结果，于是考虑转化思路，把所有询问一起处理。（这是一种类似于整体二分的思想）

显然可知，在不断进行处理询问的过程之中，一些区间的答案是一样的，直到最后第 n 个操作才把所有询问的答案独立。

手动模拟一下，发现每次操作实质上是分裂一个区间，然后对它们统计不同的答案。

实际上每次操作所涉及的 a_i 仅仅影响到包含 a_i 的这个区间的答案，使这个区间分裂成为两半（左半部分打上 HI 的标记而右半部分打上 LO 的标记，并且转移答案），这样的操作是珂朵莉树的 split 操作，实现时候只需要使用 set 维护区间集即可。

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

#include<bits/stdc++.h>
using namespace std;typedef int I;
struct nd{
    mutable I l,r,frid,ans;
    friend bool operator <(nd a,nd b){
        return a.l<b.l;}};
set<nd>s;
void split(I id){
    auto it=s.upper_bound(nd{id,id,0});
    --it;auto p=*it;
    s.erase(it);
    if(p.l<=id-1)s.insert(nd{p.l,id-1,0,p.ans});
    s.insert(nd{id,p.r,1,p.ans+(p.frid^1)});
}I n;
int main(){
    scanf("%d",&n);
    s.insert(nd{0,n,1,0});
    for(I i=n,x;i;--i)scanf("%d",&x),split(x);
    for(auto i:s)printf("%d\n",i.ans);
    return 0;
}