Участник:ArtemTovkes/ADAUNIQ

Материал из DISCOPAL
Перейти к: навигация, поиск

C++ (gcc 8.3) https://www.spoj.com/problems/ADAUNIQ/

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2*1e5 + 10;
const int BUCKET = 3430;
struct que{
	int id,l,r,t;
};
struct upd{
	int pos,anc,cur;
};
int divis[MAXN],mo_left,mo_right,mo_time,n,q,freq[MAXN],exhibit[MAXN],vect[MAXN],resp;
vector<que> Q;
vector<upd> U;
bool compare(que A,que B){
	if(divis[A.l] != divis[B.l]) return divis[A.l] < divis[B.l];
	if(divis[A.r] != divis[B.r]) return divis[A.r] < divis[B.r];
	return A.t < B.t;
}
void add(int val){
	freq[val]++;
	if(freq[val] == 1) resp++;
	else if(freq[val] == 2) resp--;
}
void remove(int val){
	freq[val]--;
	if(freq[val] == 1) resp++;
	else if(freq[val] == 0) resp--;
}
void update(int idx,int cur){
	if(mo_left <= idx && idx <= mo_right){
		remove(vect[idx]);
		vect[idx] = cur;
		add(vect[idx]);
	}
	else{
		vect[idx] = cur;
	}
}
void doQuery(int idx){
	for(int t = mo_time + 1;t <= Q[idx].t;t++) update(U[t-1].pos,U[t-1].cur);
	for(int t = mo_time;t > Q[idx].t;t--) update(U[t-1].pos,U[t-1].anc);
	for(int i = mo_right + 1;i<=Q[idx].r;i++) add(vect[i]);
	for(int i = mo_left - 1;i>=Q[idx].l;i--) add(vect[i]);
	for(int i = mo_right;i>Q[idx].r;i--) remove(vect[i]);
	for(int i = mo_left;i<Q[idx].l;i++) remove(vect[i]);
	mo_left = Q[idx].l;mo_right = Q[idx].r;mo_time = Q[idx].t;
	exhibit[Q[idx].id] = resp;
}
int main(){
	scanf("%d %d",&n,&q);
	for(int i = 0;i<n;i++){
		scanf("%d",&vect[i]);
		divis[i] = i/BUCKET;
	}
	for(int i = 0;i<q;i++){
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		if(x == 1){
			mo_time++;
			upd dav;
			dav.pos = y;
			dav.anc = vect[y];
			dav.cur = z;
			vect[y] = z;
			U.push_back(dav);
			exhibit[i] = -1;
		}
		else{
			que dav;
			dav.l = y;
			dav.r = z;
			dav.t = mo_time;
			dav.id = i;
			Q.push_back(dav);
		}
	}
	sort(Q.begin(),Q.end(),compare);
	for(int i = 0;i<n;i++) add(vect[i]);
	mo_left = 0;mo_right = n-1;
	for(int i = 0;i<Q.size();i++) doQuery(i);
	for(int i = 0;i<q;i++) if(exhibit[i] != -1) printf("%d\n",exhibit[i]);
	return 0;
}