题解 P9285 [AGM 2023 资格赛] YsaeSort

· · 题解

先来一个不是很正经的 O(n^2) 做法。

首先考虑显然有一个简单的 O(n^2\log n) 的暴力，操作 1 暴力排序，操作 2 直接 O(n) 扫。事实上操作 2 直接 O(len) 扫是相当优的，因为寻址是连续的。

然后考虑怎么优化，因为每次操作 1 的排序保证区间包含或不交，所以每次相当于合并若干个有序段，这部分可以 O(n\log ^2n) 启发式合并 set，然后再把当前这个区间的 set 遍历一边放回原序列。

这样做到 O(n^2)，其实已经很优秀了，但是卡满的情况下（比如每次对 [1,i]）排序，这样每次遍历的 set 大小会被卡满，而又因为遍历 set 事实上是瓶颈，所以会跑得挺满（本机 12s）。

事实上观察到上面这种情况每次合并的有序段不会很多，所以我们考虑当有序段个数小于一个很小的常数 B 时，做 B 次归并排序。这样子就能通过这个题了，我取了 B=3。

inline void merge(multiset<int>&x,multiset<int>&y)
{
    if (x.size()<y.size()) x.swap(y);
    for (auto u:y) x.insert(u);multiset<int>().swap(y);
}
void BellaKira()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i].insert(a[i]);
        S.insert(i);
    }
    S.insert(n+1);
    cin>>q;
    ll all=0;
    int ooo=0;
    while (q--)
    {
        int opt,l,r;
        cin>>opt;
        if (opt==1)
        {
            cin>>l>>r;
            r=min(r,n);
            auto it=S.lower_bound(l);
            if (it==S.end()) continue;
            it++;
            auto itl=it;
            int t=0;
            while (it!=S.end())
            {
                if ((*it)>r) break;
                merge(s[l],s[*it]);
                it++;
                t++;
            }
            if (t>=3)
            {
                S.erase(itl,it);
                int o=l-1;
                for (auto u:s[l])
                {
                    a[++o]=u;
                }
            } else
            {
                it=itl;
                while (it!=S.end())
                {
                    if ((*it)>r) break;
                    auto it1=it;
                    it1++;
                    // cout<<"???"<<l<<" "<<(*it)<<" "<<(*it1)<<endl;
                    inplace_merge(a+l,a+(*it),a+(*it1));
                    it++;
                }
                S.erase(itl,it);
            }
        } else
        {
            cin>>l>>r;
            int mx=0;
            ll ans=0;
            for (int i=l;i<=r;i++)
            {
                if (mx>a[i])
                    ans=max(ans,1ll*a[i]*mx);
                mx=max(mx,a[i]);
            }
            all^=ans;
            cout<<ans<<'\n';
        }
    }
}

正经做法是个稍微有点 trivial 的东西，但是不那么好写。

考虑没有修改时的一个做法，就是我们每次线段树上维护一个 pair 表示当前节点答案以及当前节点的 \max。那么每次相当于合并的时候，在右儿子区间里找跟 \max 最接近的比 \max 小的数更新答案，右边这部分可以用主席树维护每个区间的权值集合。

那考虑有了排序，我们需要维护整个 a 序列的变化，怎么维护呢？

其实并不需要维护，如果我们维护了每个有序段，那么 a 序列的某个区间是可以表示成若干个整个有序段和“某个有序段的大于等于某个数的集合或小于等于某个数的集合”。

那就好办了，正好跟我们需要做的事情是一样的。

我们考虑对于两个点 i,j(a_i>a_j) 产生的贡献直到 i 与 j 合并成一个有序段之前都是存在的。继续用线段树维护上述的那个 pair。

那么每次排序相当于合并有序段，然后把当前这个区间内的所有节点答案设成 0。

线段树上合并两个 pair 也很简单，由于之前已经知道了：某个区间是可以表示成若干个整个有序段和“某个有序段的大于等于某个数的集合或小于等于某个数的集合”。所以我们直接把右边这个区间分成：某个有序段的大于等于某个数的集合、若干个连续的整个的有序段、某个有序段的小于等于某个数的集合。然后在这三个部分上查询跟 \max 最接近的比 \max 小的数更新答案即可。

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