#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) (long long)(x.size())
using namespace std;
const ll N = 5e5 + 9;
ll n, i, q, l, r, a[N], ans[N], dem[N];
vector<ll>vec;
void calc( ll l, ll r )
{
for( int w = l; w <= r; w ++ ) dem[a[w]] ++;
for( int w = l; w <= r; w ++ )
{
ans[i] += (dem[a[w]] == 2);
dem[a[w]] = 0;
}
}
struct abc{
ll l, r, id;
};
vector<abc>save[N];
bool cmp( abc x, abc y )
{
return x.r < y.r;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for( i = 1; i <= n; i ++ )
cin >> a[i], vec.pb(a[i]);
sort(all(vec));
for( i = 1; i <= n; i ++ ) a[i] = lower_bound(all(vec), a[i]) - vec.begin();
ll c = sqrt(n);
if(c * c != n) c ++;
for( i = 1; i <= q; i ++ )
{
cin >> l >> r;
if(r - l + 1 <= c)
{
calc(l, r);
continue;
}
ll block = l / c + (l % c != 0);
save[block].pb({l, r, i});
}
for( i = 1; i <= c + 2; i ++ )
sort(all(save[i]), cmp);
for( i = 1; i <= c + 2; i ++ )
{
if(sz(save[i]) == 0) continue;
ll x = (i - 1) * c + 1, y = min(n, i * c);
ll cnt = 0;
ll vt = y + 1;
for(auto k : save[i])
{
ll l = k.l, r = k.r;
for( int w = l; w <= y; w ++ )
{
dem[a[w]] ++;
cnt += (dem[a[w]] == 2);
cnt -= (dem[a[w]] == 3);
}
while(vt <= r)
{
dem[a[vt]] ++;
cnt += (dem[a[vt]] == 2);
cnt -= (dem[a[vt]] == 3);
vt ++;
}
ans[k.id] = cnt;
for( int w = l; w <= y; w ++ )
{
dem[a[w]] --;
cnt += (dem[a[w]] == 2);
cnt -= (dem[a[w]] == 1);
}
}
}
for( i = 1; i <= q; i ++ )
cout << ans[i] << "\n";
return 0;
}
/*
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |