\(\text{Solution}\)

一看有区间赋值直接上 \(ODT\)

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#include <set>

#define re register

using namespace std;

int n;

struct node{

	int l, r; mutable int v;

	inline node(int l, int r, int v):l(l), r(r), v(v){};

	inline bool operator < (const node &a) const {return l < a.l;}

};

set<node> T;

typedef set<node>::iterator IT;

inline IT split(int x)

{

	if (x > n) return T.end();

	IT it = --T.upper_bound((node){x, 0, 0});

	if (it->l == x) return it;

	int l = it->l, r = it->r, v = it->v;

	T.erase(it), T.insert((node){l, x - 1, v});

	return T.insert((node){x, r, v}).first;

}

inline void assign(int l, int r, int v)

{

	IT itr = split(r + 1), itl = split(l);

	T.erase(itl, itr), T.insert(node{l, r, v});

}

inline int Query(int l, int r, int v)

{

	IT itr = split(r + 1), itl = split(l); int res = 0;

	for(re IT it = itl; it != itr; ++it)

	if (it->v == v) res += it->r - it->l + 1;

	return res;

}

inline void read(int &x)

{

	x = 0; char ch = getchar(); int f = 1;

	for(; !isdigit(ch); f = (ch == '-' ? -1 : f), ch = getchar());

	for(; isdigit(ch); x = (x<<3) + (x<<1) + (ch^48), ch = getchar());

	x *= f;

}

int main()

{

	read(n);

	for(re int i = 1, x; i <= n; i++) read(x), T.insert((node){i, i, x});

	for(re int i = 1, l, r, v; i <= n; i++)

		read(l), read(r), read(v), printf("%d\n", Query(l, r, v)), assign(l, r, v);

}

巴特西

LOJ 数列分块入门 8

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章