0%

Leetcode715 Range模块

Posted on

题面描述 Range模块

对于给定的 $1 \leq x,y \leq 10^9$ 现给定三种操作：

  • op1: 将 $[x,y]$ 置 $0$ ，最多 $1000$ 次
  • op2: 将 $[x,y]$ 置 $1$ ，最多 $1000$ 次
  • op3: 询问 $[x,y]$ 是否全为 $1$ ，最多 $5000$ 次

这显然是一道离散化后线段树求区间和的问题。但可惜的是题目强制在线，这也意味着离散化不可行。

可以用珂朵莉树维护，即使用set维护每个不重叠的 $1$ 区间。
实现起来有很多迭代器操作，细节较多。

首先回顾一下使用到的std::set的一些方法(参考)：

1
set::lower_bound 是对数时间复杂度的
2
lower_bound(set::iterator,set::iterator) 是线性时间复杂度的
3
set::erase(set::iterator,set::iterator) 可以在线性时间内删除指定区间

探讨一下时间复杂度：

  • op1: $O\left( \left( 2op_1+op_2 \right) \log \left( 2op_1+op_2 \right) \right)$
  • op2: $O\left( \log \left( 2op_1+op_2 \right) \right)$
  • op3: $O\left( \log \left( 2op_1+op_2 \right) \right)$

因此，总时间复杂性最高为 $1000\cdot3000\cdot \log 3000=4\cdot 10^7$
但考虑到每当删除操作删除了很多元素后，虽然占用时间但也会使set变小，因此上述时间复杂度应该较为宽松。
运行时间不到半秒，时间复杂度玄学。

1
struct node{
2
    mutable int L,R;
3
    node(int l,int r):L(l),R(r){}
4
    bool operator < (const node &qmh) const{
5
        return L<qmh.L;
6
    }
7
};
8
9
class RangeModule {
10
    set<node> kdl;
11
    set<node>::iterator itx,ity;
12
    int tmp;
13
public:
14
    RangeModule() {}
15
16
    void addRange(int x, int y) {
17
        itx=kdl.upper_bound({x,0});
18
        ity=kdl.upper_bound({y,0});
19
        if (itx==kdl.begin()&&ity==kdl.begin()) {
20
            kdl.emplace(x,y);
21
            return;
22
        }
23
        if (itx==kdl.begin()) itx->L=x;
24
        else --itx;
25
        --ity;
26
        if (itx->R>=x) x=itx->L;
27
        else ++itx;
28
        if (ity->R>=y) y=ity->R;
29
        ++ity;
30
        kdl.erase(itx,ity);
31
        kdl.emplace(x,y);
32
    }
33
34
    bool queryRange(int x, int y) {
35
        itx=kdl.upper_bound({x,0});
36
        ity=kdl.upper_bound({y,0});
37
        if (itx==kdl.begin()||ity==kdl.begin()) return false;
38
        --itx;--ity;
39
        if (itx!=ity) return false;
40
        if (y>ity->R) return false;
41
        return true;
42
    }
43
44
    void removeRange(int x, int y) {
45
        itx=kdl.upper_bound({x,0});
46
        ity=kdl.upper_bound({y,0});
47
        if (itx==kdl.begin()&&ity==kdl.begin()) return;
48
        if (itx==kdl.begin()) x=itx->L;
49
        else --itx;
50
        --ity;
51
        if (itx==ity&&x>itx->L&&y<itx->R){
52
            tmp=itx->R;
53
            itx->R=x;
54
            kdl.emplace(y,tmp);
55
            return;
56
        }
57
        if (x!=itx->L&&x<itx->R){
58
            itx->R=x;
59
            ++itx;
60
        }
61
        else if (x!=itx->L) ++itx;
62
        if (y!=ity->L&&y<ity->R) ity->L=y;
63
        else if (y!=ity->L) ++ity;
64
        kdl.erase(itx,ity);
65
    }
66
};

珂朵莉树祖先题