二维数点，对于询问的\([l, r]\)区间我们只需要统计有多少个数上一次出现的位置\(pos\) 满足\(pos \leq l\)，即可。
template<class T>
struct BIT {
T c[N];
int size;
void resize(int s) { size = s;}
T query(int x) { // 1 ... x
assert(x <= size);
T s = 0;
for (; x; x -= x & (-x)) {
s += c[x];
}
return s;
}
void modify(int x, T s) { // a[x] += s
assert(x != 0);
for (; x <= size; x += x & (-x)) {
c[x] += s;
}
}
};
BIT<int> tr;
int n, q, pos[N];
int a[N], ans[N];
vector<pii> qu[N];
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++) cin>>a[i];
cin>>q;
for(int i = 1; i <= q; i++)
{
int l, r; cin>>l>>r;
qu[r].pb({l, i});
}
tr.resize(n);
for(int r = 1; r <= n; r++)
{
int last = pos[a[r]];
tr.modify(last + 1, 1);
tr.modify(r + 1, -1);
for(auto it : qu[r])
ans[it.second] = tr.query(it.fi);
pos[a[r]] = r;
}
for(int i = 1; i <= q; i++)
cout<<ans[i]<<endl;
return;
}
扫描线
对数组预处理这个数上一次出现的位置，然后进行常规的扫描线操作
为什么（代码这样写）可以这样做，区间\([l,r]\)答案为\([1,r] - [1, l - 1]\)，而在排序中，我们数组存的第一关键字是上一次出现的位置，所以始终第一个出现在\([l,r]\)区间的数会快询问一步在树状数组进行modify，保证一个数只会被算到一次
template<class T>
struct BIT {
T c[N];
int size;
void resize(int s) { size = s;}
T query(int x) { // 1 ... x
assert(x <= size);
T s = 0;
for (; x; x -= x & (-x)) {
s += c[x];
}
return s;
}
void modify(int x, T s) { // a[x] += s
assert(x != 0);
for (; x <= size; x += x & (-x)) {
c[x] += s;
}
}
};
BIT<int> tr;
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
event.pb({pre[a[i]], 0, i});
pre[a[i]] = i;
}
cin>>q;
for(int i = 1; i <= q; i++)
{
int l, r; cin>>l>>r;
event.pb({l, -1, r, i});
}
sort(all(event));
tr.resize(n);
for(auto eve : event)
{
if(eve[1] == 0)
{
tr.modify(eve[2], 1);
}
else
{
ans[eve[3]] -= tr.query(eve[0] - 1);
ans[eve[3]] += tr.query(eve[2]);
}
}
for(int i = 1; i <= q; i++)
cout<<ans[i]<<endl;
return;
}