Submission #577357

#	Time	Username	Problem	Language	Result	Execution time	Memory
577357		rembocoder	Diversity (CEOI21_diversity)	C++17	100 / 100	6724 ms	10488 KiB

diversity

    #include "bits/stdc++.h"
    using namespace std;
     
    #define ar array
    #define ll int64_t
     
    const int N = 3e5 + 5;
    const int Q = 5e4 + 5;
    const int B = 1350;
    int a[N], l[Q], r[Q], cnt[N];
    int is[N], mm[N];
    ll res[Q], dp[N];
     
    signed main(){
    	ios::sync_with_stdio(0); cin.tie(0);
    	
    	int n, q; cin>>n>>q;
    	vector<int> p;
    	for(int i=0;i<n;i++){
    		cin>>a[i];
    	}
    	for(int i=1;i<N;i++){
    		dp[i] = dp[i-1] + (i * 1ll * (i - 1) / 2);
    	}
    	for(int i=0;i<q;i++){
    		cin>>l[i]>>r[i];
    		l[i]--;
    		p.push_back(i);
    	}
    	sort(p.begin(), p.end(), [&](int i, int j){
    		if(l[i] / B != l[j] / B){
    			return l[i] < l[j];
    		} 
    		return r[i] < r[j];
    	});
    	
    	set<int> ss;
    	auto add = [&](int i){
          	int& cur = cnt[a[i]];
    		if(cur){
    			mm[cur]--;
    			if(!mm[cur]) ss.erase(cur);
    		} 
    		cur++;
    		if(!mm[cur]) ss.insert(cur);
    		mm[cur]++;
    	};
    	auto del = [&](int i){
    		//~ assert(cnt[a[i]]);
    		mm[cnt[a[i]]]--;
    		if(!mm[cnt[a[i]]]) ss.erase(cnt[a[i]]);
    		cnt[a[i]]--;
    		if(cnt[a[i]]){
    			if(!mm[cnt[a[i]]]) ss.insert(cnt[a[i]]);
    			mm[cnt[a[i]]]++;
    		}
    	};
    	
    	int lx = 0, rx = 0;
    	for(auto i : p){
    		if(rx > r[i]){ 
    			ss.clear();
    			lx = rx = l[i];
    			memset(cnt, 0, sizeof cnt);
    			memset(mm, 0, sizeof mm);
    		}
    		while(rx < r[i]){
    			add(rx++);
    		}
    		while(lx > l[i]){
    			add(--lx);
    		}
    		while(lx < l[i]){
    			del(lx++);
    		}
    		
    		int ls = 0, rs = 0;
    		vector<ar<ll, 2>> L, R;
    		for(auto v : ss){
    			int c = mm[v];
    			int b = (c + 1) / 2, s = c / 2;
    			if(ls > rs) swap(b, s);
    			if(b) L.push_back({v, b}), ls += b;
    			if(s) R.push_back({v, s}), rs += s;
    		}
    		reverse(R.begin(), R.end());
    		L.insert(L.end(), R.begin(), R.end());
    		ll sum = 0, sumj = 0, p = 0;
    		for(auto [v, c] : L){
    			ll C = p * c + c * (c - 1) / 2;
    			res[i] = res[i] + v * C * sum - v * c * sumj;
    			res[i] += dp[c] * v * v;
    			sumj += v * C;
    			sum += v * c;
    			p += c;
    		}
    		
    		res[i] += sum * (sum + 1) / 2;
    	}
    	
    	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
    }
     

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36