AcWing 2492. HH的项链
原题链接
困难
作者:
moran236
,
2021-09-03 14:29:24
,
所有人可见
,
阅读 372
算法1
(莫队) $O(nsqrtn)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1E6 + 7;
int n, m, sum, block;
int arr[N], cnt[N];
int ans[N];
struct node
{
int l, r, id;
bool operator<(const node &t) const
{
if (l / block == t.l / block)
return r < t.r;
return l / block < t.l / block;
}
} q[N];
void update(int pos, int n)
{//只有新加的和最后一个退场
int val = arr[pos];
if (n == 1){
if(cnt[val]==0)
sum++;
}
else{
if(cnt[val]==1)
sum--;
}
cnt[val] += n;
}
int main()
{
cin >> n;
block = sqrt(n);
for (int i = 1; i <= n; i++)
cin >> arr[i];
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + 1 + m);
int l = q[1].l;
int r = q[1].l - 1;
for (int i = 1; i <= m; i++)
{
while (l > q[i].l)
update(--l, 1);
while (r < q[i].r)
update(++r, 1);
while (l < q[i].l)
update(l++,-1);
while (r > q[i].r)
update(r--,-1);
ans[q[i].id] = sum;
}
for(int i=1;i<=m;i++){
cout << ans[i] << endl;
}
}