力扣-线段树_线段树力扣python3

作者：数据科学创新者 | 2024-02-05 16:46:43

踩

线段树力扣python3

力扣-线段树

307. 区域和检索 - 数组可修改

我的题解：

思路: 直接套用线段树模版，第一个用的是数组模拟树，第二个用节点来实现

public class NumArray {
    //数组的长度
    private int n;
    //输入的数组
    private int[] arr;
    //存储元素值
    private int[] tree;
    //存储懒惰标记
    private int[] add;
    //*
    NumArray(int[] nums){
        n = nums.length;
        arr = nums;
        tree = new int[n * 4];
        add = new int[n * 4];
        //初始id为1
        buildTree(0, n - 1, 1);
    }
    //更新单点的值*
    public void update(int idx, int val){
        update(0, n - 1, 1, idx, val);
    }
    //求区间的范围*
    public int sumRange(int left, int right){
        return query(0, n - 1, left, right, 1);
    }
    //构建树*
    private void buildTree(int start, int end, int rootId){
        //若当前元素是唯一的那么就更新当前树节点的值,并返回
        if(start == end) {
            tree[rootId] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        //划分为左边和右边
        buildTree(start, mid, rootId * 2);
        buildTree(mid + 1, end, rootId * 2 + 1);
        //向上推送
        pushUp(rootId);
    }
    //计算根节点的值
    private void pushUp(int rootId){
        tree[rootId] = tree[rootId * 2] + tree[rootId * 2 + 1];
    }
    //更新各个分支的值
    private void pushDown(int rootId, int leftNum, int rightNum){
        //若当前元素懒惰标记已清除就直接返回
        if(add[rootId] == 0) return;
        //更新懒惰标记的值
        add[rootId * 2] += add[rootId];
        add[rootId * 2 + 1] += add[rootId];
        //更新节点的值
        tree[rootId * 2] += leftNum * add[rootId];
        tree[rootId * 2 + 1] += rightNum * add[rootId];
        //懒惰标记清除
        add[rootId] = 0;
    }

    //更新操作-单元素
    //start-end代表树的区间范围，rootId根节点updateIdx更新的节点，更新的值val*
    private void update(int start, int end, int rootId, int updateIdx, int val){
        //目标条件
        if(start == end){
            arr[start] = tree[rootId] = val;
            return;
        }
        //划分
        int mid = (start + end) / 2;
        //左边
        if(updateIdx <= mid){
            update(start, mid, rootId * 2, updateIdx, val);
        }else{
            update(mid + 1, end, rootId * 2 + 1, updateIdx, val);
        }
        pushUp(rootId);
    }
    //更新操作-区间，这里是内部更新，加入外边界l和r
    private void update(int start, int end, int rootId, int l, int r, int val){
        //若未覆盖内边界
        if(r < start || l > end){
            return;
        }
        //若覆盖内边界
        if(l <= start && end <= r){
            tree[rootId] += (end - start + 1) * val;
            add[rootId] += val;
            return;
        }

        //其它情况缩小范围确保覆盖
        int mid = (start + end) / 2;
        //先推送
        pushDown(rootId, mid - start + 1, end - mid);
        //再更新
        update(start, mid, rootId * 2, l, r, val);
        update(mid + 1, end, rootId * 2 + 1, l, r, val);
        //回推
        pushUp(rootId);
    }

    //查询
    private int query(int start, int end, int l, int r, int rootId){
        //若在范围外直接返回0
        if(r < start || l > end) return 0;
        //若范围覆盖
        if(l <= start && end <= r){
            return tree[rootId];
        }
        //划分
        int mid = (start + end) / 2;
        //先推送
        pushDown(rootId, mid - start + 1, end - mid);
        //再查询
        int leftSum = query(start, mid, l, r, rootId * 2);
        int rightSum = query(mid + 1, end, l, r, rootId * 2 + 1);
        return leftSum + rightSum;
    }
}

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

public class NumArray {
    private int N;
    private Node root = new Node();
    public NumArray(int[] nums) {
        N = nums.length - 1;
        for (int i = 0; i <= N; i++) {
            update(root, 0, N, i, i, nums[i]);
        }
    }
    //*
    public void update(int index, int val) {
        update(root,0, N, index, index, val);
    }
    //*
    public int sumRange(int left, int right) {
        return query(root, 0, N, left, right);
    }

