Serval and Toxel's Arrays[时间戳][*1400~*1600]

给你一个零时刻的长度为 \(n\) 的数组 \(a_i\)。

时刻 \(i\ (1 \le i \le m)\) 的数组是在时刻 \(i-1\) 的基础上把位置 \(p_i\) 的数改成 \(v_i\) 得到的。

现在让你求出 \(\sum_{i=0}^m \sum_{j=i+1}^m f(i,j)\)，其中 \(f(i,j)\) 的值为时刻 \(i\) 和时刻 \(j\) 的数组拼起来后一共有几种数字。

看上去好像是一道时间戳的题

说到时间戳就想到了

D - All Assign Point Add (atcoder.jp)

是一道简单的时间戳

题目中要求\(\sum_{i=0}^m \sum_{j=i+1}^m f(i,j)\)

根据容斥我们可以知道

如果一个数被 \(i\) 和 \(j\) 同时包含 那么 \(f(i,j)\) 对答案的贡献是1

如果一个数被 \(i\) 或 \(j\) 包含 那么 \(f(i,j)\) 对答案的贡献也是1

如果一个数不被 \(i\) 或 \(j\) 包含 那么 \(f(i,j)\) 对答案的贡献是0

那么我们就可以将上面的两种情况合并

只分析下面的情况

那么每一个数的贡献就是 总配对数减去不被包含的配对数

那么总配对数就是 \(m\times (m+1)\)

设 \(len\) 为不被配对的个数

那么没有贡献的配对数就是 \(len\times (len+1)\)

对于每一个出现过的数进行上面的操作即可

由于题目中的数是散的，所以我们可以用map进行记录

也可以用一个vector<int>来进行时间戳的记录

key code

int n,m;
void solve(){
	//try it again.
	cin>>n>>m;
	map<int,vector<int>>mp;
	int a[n+10];
	up(1,n)cin>>a[o];
	up(1,n){
		mp[a[o]].pb(0);
	}
	up(1,m){
		int x,v;
		cin>>x>>v;
		if(a[x]==v)continue;
		mp[a[x]].pb(o);
		a[x]=v;
		mp[a[x]].pb(o);
	}
	int ans=0;
	for(auto &[x,y]:mp){
		if(sz(y)&1)y.pb(m+1);
		ans+=m*(m+1)>>1;
		int len=0,last=0;
		for(int i=0;i<sz(y);i+=2){
			len+=y[i]-last;
			last=y[i+1];
		}
		len+=m-last;
		ans-=len*(len+1)>>1;
	}
	cout<<ans<<endl;
}