P4690 [Ynoi2016] 镜中的昆虫

区间赋值区间数颜色，\(n \leq 10^5\)，值域 \([1,10^9]\)，要求线性空间。

sol

首先考虑经典数颜色套路，设 \(pre_i\) 表示上一个与 \(a_i\) 相同的数的位置。

对于区间赋值操作，我们发现性质：\(\forall i\in(l,r],pre_i ←i-1\)，对于 \(i=l\) 或区间外的情况特判即可。

考虑使用 ODT 维护 \(pre\) 的修改，一个 ODT 维护序列，一个 ODT 数组维护颜色位置，均摊修改次数为 \(\mathcal O(n)\)（增加节点总数 \(\mathcal O(n)\)，删除节点总数 \(\mathcal O(n)\)），时间复杂度 \(\mathcal O(n\log n)\)。

那么问题转化为带修求 \(\sum\limits_{i=l}^{r}[pre_i<l]\)，考虑到要求线性空间，故使用三维 cdq，时间复杂度 \(\mathcal O(n \log^2 n)\)。

时间复杂度 \(\mathcal O(n \log ^2 n)\)，空间复杂度 \(\mathcal O(n)\)。

详见代码。

#include <bits/stdc++.h>

using namespace std;

namespace Fread
{
	const int SIZE = 1 << 21;
	char buf[SIZE], *S, *T;
	inline char getchar()
	{
		if (S == T)
		{
			T = (S = buf) + fread(buf, 1, SIZE, stdin);
			if (S == T)
				return '\n';
		}
		return *S++;
	}
}

namespace Fwrite
{
	const int SIZE = 1 << 21;
	char buf[SIZE], *S = buf, *T = buf + SIZE;
	inline void flush()
	{
		fwrite(buf, 1, S - buf, stdout);
		S = buf;
	}
	inline void putchar(char c)
	{
		*S++ = c;
		if (S == T)
			flush();
	}
	struct NTR
	{
		~NTR()
		{
			flush();
		}
	} ztr;
}

#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif

inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}

inline void write(int x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + 48);
}

const int _ = 2e5 + 10, M = 1e6 + 10;

int n, m, tot, a[_], cnt, b[_], ans[_], d[_], pre[_];

struct Query
{
	int opt, l, r, x;
} q[_];

struct Node
{
	int x, y, z, k, d, ans;
	inline bool operator < (const Node &t) const
	{
		return x != t.x ? x < t.x : (y != t.y ? y < t.y : z < t.z);
	}
} p[M], c[M >> 1];

#define pii pair<int, int>
#define pa set<pii>::iterator

struct Col
{
	set<pii> cl, v[_];
	inline void split(int k)
	{
		pa it = cl.lower_bound({k + 1, 0});
		int r = it->first - 1;
		--it;
		int l = it->first;
		if(k == r) return;
		int c = it->second;
		cl.erase(it);
		cl.insert({l, c});
		cl.insert({k + 1, c});
		v[c].erase({l, r});
		v[c].insert({l, k});
		v[c].insert({k + 1, r});
	}
	inline void Insert(int l, int r, int c, int t)
	{
		split(l - 1), split(r);
		for(pa it = cl.lower_bound({l, 0}); it-> first <= r;)
		{
			int x = it->first, y = it->second;
			++it;
			int z = it->first - 1;
			cl.erase({x, y});
			v[y].erase({x, z});
			if(x == l)
			{
				int e = (--(v[c].upper_bound({x, 0})))->second;
				if(pre[x] != e)
				{
					p[++tot] = {t, x, pre[x], 0, -1, 0};
					pre[x] = e;
					p[++tot] = {t, x, pre[x], 0, 1, 0};
				}
			}
			else
			{
				if(pre[x] != x - 1)
				{
					p[++tot] = {t, x, pre[x], 0, -1, 0};
					pre[x] = x - 1;
					p[++tot] = {t, x, pre[x], 0, 1, 0};
				}
			}
			x = z + 1;
			z = (v[y].lower_bound({x, 0}))->first;
			int e = (--v[y].lower_bound({l, 0}))->second;
			if(z > r && z <= n && pre[z] != e)
			{
				p[++tot] = {t, z, pre[z], 0, -1, 0};
				pre[z] = e;
				p[++tot] = {t, z, pre[z], 0, 1, 0};
			}
		}
		pa it = v[c].lower_bound({r + 1, 0});
		int x = it->first;
		if(x <= n && pre[x] != r)
		{
			p[++tot] = {t, x, pre[x], 0, -1, 0};
			pre[x] = r;
			p[++tot] = {t, x, pre[x], 0, 1, 0};
		}
		v[c].insert({l, r});
		cl.insert({l, c});
		x = r + 1;
		if(x <= n)
		{
			it = cl.lower_bound({x, 0});
			int y = it->second;
			int e = (--v[y].lower_bound({x, 0}))->second;
			if(pre[x] != e)
			{
				p[++tot] = {t, x, pre[x], 0, -1, 0};
				pre[x] = e;
				p[++tot] = {t, x, pre[x], 0, 1, 0};
			}
		}
	}
} col;