    class Node{
        Node left, right;
        int val, add;
    }
    //*
    void pushUp(Node node){
        node.val = node.left.val + node.right.val;
    }
    //*
    void pushDown(Node node, int leftNum, int rightNum){
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ;
        node.left.val = node.add * leftNum;
        node.right.val = node.add * rightNum;
        node.left.add = node.add;
        node.right.add = node.add;
        node.add = 0;
    }
    //*
    void update(Node node, int start, int end, int l, int r, int val){
        if (l <= start && end <= r) {
            node.val = (end - start + 1) * val;
            node.add = val;
            return ;
        }
        int mid = (start + end) >> 1;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }
    //***
    int query(Node node, int start, int end, int l, int r){
        if(l <= start && end <= r){
            return node.val;
        }

        int mid = (start + end) >> 1, ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if(l <= mid){
            ans += query(node.left, start, mid, l, r);
        }
        if(mid < r){
            ans += query(node.right, mid + 1, end, l, r);
        }
        return ans;
    }
}
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

729. 我的日程安排表 I

我的题解：

思路: 区间查询的问题我们可以用线段树来实现，这里我们先看线段树当前区间是否已被填充，即返回值是否不为0，若是，则返回false，否则我们对当前区间进行填充，默认填充1，然后返回true

public class MyCalendar {
    public MyCalendar(){

    }

    public boolean book(int start, int end) {
        //先查询该区间是否等于0，若是则可以存，否则返回false
        if(query(root, 0, N, start, end - 1) == 0){
            update(root, 0, N, start, end - 1, 1);
            return true;
        }
        return false;
    }

    class Node{
        //左右孩子
        Node left, right;
        //当前值，和懒惰更新的值
        int val, add;
    }

    private Node root = new Node();
    int N = (int) 1e9;
    public void update(Node node, int start, int end, int l, int r, int val){
        //若覆盖了当前区域直接更新
        if(l <= start && end <= r) {
            node.val += val;
            node.add += val;
            return;
        }
        //其他情况先下推在划分
        pushDown(node);
        int mid = (start + end) / 2;
        if(l <= mid) update(node.left, start, mid, l, r, val);
        if(r > mid) update(node.right, mid + 1, end, l, r, val);
        //上推-更新根节点
        pushUp(node);
    }

    public int query(Node node, int start, int end, int l, int r){
        //若覆盖了整个区域直接返回
        if(l <= start && end <= r) return node.val;
        //先下推再划分
        pushDown(node);
        int mid = (start + end) / 2;
        int max = 0;
        if(l <= mid) max = query(node.left, start, mid, l, r);
        if(r > mid) max = Math.max(max, query(node.right, mid + 1, end, l, r));
        return max;
    }
    //对于根节点
    void pushUp(Node node){
        node.val = Math.max(node.left.val, node.right.val);
    }

    //下推函数-对于子节点，新建节点，和将懒惰标记实现
    void pushDown(Node node){
        if(node.left == null) node.left = new Node();
        if(node.right == null) node.right = new Node();
        if(node.add == 0) return;
        node.left.val += node.add;
        node.right.val += node.add;
        node.left.add += node.add;
        node.right.add += node.add;
        node.add = 0;
    }

}
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

我的日程安排表 II

我的题解：

思路: 本题同样可以用线段树来完成，要注意这里当查询到区间里的最大值已经为2时，说明本次就不能插入，返回false，否则正常插入1到区间中，并返回true

class MyCalendarTwo {

    public boolean book(int start, int end) {
        if(query(root, 0, N, start, end - 1) == 2) return false;
        update(root, 0, N, start, end - 1, 1);
        return true;
    }
    Node root = new Node();
    int N = (int) 1e9;
    class Node{
        Node left, right;
        int val, add;
    }
    //根节点
    void pushUp(Node node){
        node.val = Math.max(node.left.val, node.right.val);
    }
    //创建子节点和实现懒惰标记
    void pushDown(Node node){
        if(node.left == null) node.left = new Node();
        if(node.right == null) node.right = new Node();
        if(node.add == 0) return;
        node.left.val += node.add;
        node.right.val += node.add;
        node.left.add += node.add;
        node.right.add += node.add;
        node.add = 0;
    }

