拜年【题解】

这题正解是线性的，不过考虑到这是一场基础赛和管理员的建议，我们把

\log

做法放过去了。

我们要统计满足条件的

(l,r)

的数量，使得：

把所有 $a_{i,j}\in[l,r]$ 的格子变成 $1$ ，其余变成 $0$ 。
在这个二进制网格中，从 $(1,1)$ 到 $(2,n)$ 存在一条只经过 $1$ 的四连通路径。

双指针

可以枚举

r

，求对于固定的

r

有多少个

l

满足条件。有一个显然的性质：若

l

满足条件，则

l-1

一定满足条件，因为

l-1

相对于

l

，值域增大，为

1

的格子会增多，连通性不减弱。

因此，对于一个固定的

r

，如果存在合法的

l

，则一定可以找到一个区间

[1,x]

，满足当且仅当

l\in[1,x]

时合法。

此时可以尝试维护第一个不合法的

L=x+1

。又可以发现，若

r

增加

1

，

L

是单调不降的，因此如果能够

O(K)

的实现

r

扩展，

L

收缩，以及查询

(1,1)

和

(2,n)

是否连通就可以双指针实现

O(nK)

的复杂度。

刻画充要条件

注意到本题只有 2 行，结构非常特殊，可以刻画“是否连通”的充要条件，从而做到线性或近线性。

对于一个固定的

(l,r)

，对应的二进制网格为

b

。

我们关心的是：在 $2\times n$ 的网格上，什么时候 $(1,1)$ 可以到达 $(2,n)$ 。

可以证明，其连通当且仅当同时满足：

起点与终点是 $1$ 。

即：
- $(1,1)$ 是 $1$ 。
- $(2,n)$ 是 $1$ 。
每一列至少有一个 $1$ 。

如果没有，路径被直接切断。
不存在“交叉阻断”结构。

“交叉阻断”就是说，存在相邻两列：
- 两列都恰好只有一个 $1$ 。
- 且这两个 $1$ 在不同的行。
形如：
CPP
```
1 0    0 1
0 1    1 0
```
这种结构会把路径“剪断”，形成左右不连通的两个块。

代码中的变量含义是：

变量	含义
`flag`	起点与终点中有几个满足都是 $1$
`cmk`	多少列含有至少一个 $1$
`cnt`	“交叉阻断”结构的数量

路径存在等价于：

CPP

flag == 2 && cmk == n && cnt == 0

复杂度

O(K)=O(1)

最终

O(n)

。

AC 代码

CPP

#include<bits/stdc++.h>
using namespace std;

struct node {
	int t, p;
};

inline bool check(const node& chk, int n) { return (chk.t == 0 && chk.p == 1) || (chk.t == 1 && chk.p == n); }
inline int ct(int i, int j, const vector<vector<int>>& mp, int n) {
    if (i < 1 || j > n) return 0;
    return (mp[0][i] + mp[1][i] == 1) && (mp[0][j] + mp[1][j] == 1) && (mp[0][i] != mp[0][j]);
}
int chkadd(const node& x, vector<vector<int>>& mp, int n) {
    int res = -ct(x.p - 1, x.p, mp, n) - ct(x.p, x.p + 1, mp, n);
    mp[x.t][x.p] = 1;
    return res + ct(x.p - 1, x.p, mp, n) + ct(x.p, x.p + 1, mp, n);
}
int chkdel(const node& x, vector<vector<int>>& mp, int n) {
    int res = -ct(x.p - 1, x.p, mp, n) - ct(x.p, x.p + 1, mp, n);
    mp[x.t][x.p] = 0;
    return res + ct(x.p - 1, x.p, mp, n) + ct(x.p, x.p + 1, mp, n);
}
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(2, vector<int>(n + 1)), mp(2, vector<int>(n + 1));
    vector<vector<node>> find(2 * n + 1);
    vector<int> mk(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[0][i], find[a[0][i]].push_back({0, i});
    for (int i = 1; i <= n; i++) cin >> a[1][i], find[a[1][i]].push_back({1, i});
    int l = 1, cmk = 0, cnt = 0, flag = 0;
    long long ans = 0;
    for (int r = 1; r <= 2 * n; r++) {
        for (const auto &i : find[r]) {
            cnt += chkadd(i, mp, n);
            if (++mk[i.p] == 1) cmk++;
            flag += check(i, n);
        }
        while (l <= r && (flag == 2 && cmk == n && cnt == 0)) {
            for (const auto& i : find[l]) {
                cnt += chkdel(i, mp, n);
                if (--mk[i.p] == 0) cmk--;
                flag -= check(i, n);
            }
            l++;
        }
        ans += l - 1;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

拜年【题解】

文章操作

拜年【题解】

双指针

刻画充要条件

复杂度

相关推荐

评论

拜年【题解】