inline void update(int x, int v)
{
	++x;
	while(x < _) d[x] += v, x += x & -x;
}

inline int query(int x)
{
	++x;
	int res = 0;
	while(x) res += d[x], x -= x & -x;
	return res;
}

void solve(int l, int r)
{
	if(l >= r) return;
	int mid = (l + r) >> 1;
	solve(l, mid), solve(mid + 1, r);
	int i = l, j = mid + 1, k = 0;
	bool flg = (l != 1 || r != tot);
	while(i <= mid && j <= r)
		if(p[i].y <= p[j].y)
	{
		if(p[i].k == 0) update(p[i].z, p[i].d);
		if(flg) c[k++] = p[i];
		++i;
	}
	else
	{
		if(p[j].k == 1) p[j].ans += query(p[j].z);
		if(flg) c[k++] = p[j];
		++j;
	}
	while(i <= mid)
	{
		if(p[i].k == 0) update(p[i].z, p[i].d);
		if(flg) c[k++] = p[i];
		++i;
	}
	while(j <= r)
	{
		if(p[j].k == 1) p[j].ans += query(p[j].z);
		if(flg) c[k++] = p[j];
		++j;
	}
	for(int i = l; i <= mid; ++i) if(p[i].k == 0) update(p[i].z, -p[i].d);
	if(flg) for(int i = 0; i < k; ++i) p[i + l] = c[i];
}

signed main()
{
	n = cnt = read(), m = read();
	for(int i = 1; i <= n; ++i) a[i] = b[i] = read();
	for(int i = 1; i <= m; ++i)
	{
		q[i].opt = read(), q[i].l = read(), q[i].r = read();
		if(q[i].opt == 1) b[++cnt] = q[i].x = read();
	}
	sort(b + 1, b + cnt + 1);
	cnt = unique(b + 1, b + cnt + 1) - b - 1;
	for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
	for(int i = 1; i <= m; ++i) if(q[i].opt == 1) q[i].x = lower_bound(b + 1, b + cnt + 1, q[i].x) - b;
	for(int i = 1; i <= cnt; ++i) col.v[i].insert({0, 0});
	for(int i = 1; i <= n; ++i)
	{
		pre[i] = (--col.v[a[i]].end())->second;
		p[++tot] = {0, i, pre[i], 0, 1, 0};
		col.v[a[i]].insert({i, i});
		col.cl.insert({i, a[i]});
	}
	for(int i = 1; i <= cnt; ++i) col.v[i].insert({n + 1, 0});
	col.cl.insert({0, 0}), col.cl.insert({n + 1, n + 1});
	for(int i = 1; i <= m; ++i)
		if(q[i].opt == 1) col.Insert(q[i].l, q[i].r, q[i].x, i);
	else p[++tot] = {i, q[i].r, q[i].l - 1, 1, 1, 0}, p[++tot] = {i, q[i].l - 1, q[i].l - 1, 1, -1, 0};
	sort(p + 1, p + tot + 1);
	solve(1, tot);
	for(int i = 1; i <= tot; ++i) if(p[i].k) ans[p[i].x] += p[i].ans * p[i].d;
	for(int i = 1; i <= m; ++i) if(q[i].opt == 2) write(ans[i]), putchar('\n');
	return 0;
}