区间不同数的个数 二维数点 扫描线 可持久化线段树

二维数点，对于询问的\([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;
}