CF981G Magic multisets

CF981G Magic multisets

近似某月赛 E 题 risrqnis。

首先想到树套树，空间爆炸，排除。

用一棵线段树维护区间集合答案，支持 $\times 2$ 和 $+1$ 操作。

怎样维护区间集合添加操作呢，观察到加的数都是同一个数，考虑一个数据结构，建 $n$ 个，维护每个颜色的出现区间，加数即区间推平。

考虑到经典 trick 颜色端均摊，即 ODT，每次推平最多增加 $\mathcal{O}(1)$ 个区间，每个区间删除 $\mathcal{O}(1)$ 次，时间复杂度均摊正确。

综上，ODT 维护颜色的出现区间，线段树维护答案。

时间复杂度 $\mathcal{O}(n)$。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define he putchar('\n')
#define ha putchar(' ')

namespace Fread
{
    const int SIZE = 1 << 23;
    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 << 23;
    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;
	char c = getchar();
	while(c < '0' || c > '9')
		c = getchar();
	while(c >= '0' && c <= '9')
	{
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x;
}

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

const ll _ = 2e5 + 1, mod = 998244353;

int n, q;

int tr[_ << 2], t1[_ << 2], t2[_ << 2];

void build(int o, int l, int r)
{
	if(l == r) return;
	int mid = (l + r) >> 1;
	t1[o] = 0, t2[o] = 1;
	build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r);
}

void push1(int o, int l, int r, ll v)
{
	if(!v) return;
	t1[o] = (t1[o] + v) % mod;
	tr[o] = (tr[o] + 1ll * (r - l + 1) * v) % mod;
}

void push2(int o, ll v)
{
	if(v == 1) return;
	t1[o] = 1ll * t1[o] * v % mod;
	t2[o] = 1ll * t2[o] * v % mod;
	tr[o] = 1ll * tr[o] * v % mod;
}

void pushdown(int o, int l, int r)
{
	int mid = (l + r) >> 1;
	push2(o << 1, t2[o]), push2(o << 1 | 1, t2[o]), t2[o] = 1;
	push1(o << 1, l, mid, t1[o]), push1(o << 1 | 1, mid + 1, r, t1[o]), t1[o] = 0;
}

void upd(int o, int l, int r, int L, int R, int v, int id)
{
	if(L <= l && r <= R)
	{
		if(id == 1) push1(o, l, r, v);
		else push2(o, v);
		return;
	}
	pushdown(o, l, r);
	int mid = (l + r) >> 1;
	if(L <= mid) upd(o << 1, l, mid, L, R, v, id);
	if(R > mid) upd(o << 1 | 1, mid + 1, r, L, R, v, id);
	tr[o] = (tr[o << 1] + tr[o << 1 | 1]) % mod;
}

int qry(int o, int l, int r, int L, int R)
{
	if(L <= l && r <= R) return tr[o];
	pushdown(o, l, r);
	int mid = (l + r) >> 1, res = 0;
	if(L <= mid) res = qry(o << 1, l, mid, L, R);
	if(R > mid) res = (res + qry(o << 1 | 1, mid + 1, r, L, R)) % mod;
	return res % mod;
}

struct Odt
{
	#define It set<odt>::iterator
	struct odt
	{
		int l, r, v;
		odt(int L = 0, int R = 0, int V = 0) { l = L, r = R, v = V; }
		friend bool operator < (const odt &a, const odt &b) { return a.l < b.l; }
	};
	set<odt> s;
	void init() { s.insert(odt(1, n, 0)); }
	It split(int x)
	{
		It it = s.lower_bound(odt(x, 0, 0));
		if(it != s.end() && it -> l == x) return it;
		--it;
		int L = it -> l, R = it -> r, V = it -> v;
		s.erase(it), s.insert(odt(L, x - 1, V));
		return s.insert(odt(x, R, V)).first;
	}
	void assign(int l, int r)
	{
		It itr = split(r + 1), itl = split(l);
		for(It it = itl; it != itr; ++it)
			if(!(it -> v)) upd(1, 1, n, it -> l, it -> r, 1, 1);
			else upd(1, 1, n, it -> l, it -> r, 2, 0);
		s.erase(itl, itr), s.insert(odt(l, r, 1));
	}
} t[_];

signed main()
{
	n = read(), q = read();
	build(1, 1, n);
	for(int i = 1; i <= n; ++i) t[i].init();
	int opt, l, r, x;
	while(q--)
	{
		opt = read(), l = read(), r = read();
		if(opt == 1)
			x = read(), t[x].assign(l, r);
		else
			write(qry(1, 1, n, l, r)), he;
	}
	return 0;
}