Submission #577358

#	Time	Username	Problem	Language	Result	Execution time	Memory
577358		rembocoder	Diversity (CEOI21_diversity)	C++17	64 / 100	7029 ms	7552 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]]);
              	int& cur = cnt[a[i]];
        		mm[cur]--;
        		if(!mm[cur]) ss.erase(cur);
        		cur--;
        		if(cur){
        			if(!mm[cur]) ss.insert(cur);
        			mm[cur]++;
        		}
        	};
        	
        	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: 0 / 36