    void update(Node node, int start, int end, int l, int r, int val){
        //若包括整个范围，就直接修改根节点
        if(l <= start && end <= r){
            node.val += val;
            node.add += val;
            return;
        }

        //先下推，构造节点，将懒惰标记实现
        pushDown(node);
        int mid = (start + end) / 2;
        if(l <= mid) update(node.left, start, mid, l, r, val);
        if(mid < r) update(node.right, mid + 1, end, l, r, val);
        //向上更新根节点的值
        pushUp(node);
    }
    //这里要返回最大值，若最大值为2说明已经插入两次了
    int query(Node node, int start, int end, int l, int r){
        if(l <= start && end <= r) return node.val; ;
        pushDown(node);
        int max = 0, mid = (start + end) / 2;
        if(l <= mid) max = query(node.left, start, mid, l, r);
        if(mid < r) max = Math.max(query(node.right, mid + 1, end, l, r), max);
        return max;
    }
}

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

732. 我的日程安排表 III

我的题解：

思路: 这里只需要用线段树将当前区间加入线段树中，然后返回根节点的值，即是最大次数

public class MyCalendarThree {
    public MyCalendarThree() {

    }

    public int book(int startTime, int endTime) {
        //这里整个线段树的范围是0~N，插入区间的范围是startTime ~ endTime - 1，因为这里最后endTime是开区间
        update(root, 0, N, startTime, endTime - 1, 1);
        //这里返回根节点的值
        return root.val;
    }
    Node root = new Node();
    int N = (int) 1e9;
    class Node{
        Node left, right;
        int val, add;
    }

    void pushUp(Node node){
        node.val = Math.max(node.left.val, node.right.val);
    }

    void pushDown(Node node){
        if(node.left == null) node.left = new Node();
        if(node.right == null) node.right = new Node();
        if(node.add == 0) return;
        node.left.val += node.add;
        node.left.add += node.add;
        node.right.val += node.add;
        node.right.add += node.add;
        node.add = 0;
    }

    void update(Node node, int start, int end, int l, int r, int val){
        if(l <= start && end <= r){
            node.val += val;
            node.add += val;
            return;
        }

        pushDown(node);
        int mid = start + (end - start) / 2;
        if(l <= mid){
            update(node.left, start, mid, l, r, val);
        }
        if(r > mid){
            update(node.right, mid + 1, end, l, r, val);
        }
        pushUp(node);
    }

    int query(Node node, int start, int end, int l, int r){
        if(l <= start && end <= r){
            return node.val;
        }
        pushDown(node);
        int mid = start + (end - start) / 2;
        int ans = 0;
        if(l <= mid){
            ans = query(node.left, start, mid, l, r);
        }
        if(r > mid){
            ans = Math.max(query(node.left, mid + 1, end, l, r), ans);
        }
        return ans;
    }
}
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

715. Range 模块

我的题解：

思路: 本题同样可以用线段树来处理，这里比较特殊的地方在于query的时候要返回整个区间的最小值，因此在向上推的时候要返回最小值或者是布尔值，在下推的时候要根据懒惰标记对，左右孩子节点的cover和懒惰标记进行更新，这里很关键

1.0-数值版

public class RangeModule {
    Node root = new Node();
    int N = (int) 1e9;
    public RangeModule() {

    }
    public void addRange(int left, int right) {
        update(root, 0, N, left, right - 1, 1);
    }

    public boolean queryRange(int left, int right) {
        return query(root, 0, N, left, right - 1) > 0;
    }

    public void removeRange(int left, int right) {
        update(root, 0, N, left, right - 1, -1);
    }

    class Node{
        Node left, right;
        int val, add;
    }

    void pushUp(Node node){
        node.val = Math.min(node.left.val, node.right.val);
    }

    void pushDown(Node node){
        if(node.left == null) node.left = new Node();
        if(node.right == null) node.right = new Node();
        if(node.add == 0) return;
        node.left.val = node.add;
        node.left.add = node.add;
        node.right.val = node.add;
        node.right.add = node.add;
        node.add = 0;
    }

