题解 | #锁#_牛客博客

题目链接

锁

题目描述

有 $n$ 份资源，编号为 1 到 $n$ ，初始均处于未上锁状态。现在共有 $m$ 次操作，每次给定一个编号 $x$ ：

若编号为 $x$ 的资源未上锁，则为其上锁；
否则，解除其锁，使其回到未上锁状态。

每次操作后，牛牛希望分别统计区间 $[1, r_1]$ 与 $[l_2, n]$ 中“可访问”（即未上锁）资源的数量。

输入:

第一行一个整数 $T$ 代表数据组数。
每组数据第一行四个整数： $n, m, r_1, l_2$ 。
此后 $m$ 行，每行一个整数 $x$ ，表示操作的资源编号。

输出:

对于每次操作，新起一行输出两个整数，分别表示区间 $[1, r_1]$ 与 $[l_2, n]$ 中可访问资源的数量。

解题思路

这是一个需要高效处理区间查询和单点更新的问题。由于操作次数 $m$ 可能很大，如果在每次操作后都重新遍历区间来计数（ $O(n)$ ），总时间复杂度将是 $O(m \cdot n)$ ，可能会超时。因此，我们需要一种更高效的增量计算方法。

我们可以维护两个计数器，分别对应两个目标区间中未上锁资源的数量。每次操作只影响一个资源，我们可以根据这个资源的状态变化和它所在的位置，来动态更新这两个计数器。

算法步骤如下：

状态初始化：
- 创建一个大小为 $n+1$ 的布尔数组 $\text{is_locked}$ ，全部初始化为 false，表示所有资源初始都未上锁。
- 初始化两个计数器：
  - $\text{count}_1$ (区间 $[1, r_1]$ 的未上锁数量) = $r_1$ 。
  - $\text{count}_2$ (区间 $[l_2, n]$ 的未上锁数量) = $n - l_2 + 1$ 。
处理每次操作：对于每次给定的资源编号 $x$ ：
- 检查当前状态：查看 $\text{is_locked}[x]$ 的值。
- ** case 1: 资源即将被上锁** (即 $\text{is_locked}[x]$ 为 false):
  - 如果 $x$ 在区间 $[1, r_1]$ 内 (即 $x \le r_1$ )，则该区间内未上锁资源数减 1，故 $\text{count}_1 = \text{count}_1 - 1$ 。
  - 如果 $x$ 在区间 $[l_2, n]$ 内 (即 $x \ge l_2$ )，则该区间内未上锁资源数减 1，故 $\text{count}_2 = \text{count}_2 - 1$ 。
- ** case 2: 资源即将被解锁** (即 $\text{is_locked}[x]$ 为 true):
  - 如果 $x \le r_1$ ，则 $\text{count}_1 = \text{count}_1 + 1$ 。
  - 如果 $x \ge l_2$ ，则 $\text{count}_2 = \text{count}_2 + 1$ 。
- 更新状态：翻转资源 $x$ 的锁定状态， $\text{is_locked}[x] = !\text{is_locked}[x]$ 。
- 输出结果：输出更新后的 $\text{count}_1$ 和 $\text{count}_2$ 。

这种方法将每次操作的复杂度降到了 $O(1)$ ，可以高效地解决问题。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, m, r1, l2;
    cin >> n >> m >> r1 >> l2;
    
    // is_locked[i] 为 true 表示资源 i 已上锁
    vector<bool> is_locked(n + 1, false);
    // count1: 区间 [1, r1] 中未上锁的资源数
    int count1 = r1;
    // count2: 区间 [l2, n] 中未上锁的资源数
    int count2 = n - l2 + 1;

    for (int i = 0; i < m; ++i) {
        int x;
        cin >> x;

        if (is_locked[x]) {
            // 当前是上锁状态，操作后解锁
            is_locked[x] = false;
            // 检查 x 是否在区间 [1, r1] 内
            if (x >= 1 && x <= r1) {
                count1++;
            }
            // 检查 x 是否在区间 [l2, n] 内
            if (x >= l2 && x <= n) {
                count2++;
            }
        } else {
            // 当前是未上锁状态，操作后上锁
            is_locked[x] = true;
            if (x >= 1 && x <= r1) {
                count1--;
            }
            if (x >= l2 && x <= n) {
                count2--;
            }
        }
        cout << count1 << " " << count2 << endl;
    }
}

int main() {
    // 处理多组测试数据
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int r1 = sc.nextInt();
        int l2 = sc.nextInt();

        // isLocked[i] 为 true 表示资源 i 已上锁
        boolean[] isLocked = new boolean[n + 1]; // 默认全为 false
        // count1: 区间 [1, r1] 中未上锁的资源数
        int count1 = r1;
        // count2: 区间 [l2, n] 中未上锁的资源数
        int count2 = n - l2 + 1;

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            
            if (isLocked[x]) {
                // 当前是上锁状态，操作后解锁
                isLocked[x] = false;
                // 检查 x 是否在区间 [1, r1] 内
                if (x >= 1 && x <= r1) {
                    count1++;
                }
                // 检查 x 是否在区间 [l2, n] 内
                if (x >= l2 && x <= n) {
                    count2++;
                }
            } else {
                // 当前是未上锁状态，操作后上锁
                isLocked[x] = true;
                if (x >= 1 && x <= r1) {
                    count1--;
                }
                if (x >= l2 && x <= n) {
                    count2--;
                }
            }
            System.out.println(count1 + " " + count2);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 处理多组测试数据
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys
input=sys.stdin.readline

# python 代码请提交到 pypy3

def solve():
    # 读取一行并解析为整数
    n, m, r1, l2 = map(int, input().split())
    
    # is_locked[i] 为 True 表示资源 i 已上锁
    is_locked = [False] * (n + 1)
    # count1: 区间 [1, r1] 中未上锁的资源数
    count1 = r1
    # count2: 区间 [l2, n] 中未上锁的资源数
    count2 = n - l2 + 1

    for _ in range(m):
        x = int(input())
        
        if is_locked[x]:
            # 当前是上锁状态，操作后解锁
            is_locked[x] = False
            # 检查 x 是否在区间 [1, r1] 内
            if 1 <= x <= r1:
                count1 += 1
            # 检查 x 是否在区间 [l2, n] 内
            if l2 <= x <= n:
                count2 += 1
        else:
            # 当前是未上锁状态，操作后上锁
            is_locked[x] = True
            if 1 <= x <= r1:
                count1 -= 1
            if l2 <= x <= n:
                count2 -= 1
        
        print(count1, count2)

# 处理多组测试数据
t = int(input())
for _ in range(t):
    solve()

算法及复杂度

算法：模拟、增量计算
时间复杂度: 对于每组测试数据，初始化需要 $O(N)$ ，后续 $M$ 次操作每次都是 $O(1)$ ，所以总时间复杂度是 $O(N+M)$ 。
空间复杂度: $O(N)$ ，用于存储 $N$ 个资源的状态。