Created
June 30, 2018 17:02
-
-
Save Thiago4532/85e6805837acd6bd20ce838f8c358d0e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
const int maxn = 1e5 + 10, maxs = 400; | |
int n, q, k, vet[maxn], bloco[maxn], ans[maxn][maxs]; | |
int block; | |
inline int ini(int b){ | |
return ((b-1)*block) + 1; | |
} | |
inline int fim(int b){ | |
return min(n, ini(b+1) - 1); | |
} | |
int main(){ | |
ios::sync_with_stdio(false), cin.tie(0); | |
cin >> n >> q; | |
block = sqrt(n); | |
for(int i=1;i<=n;i++){ | |
cin >> vet[i]; | |
k = max(k, vet[i]); | |
bloco[i] = ((i-1)/block) + 1; | |
} | |
for(int i=1;i<=n;i++){ | |
ans[vet[i]][bloco[i]]++; | |
} | |
while(q--){ | |
int p; | |
cin >> p; | |
if(p == 1){ | |
int x, w; | |
cin >> x >> w; | |
ans[vet[x]][bloco[x]]--; | |
ans[w][bloco[x]]++; | |
vet[x] = w; | |
}else{ | |
int l, r, w; | |
cin >> l >> r >> w; | |
if(bloco[r] - bloco[l] <= 1){ | |
int resp=0; | |
for(int i=l;i<=r;i++) | |
resp += (vet[i] == w); | |
cout << (r-l+1)-resp << "\n"; | |
}else{ | |
int b1=bloco[l]+1; | |
int b2=bloco[r]-1; | |
int resp=0; | |
for(int i=b1;i<=b2;i++) | |
resp += ans[w][i]; | |
for(int i=l;i<=fim(bloco[l]);i++) | |
resp += (vet[i] == w); | |
for(int i=ini(bloco[r]);i<=r;i++) | |
resp += (vet[i] == w); | |
cout << (r-l+1)-resp << "\n"; | |
} | |
} | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
yai gld