    void update(Node node, int start, int end, int l, int r, int val){
        if(l <= start && end <= r) {
            node.val = val;
            node.add = val;
            return;
        }

        pushDown(node);
        int mid = start + (end - start) / 2;
        if(l <= mid) update(node.left, start, mid, l, r, val);
        if(mid < r) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }

    int query(Node node, int start, int end, int l, int r){
        if(l <= start && end <= r){
            return node.val;
        }
        pushDown(node);
        int mid = start + (end - start) / 2;
        int ans = 1000;
        if(l <= mid) ans = query(node.left, start, mid, l, r);
        if(mid < r) ans = Math.min(query(node.right, mid + 1, end, l, r), ans);
        return ans;
    }
}
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

2.0-布尔版，这里用布尔值优化会有明显的效果

public class RangeModule {
    public RangeModule() {

    }

    public void addRange(int left, int right) {
        update(root, 0, N, left, right - 1, 1);
    }

    public boolean queryRange(int left, int right) {
        return query(root, 0, N, left, right - 1);
    }

    public void removeRange(int left, int right) {
        update(root, 0, N, left, right - 1, -1);
    }
    int N = (int) 1e9;
    Node root = new Node();
    class Node{
        Node left, right;
        boolean cover;
        int lazy;
    }

    void pushUp(Node node){
        node.cover = node.left.cover && node.right.cover;
    }

    void pushDown(Node node){
        if(node.left == null) node.left = new Node();
        if(node.right == null) node.right = new Node();
        if(node.lazy == 0) return;

        node.left.cover = node.lazy == 1;
        node.left.lazy = node.lazy;
        node.right.cover = node.lazy == 1;
        node.right.lazy = node.lazy;
        node.lazy = 0;
     }

     void update(Node node, int start, int end, int l, int r, int val){
        if(l <= start && end <= r){
            node.cover = val == 1;
            node.lazy = val;
            return;
        }
        pushDown(node);
        int mid = start + (end - start) / 2;
        if(l <= mid) update(node.left, start, mid, l, r, val);
        if(r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
     }

     boolean query(Node node, int start, int end, int l, int r){
        if(l <= start && end <= r){
            return node.cover;
        }
        pushDown(node);
        int mid = start + (end - start) / 2;
        boolean flag = true;
        if(l <= mid) flag = query(node.left, start, mid, l, r);
        if(r > mid) flag = flag && query(node.right, mid + 1, end, l, r);
        return flag;
     }
}
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

933. 最近的请求次数

我的题解：

思路: 区间问题可以考虑用线段树来实现，要注意这里因为是求次数，所以要求对应区间的和，这个很重要

public class RecentCounter {
    public RecentCounter() {

    }

    public int ping(int t) {
        update(root, 1, N, t, t, 1);
       return query(root, 1, N, Math.max(1, t - 3000), t);
    }
    class Node{
        Node left, right;
        int val, lazy;
    }
    int N = (int) 1e9;
    Node root = new Node();
	//这里求和要相加
    void pushUp(Node node){
        node.val = node.left.val + node.right.val;
    }

    void pushDown(Node node, int leftSum, int rightSum){
        if(node.left == null) node.left = new Node();
        if(node.right == null) node.right = new Node();
        if(node.lazy == 0) return;
        //这里向下推的时候左右孩子的值，应该等于当前懒惰标记的值 * 各自区间的大小
        node.left.val += leftSum * node.lazy;
        node.right.val += rightSum * node.lazy;
        node.left.lazy += node.lazy;
        node.right.lazy += node.lazy;
        node.lazy = 0;
    }

    void update(Node node, int start, int end, int l, int r, int val){
        if(l <= start && end <= r){
            node.val += val;
            node.lazy += val;
            return;
        }
        int mid = start + (end - start) / 2;
        pushDown(node, mid - start + 1, end - mid);
        if(l <= mid){
            update(node.left, start, mid, l, r, val);
        }
        if(mid < r) {
            update(node.right, mid + 1, end, l, r, val);
        }
        pushUp(node);
    }

