Yao Lirong's Blog

Tsinghua DSA 作业总结 (2)

Tsinghua
2021/02/10

CST数据结构（2020秋）PA2a

2-1 Build

心得

List -> 编号存树

  • 我用的是自己写的 List 存树，对于一个节点，它有一个指针指向包含它所有孩子的 List，并有 height size 存储该点的高度及子树规模，当发生节点移动时，递归地向上更新。但是这样的话每次更新时，必须遍历当前节点的所有孩子，才能确认是否需要更新该点的高度或子树规模，这样不符合题目中 “复杂度与 cost 成线性” 的要求。所以会TLE，解决方法是在每一个点都存一个它向后看能看到的最大子树高度以及它后面所有点的子树规模和，这样每次删除某一点时，只需要更新它前面兄弟的这两个值就好了，符合我们对 cost 的定义。
  • List 存还会发生 MLE 的问题。既然题目中已经给出每个店的序号，其实我们不需要用 List 存，只需要用多个数组存储相对应的信息（前后节点，父子节点，本书规模及高度，其向后看所有兄弟的最大高度和字数规模和）即可，这样也解决了我们一开始读入时需要自建邻接表的问题

2-4-2 Kidd

算法

线段树，离散化。

线段树的每个节点所代表的区间必须一闭一开（我的实现中是左闭右开的），如果是闭区间会使同一个点被储存在相邻的区间中两次。

线段树中每个节点要存两个东西：1. 本节点对应的区间被翻转的次数 2. 本节点所包含的上所有子区间（包括它自己）被翻转的次数。其中 2 通过 本节点被翻转的次数 * 本节点代表的区间的大小 + 两个孩子区间的所有子区间被翻转的次数 得来。

所以在每次查询时，如果只是单纯的相交，相交部分也在这个区间被当做一个整体翻转时所翻转了，所以我们计算出相交范围的大小，乘上此区间被翻转的次数；如果查询区间包含在当前区间里面（恰好是当前区间），我们只需要加上当前区间及其所有子区间被反转的次数就好了

代码

离散化部分有严重错误，既然第一步就有错所以剩下的对不对咱其实也不知道。但是思路大概就这么个思路（

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<cstdio>
#include<iostream>
using namespace std;

int sort_cmp (const void * a, const void * b) { return ( *(int*)a - *(int*)b );}

const int N = 200003;
// isQuery[i] is true if the ith operation is a query 'Q', is false if the ith operation is a flip 'H'
bool isQuery[N]; int interval[N][2];
// a stores the unique discretized interval
int a[N*2], unique_num = 0;
struct treeNode{
    bool isNode = false; // true if this is a leaf in segment tree
    int l, r; // this node represents the interval [l,r)
    int v; // this node stores value v; this interval *only* has been flipped v times
    long long total; // the points in this interval and all its subintervals have been flipped total times
}st[(N*2)<<1];


void build(int li, int ri, int x);
void update(int li, int ri, int x);
long long query(int li, int ri, int x);
int bisearch(int li, int ri, int g);
int original_to_discrete(int x);
int discrete_to_original(int y);

int temp[N*4];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    cin.ignore(100,'\n');
    char o; int l, r;
    for(int i=0; i<m; i++){
        scanf("%c%d%d", &o, &l, &r);

        isQuery[i] = (o=='Q');
        interval[i][0] = l;
        interval[i][1] = r;
        temp[i*4 + 0] = l;
        temp[i*4 + 1] = l+1;
        temp[i*4 + 2] = r;
        temp[i*4 + 3] = r+1;

        cin.ignore(100,'\n');
    }

    qsort(temp, 4*m, sizeof(int), sort_cmp);
    a[unique_num++] = temp[0];
    for(int i=1; i<4*m; i++) {
        if(temp[i]!=temp[i-1])
            a[unique_num++] = temp[i];
    }

    build(0, unique_num, 0);

    for(int i=0; i<m; i++){
        if(isQuery[i]){
            cout<<query(original_to_discrete(interval[i][0]),
                        original_to_discrete(interval[i][1]),
                        0)<<endl;
        }
        else {
            update(original_to_discrete(interval[i][0]),
                   original_to_discrete(interval[i][1]),
                   0);
        }
    }

    return 0;
}

// node x in s-tree represents the interval [li,ri)
void build(int li, int ri, int x){
    st[x].isNode = true;
    st[x].l = li; st[x].r = ri; st[x].v = 0;
    //cout<<"building node "<<x<<"represents ["<<st[x].l<<", "<<st[x].r<<")"<<endl;

    if(li+1 != ri) {
        int mid = (li+ri)/2;
        build(li,mid,(x<<1) + 1);
        build(mid,ri,(x<<1) + 2);
    }

    return;
}


// currently at s-tree node x, updating interval [li,ri]
void update(int li, int ri, int x){

   int dis = discrete_to_original(st[x].r-1)
           - discrete_to_original(st[x].l) + 1;

    if(li<=st[x].l && ri>=st[x].r-1){ // interval(x) \subseteq [li,ri]

        st[x].v += 1;
        st[x].total += dis;
        return; // we should immediately stop updating any children of this node, because that will do a duplicate update
    }

    if(!st[(x<<1)+1].isNode) return; // if this is a leaf node, return

    if(st[(x<<1)+1].isNode && li <= st[(x<<1)+1].r-1){ // intersects left child
        update(li, ri, (x<<1)+1);
    }

    if(st[(x<<1)+2].isNode && ri >= st[(x<<1)+2].l){ // intersects right child
        update(li, ri, (x<<1)+2);
    }

    // 'st[x].v * dis' is the number of flips caused by "this" interval being flipped
    // st[(x<<1)+1].total is the total number of flips this node's left child has
    // st[(x<<1)+2].total is the total number of flips this node's right child has
    st[x].total = st[x].v * dis + st[(x<<1)+1].total + st[(x<<1)+2].total;
    return;

}

long long query(int li, int ri, int x){


    long long res = 0;

    if(li<=st[x].l && ri>=st[x].r-1){ // interval(x) \subseteq [li,ri]
        res += st[x].total;
        return res;
    }

    int dis = discrete_to_original(min(st[x].r-1, ri))
            - discrete_to_original(max(st[x].l, li)) + 1;
    res += st[x].v * dis;

    if(st[(x<<1)+1].isNode && li <= st[(x<<1)+1].r-1){
        res += query(li, ri, (x<<1)+1);
    }

    if(st[(x<<1)+2].isNode && ri >= st[(x<<1)+2].l){
        res += query(li, ri, (x<<1)+2);
    }


    return res;

}

int bisearch(int li, int ri, int g){
    int mid = 0;
    while(ri > li+1){
        mid = (li+ri)>>1;
        if(a[mid]<=g) li = mid;
        else ri = mid;
    }
    return li;
}

int discrete_to_original(int y){
    return a[y];
}

int original_to_discrete(int x){
    return bisearch(0, unique_num, x);
}

2.7 Virus

心得

堆的 sink 的边界条件应该是 

1
2
3
4
int l=i*2, r=i*2+1;
while((l<=n && a[i]>=a[l]) || (r<=n && a[i]>=a[r])){
    ...
}

而不是

1
2
3
4
5
6
7
8
int height(int x){
    if(x==0) return 1;
    int digit=0; while(x>0) {x=x>>1; digit++;} return digit;
}

while((a[i]>=a[l]||a[i]>=a[r])&&i<pow(2,height(n))){
    ...
}

堆是一个完全二叉树 (Complete Binary Tree) 而不是一个完美二叉树 (Perfect Binary Tree)

代码

仅展示了堆的实现部分

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
const int M=1000007;
const int INF=10e7;

const int N = 1007;
struct point {
    int id; // id = x*N + y
    int t;

    point(int x, int y, int ti) {
        id = x*N + y;
        t = ti;
    }
    point() {
        id = 0; t = 0;
    }
    point(int n) : point() {}
    point(const point &from) {
        this->id = from.id;
        this->t = from.t;
    }
};

point myPQ[M];

inline bool operator<(const point &p1, const point &p2) {
  return p1.t < p2.t;
}

inline bool operator>(const point &p1, const point &p2) {
  return p1.t > p2.t;
}

inline bool operator<=(const point &p1, const point &p2) {
  return p1.t <= p2.t;
}

inline bool operator>=(const point &p1, const point &p2) {
  return p1.t >= p2.t;
}


class PriorityQueue {

    int n = 0;
    point *a = myPQ;

public:
    void add(point x)
    {
        a[++n] = x;
        swim(n);
    }
    point extract()
    {
        point result = a[1];
        swap(a[1],a[n]);
        a[n--]=INF;
        sink(1);
        return result;
    }

    bool isEmpty() {return n == 0;}

private:
    void swim(int i)
    {
        while(i>1 && a[i/2]>=a[i]){
            swap(a[i/2],a[i]);
            i = i/2;
        }
    }

    void sink(int i)
    {
        int l=i*2, r=i*2+1;
        while((l<=n && a[i]>=a[l]) || (r<=n && a[i]>=a[r])){
            if(a[l]<=a[r]&&l<=n){
                swap(a[i],a[l]);
                i = l; l=i*2; r=i*2+1; continue;
            }
            else if (a[l]>a[r]&&r<=n){
                swap(a[i],a[r]);
                i = r; l=i*2; r=i*2+1; continue;
            }
            else return;
        }
    }
};

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/2021-02-10-Tsinghua-DSA-%E4%BD%9C%E4%B8%9A%E6%80%BB%E7%BB%93-(2)/

Publish date：February 10th 2021, 12:00:00 am

Update date：June 9th 2022, 3:33:28 am

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

CATALOG
  1. 1. 2-1 Build
    1. 1.1. 心得
  2. 2. 2-4-2 Kidd
    1. 2.1. 算法
    2. 2.2. 代码
  3. 3. 2.7 Virus
    1. 3.1. 心得
    2. 3.2. 代码
Total : 66
2023
2022
2021
2020
2019
NOI CS2112 Logistics Cornell Review CS3110 Manual Journal Tsinghua Book