Algoogle

Algorithm for Programming Contest

Codeforces 461C Appleman and a Sheet of Paper

Category: Codeforces Tag: segment-tree

Appleman and a Sheet of Paper

問題概要


長さnの紙を折っていきたい. 以下のクエリを捌け

  • 紙の左端からpのところで左から右に折る

  • 紙の左端から[l,r]の部分の紙の重なっている長さの総和を求める

解法


まず左から右に折るというのを, pが現在の長さの半分より大きいなら右から左におることにする.
またその次からは右から左にpを見るようにして, 大きいpが来るたびにこの反転を繰り返す.
これによって区間[0,n)で処理できるようになる.
以下の機能を持つSegment Treeを実装することでクエリを捌ける.

  • 区間の紙の重なっている量を持つ
  • 区間の紙の厚さが一様かどうかを持つ
  • 区間に一度に足された量を持つ
  • 区間に値xを足す
  • 区間[a,b)を区間[c,d)にひっくり返して足す
  • 区間の重なっている長さの総和を求める

ひっくり返して足すときは, 区間が完全に含まれていてさらに厚さが一様ならその区間に対応する目的の区間にその厚さを足して, そうでないなら区間を分割していくのでよい.
また更新するときに区間の一部だけ足されることがあったらその区間の厚さは一様ではなくなる.

実は更新はナイーブに行ってもよい.
長さnが減っていくことを考えると更新回数は高々n回になる.
このことを利用すると, 各地点での和をBITで持つことによって更新全体でO(n log n), 総和の計算にはそれぞれO(log n)で答えることができる.
また実装も平易なものになる.

コード


(461C.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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

struct segtree
{
        int N;
        vector<int> val, sum, add, flt;
        segtree(int n) {
                N = 1;
                while(N < n) N *= 2;
                sum.assign(2*N, 0);
                add.assign(2*N, 0);
                flt.assign(2*N, 0);
                init(0,n,0,N,0);
        }
        void init(int a, int b, int l, int r, int k){
                if(b <= l or r <= a) return;
                if(a <= l and r <= b) flt[k] = 1;
                sum[k] = min(r,b)-max(l,a);
                if(r-l==1) return;
                init(a,b,l,(l+r)/2,2*k+1);
                init(a,b,(l+r)/2,r,2*k+2);
        }

        int addi(int a, int b, int l, int r, int k, int x) {
                if(b <= l or r <= a) return 0;
                int s = 0;
                if(a <= l and r <= b) {
                        add[k] += x;
                        s = x*(r-l);
                }
                else {
                        flt[k] = 0;
                        int m = (l+r)/2;
                        s = addi(a,b,l,m,2*k+1,x)+addi(a,b,m,r,2*k+2,x);
                }
                sum[k] += s;
                return s;
        }

        void update(int a, int b, int c) { update(a,b,c,0,N,0);}
        void update(int a, int b, int c, int l, int r, int k) {
                if(b <= l or r <= a) return;
                if(a <= l and r <= b and flt[k]) {
                        addi(a+c-r,a+c-l,0,N,0,query(l,r)/(r-l));
                        return;
                }
                int m = (l+r)/2;
                update(a,b,c,l,m,2*k+1);
                update(a,b,c,m,r,2*k+2);
        }

        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, w = 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]*w;
        }
};

int n, q, bl, br, t, p, l, r, dir;

void solve()
{
        segtree st(n);
        bl = 0; br = n;
        dir = 0;
        while(q--){
                scanf("%d", &t);
                if(t == 1){
                        scanf("%d", &p);
                        if((br-bl)/2<p) {
                                p = (br-bl)-p;
                                dir ^= 1;
                        }
                        if(!dir) {
                                st.update(bl,bl+p,bl+2*p);
                                bl += p;
                        }
                        else {
                                st.update(br-p,br,br-p);
                                br -= p;
                        }
                }
                else {
                        scanf("%d%d", &l, &r);
                        if(!dir) printf("%d\n", st.query(l+bl,r+bl));
                        else printf("%d\n", st.query(br-r,br-l));
                }
        }
}

void input()
{
        scanf("%d%d", &n, &q);
}

int main()
{
        input();
        solve();
        return 0;
}

Comments