fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ff first
  5. #define ss second
  6. #define pb push_back
  7.  
  8. const int N=2e5+7;
  9. ll mod=1e9+7;
  10. ll ax[8]={0,0,-1,+1,-1,-1,1,1};
  11. ll ay[8]={-1,1,0,0,-1,1,-1,1};
  12. ll kx[8]={2,2,-2,-2,1,1,-1,-1};
  13. ll ky[8]={1,-1,1,-1,2,-2,2,-2};
  14.  
  15. struct query{
  16. 	ll id,l,r,t;
  17. }Q[N];
  18. struct update{
  19. 	ll pos,old,cur;
  20. }U[N];
  21. ll ans[N],a[N],last[N],cnt[N],l,r,t,dis;
  22. void add(ll val){
  23. 	cnt[val]++;
  24. 	if(cnt[val]==1) dis++;
  25. 	if(cnt[val]==2) dis--;
  26. }
  27. void del(ll val){
  28. 	cnt[val]--;
  29. 	if(cnt[val]==1) dis++;
  30. 	if(cnt[val]==0) dis--;
  31. }
  32. void update(ll val,ll pos,ll t){
  33. 	U[t].old=a[pos];
  34. 	if(pos>l && pos<=r) {add(val);del(a[pos]);}
  35. 	a[pos]=val;		
  36. }
  37. int main(){
  38. 	ios::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     ll tt=1;
  41.     //cin>>tt; 
  42.     while(tt--){
  43.     	ll i,j,n,q,s=0;
  44.     	cin>>n>>q;
  45.     	dis=0;
  46.     	ll sz= pow(n, 2./3.)+1;
  47.     	for(i=0;i<n;i++){
  48.     		cin>>a[i];last[i]=a[i];
  49.     	}
  50.     	ll up=0,qlen=0;
  51.     	for(i=0;i<q;i++){
  52.     		ll x,y,z;
  53.     		cin>>x>>y>>z;
  54.     		if(x==1){
  55.     			U[++up]={y,last[y],z};
  56.     			last[y]=z;    			
  57.     		}
  58.     		else{
  59.     			Q[++qlen]={qlen,y,z,up};    			
  60.     		}
  61.     	}
  62.     	sort(Q+1,Q+qlen+1,[&](query a,query b){
  63.     		if((a.l)/sz==(b.l)/sz){
  64.             if((a.r)/sz==(b.r)/sz) return a.t<b.t;
  65.             return ((a.r)/sz)<((b.r)/sz);
  66.          }
  67.          return (a.l)<(b.l);
  68.     	});
  69.     	l=-1,r=-1,t=0;
  70.     	for(i=1;i<=qlen;i++){
  71.     		ll ql=Q[i].l-1,qr=Q[i].r,qt=Q[i].t;
  72.     		while(t<qt) {t++;update(U[t].cur,U[t].pos,t);}
  73.     		while(t>qt) {update(U[t].old,U[t].pos,t);t--;} 
  74.     		while(l<ql) del(a[++l]); 
  75.     		while(l>ql) add(a[l--]);
  76.     		while(r>qr) del(a[r--]);
  77.     		while(r<qr) add(a[++r]);
  78.     		//cout<<Q[i].id<<" "<<i<<" "<<ql<<" "<<qr<<" "<<qt<<" "<<dis<<endl;
  79.     		ans[Q[i].id]=dis; 		
  80.     	}
  81.     	for(i=1;i<=qlen;i++) cout<<ans[i]<<"\n";
  82. 	}
  83. 	return 0;
  84. }
Success #stdin #stdout 0.01s 11972KB
comments (?)
stdin
copy 
8 8
1 2 3 3 1 2 3 3
2 1 3
2 0 3 
2 0 7
1 3 4
1 7 0
2 1 3
2 0 3 
2 0 7
stdout
copy 
1
2
0
3
4
2
https://ideone.com/rn5QP1
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!