MENU

Solution. NOI Online 2022

上午自己打 NOIO,反正考的相当不太行,分数倒也不是太重要,但是至少觉得自己现在实力,尤其是思维能力实在是有待提高。

丹钓战

首先注意到丹钓战是单调栈的谐音。

一开始读题没读清楚,因为各种原因一度想用莫队做,实际上这个题简直简单到离谱。

从头到尾用单调栈把题目描述的过程跑一遍,然后对于第 $i$ 个元素我们记录在 pop 后栈顶元素的下标 $pre_i$。换言之,我们记录的就是 push 当前元素会使得哪些元素被弹出。

接下来,容易发现,在查询区间 $[l,r]$ 时,二元组 $i\in[l,r]$ 会对答案造成贡献当且仅当 $pre_i<l$。

于是做法也就显而易见了,我们希望查询 $[l,r]$ 中 $pre_i<l$ 的二元组个数,可以使用主席树进行维护。

离线做法更为简单,再将序列扫一遍,用一个树状数组对 $pre$ 进行计数,扫到 $i$ 的时候,对于所有 $l=i-1$ 的询问记录负贡献,$r=i$ 的记录正贡献。

复杂度 $O(n\log n)$。

namespace Main{
    const int N = 500005;
    int n, q, pre[N], ans[N];
    pair<int, int> a[N];
    stack<int> stk;
    vector<int> ql[N];
    vector<pair<int, int>> qr[N];
    struct bit{
        int t[N];
        inline int lowbit(int x) { return x & -x; }
        void add(int x) { for(int i = x; i < N; i += lowbit(i)) t[i]++; }
        int query(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += t[i]; return res; }
    }tree;
    void Main(){
        input(n, q);
        for(int i = 1; i <= n; i++) input(a[i].first);
        for(int i = 1; i <= n; i++) input(a[i].second);
        for(int i = 1; i <= n; i++){
            while(!stk.empty() && (a[stk.top()].first == a[i].first || a[stk.top()].second <= a[i].second)) stk.pop();
            pre[i] = stk.empty() ? 0 : stk.top();
            stk.push(i);
            // cerr << pre[i] << ' ';
        }
        for(int i = 0, l, r; i < q; i++){
            input(l, r);
            ql[l-1].push_back(i);
            qr[r].emplace_back(l, i);
        }
        for(int i = 1; i <= n; i++){
            tree.add(pre[i] + 1);
            for(int t: ql[i]) ans[t] -= tree.query(i + 1);
            for(pair<int, int> t: qr[i]) ans[t.second] += tree.query(t.first);
        }
        for(int i = 0; i < q; i++) write(ans[i]), puts("");
        return;
    }
} // namespace

注意输入优化

值得一提的是这个题的思考方式,一方面很 naive,一方面也很有价值(至少对我而言),看了一下 fz 的 NOIO 游记似乎 fz 也没有做出来 t1,但是也有人发出 t1 应该评绿的暴论。

考虑这样一件事情,如果题目问的是,给出序列 $\{a_n\}$,每次抽出一个区间 $[l,r]$,询问其中有多少个数 $a_i$ 满足 $\forall j\in(i,r],\ a_i\ge a_j$。

容易发现,两个问题的本质是一样的。正难则反,一个数后面的所有数都没有自己大,也就意味着第一个比自己大的数在当前询问区间的后面,这个用单调栈可以轻而易举的解决,原题同理,本质上就是一个简单的转化。

讨论

这也应该是一个简单题。

题目给出的限制条件其实非常弱,考虑将集合从大到小排序,这样的话我们只需要保证后面的集合与前面的集合有交且不被包含,这一对集合就是满足题意的。

于是不难想到在从前往后遍历所有集合时,我们维护 $p_i$ 表示 $i$ 在第 $p_i$ 个集合中出现过。考虑当前集合 $S$,如果 $\forall a,b\in S$ 都有 $p_a=p_b$,那么 $S$ 被某个集合包含,或者 $S$ 与之前的所有集合不交(当且仅当 $\forall a\in S,\ p_a=0$),否则我们找到了一组合法解,输出即可。

这里注意一下细节,如果 $S$ 被包含,我们应该覆盖原来的标记而不是保留。

复杂度看起来像 $O(n^2)$,实际上是优秀的 $O(n+\sum k_i)=O(n+m)$

namespace Main{
    const int N = 1000005;
    int t, n, k[N], p[N];
    pair<int, vector<int>> a[N];
    void Main(){
        input(t);
        while(t--){
            for(int i = 0; i < n; i++) a[i].second.clear();
            memset(p, -0x3f, sizeof(p));
            input(n);
            for(int i = 0; i < n; i++){
                input(k[i]);
                a[i].first = i + 1;
                for(int j = 0; j < k[i]; j++) a[i].second.push_back(read<int>());
                // for InfOJ
                sort(a[i].second.begin(), a[i].second.end());
                a[i].second.erase(unique(a[i].second.begin(), a[i].second.end()), a[i].second.end());
            }
            sort(a, a + n, [](auto a, auto b){
                return a.second.size() > b.second.size();
            });
            bool flag = false;
            for(int i = 0; i < n && !flag; i++){
                int num = -1;
                for(int x: a[i].second){
                    if(num == -1) num = p[x];
                    else if(num != p[x]){
                        puts("YES");
                        write(a[i].first), putchar(' '), write(a[max(num, p[x])].first);
                        puts("");
                        flag = true;
                        break;
                    }
                    p[x] = i;
                }
            }
            if(!flag) puts("NO");
        }
        return;
    }
} // namespace

如何正确的排序

$m=2$ 时答案为 $2n\sum a_{i,j}$,不多赘述。

$m=3$ 时考虑转化为求 $g(i,j)=a_{k,i}+a_{k,j}$ 使得 $a_{x,i}+a_{x,j}\le g(i,j)\le a_{y,i}+a_{y,j}$。

Last Modified: March 28, 2022
Archives Tip
QR Code for this page
Tipping QR Code