【练习-10】 Unread Messages（未读消息）

题目描述

There is a group of people in an internet email message group. Messages are sent to all members of the group, and no two messages are sent at the same time.
Immediately before a person sends a message, they read all their unread messages up to that point.
Each sender also reads their own message the moment it is sent. Therefore, a person’s unread messages are exactly the set of messages sent after that person’s last message.
Each time a message is sent, compute the total number of unread messages over all group members.

输入

The first line of input contains two integers n (1 ≤ n ≤ 109 ) and m (1 ≤ m ≤ 1,000), where n is the number of people in the group, and m is the number of messages sent. The group members are
identified by number, 1 through n.
Each of the next m lines contains a single integer s (1 ≤ s ≤ n), which is the sender of that message. These lines are in chronological order.

输出

Output m lines, each with a single integer, indicating the total number of unread messages over all group members, immediately after each message is sent.

样例输入

【样例1】
2 4
1
2
1
2
【样例2】
3 9
1
2
3
2
1
3
3
2
1

样例输出

【样例1】
1
1
1
1
【样例2】
2
3
3
4
3
3
5
4
3

题目大意：

有n个人发m次消息（每次只有一个人发），接下来m行没行输入是第几个人发的。
当一个人发消息时，其他所有人都会有一条未读消息，当一个人发消息时，他的未读消息会清0.

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define CLEAR(a) memset(a,0,sizeof a);
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
map<ll,ll> mp;
int main()
{
    
	ll n,m,x，res=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
    
		cin>>x;
		res+=(n-(i-mp[x]));
		mp[x]=i;
		cout<<res<<endl;
	}
    return 0;
}

思路：

因为发一条消息时，除了自己每个人的未读消息都会+1。那不妨假设每个人都会+1，也就是说未读消息总数+n。
然后我们再减去发消息的人已经看了的消息，用map记录上一次看消息是什么时候，用i-mp[x]就是已经看了的消息（不需要额外-1，因为A发消息时A也+1了）。
那么只要加上n-(i-mp[x])就是未读消息的量了。