HH 的项链

链接

恕我无能,这题不看提示真写不来啊~~~

这题还是要用树状数组,(感觉线段树也行?没试过)

不过得稍微变实现的形式,我们把每个数据都看做1就行了,毕竟每个数据的种类只有1个嘛

但是,问题就在重复上,如果出现重复,那其中一个就必须为0才行,不然求和会不对

比如 1 2 3 4 5我们就转换为1 1 1 1 1 ,然后放进树状数组

但是1 2 3 4 2就不一样了,可能是1 0 1 1 1或是1 1 1 1 0,这两者放进树状数组得到的结果有什么区别呢

由于我们习惯性地从左向右遍历,我们发现,前者当查询区间为[left,5]时,用树状数组查询是正确的,后者则不行(除非从右往左)

因此,我们可以这样实现:

将查询的数据按右边从小到大排序,当查询右区间为k时,我们只更新前k个树状数组的数据, 比如 1 2 3 4 2,前四个的树状数组是1 2 1 4,当来到第五个时,我们需要在第二个数据实现减一操作得到 1 1 1 3 1,并且记录此时2的位置(可以用map记录)

代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

vector<int>tree;
vector<int>num;
unordered_map<int, int>last;
int n, m;

int lowbit(int x) {
	return x & -x;
}

int query(int x) {
	int sum = 0;
	for (;x;x -= lowbit(x)) {
		sum += tree[x];
	}
	return sum;
}

void update(int x, int value) {
	for (;x <= n;x += lowbit(x)) {
		tree[x] += value;
	}
}

struct ask {
	int l, r;
	int idx, ans;
	bool operator <(const ask& other)const {
		return r < other.r;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	tree.resize(n + 1, 0);
	num.resize(n + 1);
	for (int i = 1;i <= n;i++) {
		cin >> num[i];
	}
	cin >> m;
	vector<ask>ASK(m);
	for (int i = 0;i < m;i++) {
		cin >> ASK[i].l >> ASK[i].r;
		ASK[i].idx = i;
	}
	sort(ASK.begin(), ASK.end());
	int index = 0;
	for (int i = 1;i <= n;i++) {
		if (last[num[i]] != 0) {//已经出现过,上一次减去1
			update(last[num[i]], -1);
		}
		last[num[i]] = i;//更新位置
		update(last[num[i]], 1);

		while (index < m&&ASK[index].r == i) {
			ASK[index].ans = query(ASK[index].r) - query(ASK[index].l - 1);
			index++;
		}
	}
	sort(ASK.begin(), ASK.end(), [](const ask& x, const ask& y) {
		return x.idx < y.idx;
		});
	for (ask answer : ASK) {
		cout << answer.ans << '\n';
	}
}

时间复杂度:O(n log n + m log m)

空间复杂度:O(n+m)