LuoguP4690 镜中的昆虫 题解

早年看到过这道题,当时用珂朵莉树试着暴力草过但是失败了QAQ

人生第一次树套树祭。

区间数颜色的话可以记一个pre[i]表示左侧第一个与i同色的位置。由于相同颜色只算一次,因此统计时只统计区间从左到右第一次出现该颜色的位置。

则问题转化成区间内有多少个i使得l≤i≤r且0≤pre [i]<l。若将每个(i, pre[i])看成一个点,则此问题变成了二维矩形数点问题,采用树套树直接解决。

区间修改的话使用类似珂朵莉树的思想暴力修改,则pre数组的改变次数可以被证明最多是O(n+m)次

这里只是借用了珂朵莉树的思想,复杂度是可证而不是玄学。

戳这里看代码
#include <bits/stdc++.h>
#define KIT set<Kutori>::iterator
#define IT set<int>::iterator
using namespace std;
const int MAXN = 4e5 + 50;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) +(x << 1) + ch - 48;
}
set <int> ima; map <int, int> mp;
int M, pre[MAXN], n, Q, cntcol, a[MAXN];
struct Kutori {
	int l, r, val;
	Kutori(int _l = 0, int _r = 0, int _val = 0): l(_l), r(_r), val(_val) {}
	bool operator < (const Kutori &b) const {return l < b.l;}
};
struct Ctholly_Tree {
	set <Kutori> st[MAXN], all;
	void Insert(int l, int r, int col) {st[col].insert(Kutori(l, r)); all.insert(Kutori(l, r, col));}
	void Erase(Kutori x) {st[x.val].erase(x); all.erase(x);}
	void Split(int x) {
		KIT it = all.upper_bound(Kutori(x)); --it;		
		if(it->l == x) return;
		Kutori tmp = *it; Erase(tmp);
		Insert(tmp.l, x-1, tmp.val); Insert(x, tmp.r, tmp.val);
	}
} CT;
struct Val_JZMTree {
	int s[MAXN << 6], ls[MAXN << 6], rs[MAXN << 6], cnt;
	void update(int &u, int l, int r, int pos, int val) {
		s[u ? u : u = ++cnt] += val;
		if(l == r) return; int mid = (l + r) >> 1;
		pos <= mid ? update(ls[u], l, mid, pos, val) : update(rs[u], mid+1, r, pos, val);
	}
	int query(int u, int l, int r, int k) {
		if(!u || k == r) return s[u]; int mid = (l + r) >> 1;
		return k <= mid ? query(ls[u], l, mid, k) : s[ls[u]] + query(rs[u], mid+1, r, k);
	}
} VAL;
struct Pos_BIT {
	int rt[MAXN];
	void update(int x, int l, int v) {for(; x <= n; x += x&-x) VAL.update(rt[x], 0, M, l, v);}
	int Q(int x, int k) {int res = 0; for(; x; x -= x&-x) res += VAL.query(rt[x], 0, M, k); return res;}
	int query(int l, int r, int k) {return Q(r, k) - Q(l-1, k);}
} POS;
void Up(int x, int val) {POS.update(x, pre[x], -1); pre[x] = val; POS.update(x, pre[x], 1);}
void Modify(int l, int r, int x) {
	CT.Split(l); if(r < n) CT.Split(r+1);
	ima.clear(); ima.insert(x);
	while("lxldl") {
		KIT it = CT.all.lower_bound(Kutori(l));
		if(it == CT.all.end() || it->l > r) break;
		Kutori tmp = *it; ima.insert(tmp.val);
		if(tmp.l > l && pre[tmp.l] != tmp.l-1) Up(tmp.l, tmp.l-1);
		CT.Erase(tmp);
	}
	KIT it = CT.st[x].lower_bound(Kutori(l)); Up(l, (--it)->r);
	CT.Insert(l, r, x);
	for(IT it2 = ima.begin(); it2 != ima.end(); ++it2) {
		it = CT.st[*it2].upper_bound(Kutori(r));
		if(it == CT.st[*it2].end()) continue;
		int pos = it->l;
		it = CT.st[*it2].lower_bound(Kutori(pos));
		Up(pos, (--it)->r);
	}
}
int main() {
	read(n); read(Q); M = n + Q;
	for(int i = 1; i <= n; ++i) {
		read(a[i]);
		if(!mp[a[i]]) CT.st[mp[a[i]] = ++cntcol].insert(Kutori());
		a[i] = mp[a[i]];
	}
	for(int i = 1; i <= n; ++i) {
		KIT it = CT.st[a[i]].end(); --it; pre[i] = it->l;
		POS.update(i, pre[i], 1); CT.Insert(i, i, a[i]);
	}
	for(int opt, l, r, x; Q--; ) {
		read(opt); read(l); read(r);
		if(opt == 1) {
			read(x);
			if(!mp[x]) CT.st[mp[x] = ++cntcol].insert(Kutori());
			x = mp[x]; Modify(l, r, x);
		} else printf("%d\n", POS.query(l, r, l-1));
	}
}

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00