Mad MAD Sum-Codeforces Round 960 (Div. 2)

题目在这里

大意: MAD函数返回出现次数$\ge 2$的最大整数 $b_i$ = $MAD(a[1,2,...i])$ 每次操作把$a_i$进行上述操作，直到全变为0为止，对每次操作的数组进行求和，记为$sum$,问sum的大小

分析: 经过一次运算总可以得到非递减的序列,因为MAD函数非递减，最大值只会越来越大 只有连续的数段可以向右传递,做一次虽然非递减，但是会有只有单个的情况这是不可以向右传递的 我们可以再做一次计算去除这些数，剩下就是可以向右传递的

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n;    
void calc(vector<int>&a,i64 &s){
	map<int,int> mp;
	i64 now = 0;
	vector<int> res(n+1,0);
	for(int i = 1;i<=n;++i){
		mp[a[i]]++;
		if(mp[a[i]]>=2&&a[i]>now){
			now = a[i];
		}
		res[i] = now;
	}
	a = res;
	for(int i = 1;i<=n;++i){
		//cout<<a[i]<<' ';
		s+=a[i];
	}
	//cout<<s<<"\n";
}
void solve(){
	cin>>n;
	vector<int>a(n+1);
	i64 s = 0;
	for(int i = 1;i<=n;++i) cin>>a[i],s+=a[i];
	calc(a,s);calc(a,s);
	for(int i = 1;i<=n;++i){
		s+=(n-i)*1LL*a[i];
	}
	//cout<<s<<"\n";
}


signed main(){
	ios;
	int t;cin>>t;
	while(t--){
		solve();
	}

	return 0;
}

读错题目了好难受qaq