屯昌县网站建设_网站建设公司_云服务器_seo优化

描述

已知牛牛有 nn 份资源，编号为 11 到 nn，初始均处于未上锁状态。现在共有 mm 次操作，每次给定一个编号 pp：
∙ ∙若编号为 pp 的资源未上锁，则为其上锁；
∙ ∙否则，解除锁，使其回到未上锁状态。
每次操作后，牛牛希望分别统计区间 [1,x][1,x] 与 [y,n][y,n] 中“可访问”资源的数量。这里规定，资源可访问当且仅当其处于未上锁状态。

输入描述：

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦103)T(1≦T≦103) 代表数据组数，每组测试数据描述如下：
第一行输入四个整数，依次为：
∙ ∙n(1≦n≦2×105)n(1≦n≦2×105)，表示资源数量；
∙ ∙m(1≦m≦4×105)m(1≦m≦4×105)，表示操作次数；
∙ ∙x(1≦x≦n)x(1≦x≦n)，表示区间 [1,x][1,x] 的右端点；
∙ ∙y(1≦y≦n)y(1≦y≦n)，表示区间 [y,n][y,n] 的左端点。
此后 mm 行，第 ii 行输入一个整数 pi(1≦pi≦n)pi​(1≦pi​≦n)，表示对编号为 pipi​ 的资源切换锁状态。

输出描述：

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

示例1

输入：

2 4 3 2 3 2 3 3 6 6 4 2 1 3 6 4 4 2

复制输出：

1 2 1 1 1 2 3 5 2 4 2 3 1 2 2 3 1 2

说明：

对于第一组测试数据，用 yy 表示资源上锁，nn 表示资源未上锁，过程如下： ∙ ∙第一次操作后，资源上锁情况为：n,y,n,nn,y,n,n，可以发现，区间 [1,2][1,2] 中只有编号 11 可访问，而区间 [3,4][3,4] 均未上锁，所以输出 11 和 22； ∙ ∙第二次操作后，资源上锁情况为：n,y,y,nn,y,y,n，可以发现，区间 [1,2][1,2] 情况不变，区间 [3,4][3,4] 中只剩下编号 44 可访问，所以输出 11 和 11； ∙ ∙第三次操作，将资源 33 解锁，重新回到了第一次操作后的状态，因此，输出与第一次操作后的输出相同，输出 11 和 22。

思路：

主播看到题没想那么多，看到数据范围，直接无脑想用桶或者布尔计数来标记每个锁的状态，这样无脑的做法来做，过了，不过数据再大的就肯定过不了的，正解应该是树状数组 / 线段树 + 前缀和思想来高效维护区间统计。简单来说，就是用bool数组记录每个数的标记状态，每次切换状态后，只更新该数所在区间的计数，最后实时输出结果，核心是 “按需更新、即时输出” 的模拟思想。

主播的代码:

#include <iostream> #include<queue> #include<cstring> #include<algorithm> #include<cstdio> #include<map> #include<vector> #include<set> #include<stack> #include<string> #include<math.h> #include <iomanip> #include<unordered_map> #include <unordered_set> #include<array> #define gets(S) fgets(S,sizeof(S),stdin) #define ll long long const ll N = 5e5 + 5; const ll Max = 0x3f3f3f3f; using namespace std; ll t; bool saki[N]; int main() { cin >> t; ll n, m, x, y; while (t--) { cin >> n >> m >> x >> y; ll w, ansx = x, ansy = n - y + 1; for (int i = 1; i <= m; i++) { cin >> w; if (!saki[w]) { saki[w] = 1; } else { saki[w] = 0; } if (w >= y) { if (saki[w]) { ansy -= 1; } else { ansy += 1; } } if (w <= x) { if (saki[w]) { ansx -= 1; } else { ansx += 1; } } cout << ansx << ' ' << ansy << endl; } for (int i = 1; i <= m; i++) { saki[i] = 0; } } return 0; }