Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 500005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n, m, bsize;
- int a[N];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n >> m;
- for(int i=1; i<=n; i++) cin >> a[i];
- }
- void compress(){
- vector<int> b(a+1,a+1+n);
- sort(all(b));
- b.erase(unique(all(b)),b.end());
- for(int i=1; i<=n; i++){
- int k = lower_bound(all(b),a[i])-b.begin();
- a[i] = b[k];
- }
- }
- struct query{
- int l, r;
- int idx;
- bool operator < (const query& a){
- if ((l-1)/bsize != (a.l-1)/bsize) return (l-1)/bsize < (a.l-1)/bsize;
- return r < a.r;
- }
- };
- query Q[N];
- int nho[N];
- int ans=0;
- int res[N];
- void add(int pos){
- nho[a[pos]]++;
- if (nho[a[pos]]==2) ans++;
- if (nho[a[pos]]==3) ans--;
- }
- void del(int pos){
- nho[a[pos]]--;
- if (nho[a[pos]]==2) ans++;
- if (nho[a[pos]]==1) ans--;
- }
- void proc()
- {
- compress();
- bsize = sqrt(n)+1;
- for(int i=1; i<=m; i++){
- cin >> Q[i].l >> Q[i].r;
- Q[i].idx = i;
- }
- sort(Q+1,Q+1+m);
- int l=0, r=0;
- for(int i=1; i<=m; i++){
- int u = Q[i].l;
- int v = Q[i].r;
- int id = Q[i].idx;
- while (l > u) add(--l);
- while (l < u) del(l++);
- while (r < v) add(++r);
- while (v < r) del(r--);
- res[id] = ans;
- }
- for(int i=1; i<=m; i++) cout << res[i] << '\n';
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement