caioj 1102(线段树)

caioj 1102
(本题为bzoj 2243弱化版)
线段树维护三个值:

  • $lcol$:区间左端点的颜色
  • $rcol$:区间右端点的颜色
  • $cnt$:区间线段的条数

然后合并区间的时候如果中间颜色相同,要$cnt-1$
查询同理,如果左右区间都更新了,则要判断中间颜色
或者把所有区间先找出来再一一合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 100000 + 5;
int n, Q, col[MAXN];
#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)
int lazy[MAXN * 4], lcol[MAXN * 4], rcol[MAXN * 4], cnt[MAXN * 4];
void pushdown(int o, int l, int r) {
if (l == r) return ;
if (lazy[o]) {
lazy[lc] = lazy[rc] = lazy[o];
lcol[lc] = rcol[lc] = lazy[o];
lcol[rc] = rcol[rc] = lazy[o];
cnt[lc] = cnt[rc] = 1;
lazy[o] = 0;
}
}
void pushup(int o, int l, int r) {
if (l == r) return ;
lcol[o] = lcol[lc], rcol[o] = rcol[rc];
cnt[o] = cnt[lc] + cnt[rc];
if (rcol[lc] == lcol[rc]) cnt[o]--;
}
void build(int o, int l, int r) {
if (l == r) lcol[o] = rcol[o] = col[l], cnt[o] = 1; else {
build(lc, l, M);
build(rc, M + 1, r);
pushup(o, l, r);
}
}
void update(int o, int l, int r, int x, int y, int v) {
pushdown(o, l, r);
if (x <= l && r <= y) {
lcol[o] = rcol[o] = v;
cnt[o] = 1;
lazy[o] = v;
return ;
}
if (x <= M) update(lc, l, M, x, y, v);
if (M < y) update(rc, M + 1, r, x, y, v);
pushup(o, l, r);
}
int inv[MAXN * 4], inv_num;
void query(int o, int l, int r, int x, int y) {
pushdown(o, l, r);
if (x <= l && r <= y) {
inv[++inv_num] = o;
return ;
}
if (x <= M) query(lc, l, M, x, y);
if (M < y) query(rc, M + 1, r, x, y);
}
void clean() {
for (int i = 0; i <= n * 4; i++) lazy[i] = lcol[i] = rcol[i] = cnt[i] = 0;
}
void solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
build(1, 1, n);
while (Q--) {
int opt; scanf("%d", &opt);
if (opt == 1) {
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
if (x > y) swap(x, y);
update(1, 1, n, x, y, k);
} else {
int x, y, ans = 0;
scanf("%d%d", &x, &y);
if (x > y) swap(x, y);
inv_num = 0, query(1, 1, n, x, y);
for (int i = inv_num; i > 0; i--) {
ans += cnt[inv[i]];
if (i - 1 > 0) if (rcol[inv[i - 1]] == lcol[inv[i]]) ans--;
}
printf("%d\n", ans);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &Q), solve();
return 0;
}

题目描述
【题意】
有n(1~100000)个连续的格子,编号为1……n,每个格子的颜色有3种(分别是1、2、3)。
有m(1~100000)操作,操作有2种:
1 x y k:表示第x个格子至第y个格子全染色为k(1<=k<=3)
2 x y:表示询问第x个格子至第y个格子有多少条线段(相邻两个格子的颜色相同则同属一条线段)。
【输入格式】
第一行n和m。
第二行n个数,分别表格n个格子的颜色。
下来m行,每行表示一个操作。
【输出格式】
遇到操作2,则输出答案

【样例输入】
5 5
2 1 1 2 1
2 1 5
1 4 4 1
2 1 5
1 1 1 1
2 1 5
【样例输出】
4
2
1

------ 本文结束 ------