Algoogle

Algorithm for Programming Contest

Codeforces 444C DZY Loves Colors

Category: Codeforces Tag: segment-tree

DZY Loves Colors

問題概要


長さnの帯があり, それは最初位置iの色がiになっている.
この帯のある場所の色をyからxに変えるとき, その位置の鮮やかさが|y-x|だけ増える. 以下のクエリを実装しろ

  1. 区間[l,r]を色xにする

  2. 区間[l,r]の鮮やかさの合計を答える

解法


以下のようなSegment Treeで実装する.

  • 区間に全体に一度に足された鮮やかさ合計値(add)をもつ
  • 区間で足された鮮やかさの合計(sum)をもつ
  • 区間の色がすべて同じときの区間の色(col)をもつ
  • 区間の色を更新する
  • 区間の鮮やかさの合計を答える

区間[l,r)を色xに更新するのは以下のように行う.

  • 現在の区間より上の区間で1色になっていたらその色を現在の区間の色にする
  • 現在の区間が更新後とすでに同じ色なら終了
  • 現在の区間が完全に更新したい区間に含まれているなら

    • 現在の区間が1色ならその区間に目的の色との差を一気に足す
    • そうでないならさらに区間を下る
    • 現在の区間の色をxにする
  • そうでないなら区間の色をー1(1色ではない)にして区間を下る
  • 最後にその区間で足された鮮やかさの合計をsumに追加する

更新したい区間に完全に含まれているとき\&\&区間の色が1色のときの更新が下の区間に伝播しないのでそこは遅延評価っぽくしている.

コード


(444C.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct segtree
{
        int N;
        vector<int> col, sum, add;
        segtree(int n)
        {
                N = 1;
                while(N < n) N <<= 1;
                col.assign(2*N-1,-1);
                sum.assign(2*N-1,0);
                add.assign(2*N-1,0);
                for (int i = 0; i < N; i++) col[N-1+i] = i+1;
        }

        void update(int a, int b, int x) { update(a,b,0,N,0,x,-1);}
        int update(int a, int b, int l, int r, int k, int x, int c)
        {
                if(c >= 0) col[k] = c;
                c = col[k];
                if(b <= l or r <= a or col[k] == x) return 0;
                int m = (l+r)/2, s = 0;
                if(a <= l and r <= b) {
                        if(col[k] >= 0) {
                                add[k] += s = abs(col[k]-x);
                                s *= r-l;
                        }
                        else s = update(a,b,l,m,2*k+1,x,c)+update(a,b,m,r,2*k+2,x,c);
                        col[k] = x;
                }
                else {
                        s = update(a,b,l,m,2*k+1,x,c)+update(a,b,m,r,2*k+2,x,c);
                        col[k] = -1;
                }
                sum[k] += s;
                return s;
        }

        int query(int a, int b) { return query(a,b,0,N,0);}
        int query(int a, int b, int l, int r, int k)
        {
                if(b <= l or r <= a) return 0;
                if(a <= l and r <= b) return sum[k];
                int m = (l+r)/2, s = min(r,b)-max(l,a);
                return query(a,b,l,m,2*k+1)+query(a,b,m,r,2*k+2)+add[k]*s;
        }
};

int n, m, t, l, r, x;

void solve()
{
        segtree st(n);
        while(m--) {
                cin >> t >> l >> r; --l;
                if(t == 1) {
                        cin >> x;
                        st.update(l,r,x);
                }
                else cout << st.query(l,r) << endl;
        }
}

void input()
{
        cin >> n >> m;
}

signed main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments