202303-4Day10
题目描述
十滴水是一个非常经典的小游戏。
小 \(C\) 正在玩一个一维版本的十滴水游戏。
我们通过一个例子描述游戏的基本规则。
游戏在一个$ 1×c$ 的网格上进行，格子用整数$ x(1≤x≤c)$ 编号，编号从左往右依次递增。
网格内 \(m\) 个格子里有 \(1∼4\) 滴水，其余格子里没有水。
在我们的例子中，\(c=m=5\)，按照编号顺序，每个格子中分别有 \(2,4,4,4,2\) 滴水。
玩家可以进行若干次操作，每次操作中，玩家选择一个有水的格子，将格子的水滴数加一。
任何时刻若某个格子的水滴数大于等于\(5\)，这个格子里的水滴就会向两侧爆开。
此时，这个格子的水被清空，同时对于左方、右方两个方向同时进行以下操作：找到当前格子在对应方向上最近的有水的格子，如果存在这样的格子，将这个格子的水滴数加一。
若在某个时刻，有多个格子的水滴数大于等于$ 5$，则最靠左的先爆开。
在我们的例子中，若玩家对第三格进行操作，则其水滴数变为 \(5\)，故第三格水滴爆开，水被清空，其左侧最近的有水格子（第二格）和右侧最近的有水格子（第四格）的水量增加 \(1\)，此时每个格子中分别有 \(2,5,0,5,2\) 滴水。
此时第二格和第四格的水滴数均大于等于 \(5\)，按照规则，第二格的水先爆开，爆开后每个格子中分别有 \(3,0,0,6,2\)滴水；最后第四格的水滴爆开，每个格子中分别有 \(4,0,0,0,3\) 滴水。
小 \(C\) 开始了一局游戏并进行了$ n$ 次操作。
小 \(C\) 在每次操作后，会等到所有水滴数大于等于$ 5$ 的格子里的水滴都爆开再进行下一次操作。
小 \(C\) 想知道他的水平有多高，于是他想知道每一次操作后还有多少格子里有水。
保证这 \(n\) 次操作都是合法的，即每次操作时操作的格子里都有水。
输入格式
输入的第一行三个整数 \(c,m,n\) 分别表示网格宽度、有水的格子个数以及操作次数。
接下来 \(m\) 行每行两个整数 \(x,w\)，表示第$ x$ 格有$ w$ 滴水。
接下来 \(n\) 行每行一个整数 \(p\)，表示小 \(C\) 对第\(p\) 格做了一次操作。
输出格式
输出 \(n\) 行，每行一个整数表示这次操作之后网格上有水的格子数量。
数据范围
对于所有测试数据
- \(1≤c≤10^9,1≤m≤min(c,3×10^5),1≤n≤4m\)；
- \(1≤x,p≤c,1≤w≤4\)；
- 输入的所有 \(x\) 两两不同；
- 对于每个输入的 \(p\)，保证在对应操作时 \(p\) 内有水。
| 子任务编号 | \(c \le\) | \(m \le\) | 特殊性质 |
|---|---|---|---|
| \(1\) | \(30\) | \(30\) | 有 |
| \(2\) | \(3000\) | \(3000\) | 有 |
| \(3\) | \(3000\) | \(3000\) | 无 |
| \(4\) | \(10^9\) | \(3000\) | 无 |
| \(5\) | \(3×10^5\) | \(3×10^5\) | 无 |
| \(6\) | \(10^9\) | \(3×10^5\) | 有 |
| \(7\) | \(10^9\) | \(3×10^5\) | 无 |
特殊性质：在游戏的任意时刻（包括水滴爆开的连锁反应过程中），只有至多一个格子的水滴数大于等于 \(5\)。
输入样例：
5 5 2
1 2
2 4
3 4
4 4
5 2
3
1
输出样例：
2
1
题目分析
一道模拟题，根据数据量的不同采用不同形式的数据结构维护格子水滴数量
我们直接来考虑最大的即可
\(c \le 10^9 , m \le 3×10^5\) 很明显，这个数据就是在告诉我们要去离散化有水滴的点
与此同时，我们还要维护水滴的点数，如果超过\(5\)，就要清零并且左右都要++。
那其实，用一个双向链表就可以维护这样一个有头有尾的序列了，清零后相当于要去删除这个点即可，然后再去搜索左面和右面的点，递归维护水滴点数和序列。
对于整个序列而言，长度为\(m\)，所以再怎么做操作，对于\(n\)次的操作，最多就是把整个序列全部清空，也就是扫一遍整个序列，时间复杂度\(O(m)\)，而对于其他步骤，一个是找到目标点，为了速度更快，直接使用哈希表存储编号和目标位置即可，另一个是对原有的水滴排序构造双向链表，排序\(O(mlogm)\)，构造\(O(m)\)，所以算法时间复杂度为\(O(mlogm)\)。
这里代码真正实现的时候，为了方便，我使用了map直接当作双向链表，因为它可以直接进行关键字的排序，更方便找前序和后继节点，其余部分不变，map的大小即为答案。
注意：Acwing上要开\(O(2)\)或\(O(3)\)优化，编译器没做到自动优化会爆内存。其余做过\(O(2)\)优化的就不用了
C++代码实现
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;int c , m , n;
map<int , map<int , int>::iterator> mp;
map<int , int> s;
int x , w;void dfs(map<int , int>::iterator x)
{// cout << "x : " << x->first << '\n';bool flag_pre = (x == s.begin());bool flag_last = (x == -- s.end());auto pre = x;if(!flag_pre) pre --, pre->second ++;auto last = x;if(!flag_last) last ++ , last->second ++;s.erase(x);// for(auto [k , v] : s)// cout << v << ' ';// cout << '\n';if(!flag_pre && pre->second >= 5) dfs(pre);else if(!flag_last && last->second >= 5) dfs(last);}int main()
{ios::sync_with_stdio(false);cin.tie(0) , cout.tie(0);cin >> c >> m >> n;while (m -- ){cin >> x >> w;mp[x] = s.insert({x , w}).first;}int k;while(n --){cin >> k;s[k] ++;if(s[k] >= 5)dfs(mp[k]);cout << s.size() << '\n';}
}
