P11139 [APC001] D - Array Again

题目描述

你需要维护一个数列，支持 $4$ 种操作：

1. 1 x y：连续向数列中插入 $y$ 个数 $x$。
2. 2 x y：连续在数列中删除 $y$ 次 $x$。如果在某一次删除中 $x$ 已经不存在于数列中，则忽略此操作。
3. 3：对数列进行去重，即，对于每个在数列中出现过的不同的正整数 $x$，如果它在数列中出现了大于 $1$ 次，则只在数列中保留一个 $x$，其余全部删除。
4. 4 x：查询数列中 $x$ 的出现次数。

对于每个操作 $4$，请求出其答案。

输入格式

第一行一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行若干个整数，表示一次操作。

输出格式

对于每次操作 $4$ 输出一行，表示其答案。

数据保证至少有一次操作 $4$。

输入输出样例 #1

输入 #1

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

输出 #1

5
1

输入输出样例 #2

输入 #2

4
1 1000000000 1000000000
1 1000000000 1000000000
1 1000000000 1000000000
4 1000000000

输出 #2

3000000000

输入输出样例 #3

输入 #3

20
4 95002957
2 384405322 255642125
2 384405322 174926753
2 384405322 51265222
1 384405322 311383201
4 384405322
1 384405322 5464229
4 22438767
4 17075617
1 384405322 153189933
1 230228188 148299369
1 7168162 387115701
1 384405322 154480360
1 384405322 438458686
3
1 7961090 98996809
4 153074129
1 975025351 171484003
1 384405322 650527951
4 384405322

输出 #3

0
311383201
0
0
0
650527952

说明/提示

样例解释 $1$

第 $1$ 次操作：插入 $10$ 个 $2$。

第 $2$ 次操作：删除 $5$ 个 $2$。此后数列中只包含 $5$ 个 $2$。

第 $3$ 次操作：查询 $2$ 的出现次数，共 $5$ 次。

第 $4$ 次操作：对数列进行去重。此后数列中只包含一个 $2$。

第 $5$ 次操作：查询 $2$ 的出现次数，共 $1$ 次。

样例解释 $2$

请注意答案可能会超过 int 的范围。

数据范围

对于 $100\%$ 的数据，$1\le q\le 10^5$，$1\le x,y\le 10^9$。

请注意：由于本题所在比赛没有部分分，故只有通过所有的测试点才可以获得满分，否则会获得 $0$ 分。

C++实现

#include<iostream>
#include<map>
#include<queue>
using namespace std;
map<long long ,long long>p;
queue<long long>q;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int Q;
    cin>>Q;
    while(Q--){
    	short opt;
    	cin>>opt;
    	if(opt==1){
    		long long x,y;
    		cin>>x>>y;
    		p[x]=p[x]+y;
    		q.push(x);
		}
		else if(opt==2){
			long long x,y;
    		cin>>x>>y;
    		p[x]=max(p[x]-y,0ll);
		}
		else if(opt==3){
			while(!q.empty()){
				if(p[q.front()]>1)p[q.front()]=1ll;
				q.pop();
			}
		}
		else if(opt==4){
			long long x;
			cin>>x;
			cout<<p[x]<<'\n';
		}
	}
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容