    int query(Node node, int start, int end, int l, int r){
        if(l <= start && end <= r){
            return node.val;
        }
        int mid = start + (end - start) / 2;
        pushDown(node, mid - start + 1, end - mid);
        //这里求和要相加
        int ans = 0;
        if(l <= mid){
            ans = query(node.left, start, mid, l, r);
        }
        if(mid < r){
            ans += query(node.right, mid + 1, end, l, r);
        }
        return ans;
    }
}
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

699. 掉落的方块

我的题解：

思路: 这里区间覆盖问题我们可以用线段树来解决，区间的值对应方块的高度，这里在插入前先要获取该区间的最大值，然后在插入的时候在之前最大值的基础上加上当前的高度进行覆盖。这里有边界-1，避免产生重叠

import java.util.ArrayList;
import java.util.List;
public class Test1 {
    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> ans = new ArrayList<>();
        for(int[] arr : positions){
            int l = arr[0], h = arr[1], r = h + l;
            //未插入前的高度
            int tmp = query(root, 0, N, l, r - 1);
            //这里直接用之前的高度+当前的高度进行覆盖
            update(root, 0, N, l, r - 1, h + tmp);
            ans.add(root.val);
        }
        return ans;
    }
    Node root = new Node();
    int N = (int) 1e9;
    class Node{
        Node left, right;
        int val, lazy;
    }
    //*
    void pushUp(Node node){
        node.val = Math.max(node.left.val, node.right.val);
    }
    //*
    void pushDown(Node node){
        if(node.left == null) node.left = new Node();
        if(node.right == null) node.right = new Node();
        if(node.lazy == 0) return;

        node.left.val = node.lazy;
        node.right.val = node.lazy;
        node.left.lazy = node.lazy;
        node.right.lazy = node.lazy;
        node.lazy = 0;
    }
    //*
    void update(Node node, int start, int end, int l, int r, int val){
        if(l <= start && end <= r) {
            node.val = val;
            node.lazy = val;
            return;
        }
        pushDown(node);
        int mid = (start + end) / 2;
        if(l <= mid){
            update(node.left, start, mid, l, r, val);
        }
        if(mid < r) {
            update(node.right, mid + 1, end, l, r, val);
        }
        pushUp(node);
    }
    //*
    int query(Node node, int start, int end, int l, int r){
        if(l <= start && end <= r) {
           return node.val;
        }
        pushDown(node);
        int mid = (start + end) / 2;
        int max = 0;
        if(l <= mid){
            max = query(node.left, start, mid, l, r);
        }
        if(mid < r) {
            max = Math.max(query(node.right, mid + 1, end, l, r), max);
        }
        return max;
    }
    public static void main(String[] args) {
        int[][] arr = {{1, 2}, {2, 3}, {6, 1}};
        int[][] arr1 = {{100, 100}, {200, 100}};
        System.out.println(new Test1().fallingSquares(arr));
    }
}
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

6206. 最长递增子序列 II

我的题解：

思路: 并查集

public int lengthOfLIS(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            //查询
            int count = query(root, 0, N, Math.max(0, nums[i] - k), nums[i] - 1) + 1;
            update(root, 0, N, nums[i], nums[i], count);
            ans = Math.max(ans, count);
        }
        return ans;
    }

    class Node{
        Node left, right;
        int val, lazy;
    }
    Node root = new Node();
    int N = (int) 1e5;

    void pushUp(Node node){
        node.val = Math.max(node.left.val, node.right.val);
    }

    void pushDown(Node node){
        if(node.left == null) node.left = new Node();
        if(node.right == null) node.right = new Node();
        if(node.lazy == 0) return;

        node.left.val = node.lazy;
        node.right.val = node.lazy;
        node.left.lazy = node.lazy;
        node.right.lazy = node.lazy;
        node.lazy = 0;
    }

    void update(Node node, int start, int end, int l, int r, int val){
        if(l <= start && end <= r){
            node.val = val;
            node.lazy = val;
            return;
        }
        pushDown(node);
        int mid = (start + end) / 2;
        if(l <= mid) update(node.left, start, mid, l, r, val);
        if(r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }

    int query(Node node, int start, int end, int l, int r){
        if(l <= start && end <= r) return node.val;
        pushDown(node);
        int mid = (start + end) / 2;
        int max = 0;
        if(l <= mid) max = query(node.left, start, mid, l, r);
        if(mid < r) max = Math.max(query(node.right, mid + 1, end, l, r), max);
        return max;
    }
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/数据科学创新者/article/detail/61209