P1972 [SDOI2009] HH的项链

https://www.luogu.com.cn/problem/P1972

莫队算法被卡，只能得60points

正解有点像基于贪心的fenwick tree策略
fenwick的每个位置表示当前位置上是否是某个数的最后一次出现位置，值为0或者1

右指针升序排序，然后右指针移动过程中更新每个数最后一次出现的位置
而不管左指针如何变，只要保证右指针是非递减的，就可以直接使用区间查询来得到区间中不同元素的数量了

/*
* FenwickTree(树状数组)
* 设计思想：基于二进制表示的下标的快速变换来实现前缀和的计算，适用于差分后的区间修改单点查询，单点修改区间查询。
* 基于面向对象的编程思想，本方法尽可能多的隐藏了内部实现的细节，并且将必要的编程接口暴露在外部，并需要对这些接口进行直接的修改。
* 在该设计中，基础的方法都已实现，如有需要用户可以自行在该结构上进行改进。
*
* gitHub(仓库地址): https://github.com/yxc-s/programming-template.git
*/










/*
该树总是约定区间左端点从1开始(避免lowbit(0)的情况)。
如果已有数组，建议使用已有的数组实例化对象，时间复杂度更低。
注意初始化数组时容器为int和longlong的区别。
*/

class FenwickTree {
public:
    /* 按区间最大右端点下标构造。*/
    FenwickTree(unsigned int n) : n_(n) {
        ft_.resize(n_);
    }

    /* 基于已有的数组构造。*/
    FenwickTree(const std::vector<long long>& f) {
        n_ = static_cast<int>(f.size());
        ft_.assign(n_, 0);
        for (int i = 1; i < n_; ++i) {
            ft_[i] += f[i];
            if (i + lowbit(i) < n_) {
                ft_[i + lowbit(i)] += ft_[i];
            }
        }
    }

    /* 移动构造，减少一次资源分配 */
    FenwickTree(std::vector<long long>&& f) {
        n_ = static_cast<int>(f.size());
        ft_ = std::move(f);
        for (int i = 1; i < n_; ++i) {
            if (i + lowbit(i) < n_) {
                ft_[i + lowbit(i)] += ft_[i];
            }
        }
    }

    /* 按数组元素出现频次构造*/
    FenwickTree(const std::vector<int>& s) {
        n_ = *std::max_element(s.begin() + 1, s.end()) + 1;
        ft_.resize(n_);
        for (size_t i = 1; i < s.size(); ++i) {
            ft_[s[i]]++;
            if (s[i] + lowbit(s[i]) < n_) {
                ft_[s[i] + lowbit(s[i])] += ft_[s[i]];
            }
        }
    }

    /* 单点更新。 */
    void update(int pos, long long value) {
        assert(pos > 0);
        while (pos < n_) {
            ft_[pos] += value;
            pos += lowbit(pos);
        }
    }

    /* 区间更新。*/
    void update(int l, int r, long long value) {
        assert(l > 0 && r >= l);
        update(l, value);
        update(r + 1, -value);
    }

    /* 单点查询。*/
    long long query(int p) {
        assert(p < n_);
        long long res = 0;
        while (p > 0) {
            res += ft_[p];
            p -= lowbit(p);
        }
        return res;
    }

    /* 区间查询。*/
    long long query(int l, int r) {
        assert(l <= r);
        return query(r) - query(l - 1);
    }


private:
    int n_;
    std::vector<long long>  ft_;


private:
    int lowbit(int x) const noexcept{ return (x & (-x)); }
};



using namespace std;
inline void preProcess() {

}


void solve(){
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    int m;
    cin >> m;
    vector<pair<int, int>> querys(m);

    for (int i = 0; i < m; ++i) {
        cin >> querys[i].first >> querys[i].second;
    }

    vector<int> pos(m);
    iota(pos.begin(), pos.end(), 0);
    
    sort(pos.begin(), pos.end(), [&](const int i, const int j) {
        return querys[i].second < querys[j].second;
    });

    int s = *max_element(a.begin() + 1, a.end());
    FenwickTree ft(n + 1);
    vector<int> vis(s + 1, -1);
    int r = 0;
    vector<int> ans(m);
    for (const auto& idx : pos) {
        const auto&[x, y] = querys[idx];
        while (r < y) {
            r ++;
            if (vis[a[r]] == -1){    
                ft.update(r, 1);
            }
            else {
                ft.update(vis[a[r]], -1);
                ft.update(r, 1);
            }
            vis[a[r]] = r;
        }
        ans[idx] = ft.query(y) - ft.query(x - 1);
    }

    for (const auto& x : ans) {
        cout << x << '\n';
    }
}