题解：CF1550C Manhattan Subarrays

$\mathtt{TAG}$：暴力、BIT、组合数学

一开始震惊到我了，$O(n^2 \log_2 n)$ 过了，然后一算发现是 $O(n \log_2 n)$ 的。

First. 解析坏的三元组

画个图发现，当且仅当 $x_1 \le x_2 \le x_3$ 且 $y_1 \ge y_2 \ge y_3$ 或 $y_1 \le y_2 \le y_3$ 的时候构成坏三元组。

回到题目上，由于每个数的横坐标是下标，所以坏三元组就转化为了一个长度为 $3$ 不下降或不上升的子序列。

Second. 没有坏三元组的区间

首先不妨进行最暴力的想法，枚举每个区间，看它存不存在坏三元组。

而没有坏三元组的子数组的最长长度为 $4$。

证明：

如图，当两个同幅度的子序列相错的时候不能再添加任何一个点。

补充：正确证明是代入 Erdős–Szekeres 定理

Erdős–Szekeres 定理：对于 $|S| = n \times m + 1$ 的偏序集 $(S,\succ)$ ，一定存在一条长度为 $m + 1$ 的链或长度为 $n + 1$ 的反链。

然后代入 $m + 1 = 3$，得 $|S| = 5$。
所以要是其不存在长度为 $3$ 的链，那么 $|S| < 5$，所以最大为 $4$。

所以对于每个左端点，我们至多会枚举 $4$ 次。
时间复杂度只有 $O(n)$！

Third. 判三元组

蒟蒻太蒟了，看到这种偏序形式就用树状数组了。

先离散化，建 $3$ 个树状数组，分别维护：权值 $\le x$ 的点的数量，较大数权值 $\le x$ 且 $a_i \ge a_j$ 的二元组数量，较小数权值 $\le x$ 且 $a_i \le a_j$ 的二元组数量。

然后就判断点 $i$ 能否接在之前的一个二元组上，能接上就是坏三元组。

其实暴力更快。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> pi;
#define endl '\n'
const int N = 2e5 + 10;
int n;
int a[N] , b[N];
struct bit {
#define lowbit(x) (x & -x)
    int c[N];
    void add(int x) {
        for (int i = x; i <= n; i += lowbit(i)) c[i]++;
    }
    void erase(int x) {
        for (int i = x; i <= n; i += lowbit(i)) c[i]--;
    }
    int sum(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += c[i];
        return res;
    }
};
bit t1 , t2 , t3;

signed main() {
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i] , b[i] = a[i];
        sort(b + 1 , b + 1 + n);
        ll tmp = 0 , ans = 0;
        for (int i = 1; i <= n; i++) if (b[i] != b[i - 1]) b[++tmp] = b[i];
        for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1 , b + 1 + tmp , a[i]) - b;//离散化
        for (int i = 1; i <= n; i++) {
            bool flag = 1;
            for (int j = i; j <= n; j++) {
                if (t2.sum(a[j]) || t3.sum(n) - t3.sum(a[j] - 1)) {
                    flag = 0; // 不能暴力清空，会 TLE
                    for (int k = i; k < j; k++) {
                        t1.erase(a[k]);
                        if (t2.sum(a[k]) - t2.sum(a[k] - 1)) t2.erase(a[k]);
                        if (t3.sum(a[k]) - t3.sum(a[k] - 1)) t3.erase(a[k]);
                    }
                    break;
                }
                ans++;
                if (t1.sum(a[j])) t2.add(a[j]);
                if (t1.sum(n) - t1.sum(a[j] - 1)) t3.add(a[j]);
                t1.add(a[j]);
            }
            if (!flag) continue;
            for (int k = i; k <= n; k++) {
                t1.erase(a[k]);
                if (t2.sum(a[k]) - t2.sum(a[k] - 1)) t2.erase(a[k]);
                if (t3.sum(a[k]) - t3.sum(a[k] - 1)) t3.erase(a[k]);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

参考资料

• 【组合数学】Erdős–Szekeres定理