caioj 1102(线段树)

发表于 | 分类于 | | + s

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

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

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

#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

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