codeforce1679C. Rooks Defenders_codeforces1679c

传送门：线段树也不过如此

---

这标准线段树模板题，但是多年没碰线段树，现在已经基本不会写了T^T

首先是创建线段树。
线段树是个满二叉树，如果从长度为n的数组上生成线段树，那么树节点个数m满足

$$m\le 2^{q+1}-1$$

其中$2^q>n\wedge 2^{q-1}<n$
此外对于满二叉树来说，假设当前节点编号为n,则left node编号为$2n$,right node编号为$2n+1$，ancestor编号为$n/2$。借助这些性质可以实现在数据中存储树节点时快速访问。
应用到这个题来说，需要建两棵线段树：一颗记录行，一颗记录列。根据题意，初始状态下没有rock，所以叶结点val都是0

然后是线段树更新：首先到叶结点，更新叶结点数据；然后，回溯的时候更新ancestor中记录的区间的值。
对于这个题来说，行线段树中非叶结点中记录的是从left行到right行中，一行最少有几个rock。回溯时根据left和right节点的值更新区间最小值。列线段树同理。

最后是查询。首先要明确的一点是，查询的区间$x$始终是数组的子区间$x\subset [1,n]$，所以查询的时候只考虑Ⅰ情况即可

具体到每个非叶结点所代表的区间查询时，借助中间变量mid来判断下一步需要查询的区间。设需要查询的区间为$[l,r]$，非叶结点代表区间$[L,R]$，非叶节点代表区间的区间中点为$mid$

如果$mid<l$,说明需要去区间$[mid,R]$进一步查询，故go to right；
如果$r<mid$,说明需要去区间$[L,mid]$进一步查询， 故go to left；
如果$l<mid\wedge mid<r$,则说明需要在left 和 right两个子节点都进行查询。
如果$l\le L\wedge R\le r$,也就是非叶节点代表区间x是待查询区间的子区间时，停止查询，返回该区间x的val。

其实线段树查询的时候，不断将查询区间细分，分为线段树中记录的区间，再见这些区间合并，最终得出结果。

具体到这个题，需要查询的是区间最小值，也就是所有子区间的最小值。

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define Pair pair<int,int>
#define re return

#define getLen(name,index) name[index].size()
#define mem(a,b) memset(a,b,sizeof(a))
#define Make(a,b) make_pair(a,b)
#define Push(num) push_back(num)
#define rep(index,star,finish) for(register int index=star;index<finish;index++)
#define drep(index,finish,star) for(register int index=finish;index>=star;index--)
using namespace std;

template<class T> void _deb(const char *name,T val){
    cout<<name<<val<<endl;
}

const int MAXN = 1e5+5;

struct tree{
    int left,right;
    int attacked;
};

int n,q;
tree row[MAXN*4],col[MAXN*4];
int creat(int pos,int l,int r, tree* T);
void update(int pos,bool, tree*);
int query(int l,int r,int pos, tree*);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>q;
    creat(1,1,n, row);
    creat(1,1,n, col);
    while(q--) {
        int sym;
        cin>>sym;
        int commonA,commonB;
        switch(sym) {
            case 1:
                // insert
                cin>>commonA>>commonB;
                update(commonA,true,row);
                update(commonB,true, col);
                break;
            case 2:
                // remove
                cin>>commonA>>commonB;
                update(commonA,false,row);
                update(commonB,false,col);
                break;
            case 3:
                // query
                int x1,x2,y1,y2;
                cin>>x1>>y1>>x2>>y2;
                int ans = max(query(x1,x2,1,row), query(y1,y2,1,col));
                if(ans>0){
                    cout<<"YES"<<endl;
                }else{
                    cout<<"NO"<<endl;
                }
                break;
        }
    }

    re 0;
}
int creat(int pos,int l,int r, tree* T) {
    T[pos].left = l,T[pos].right = r;
    if(r == l) {
        return T[pos].attacked = 0;
    }

    int mid = l + (r-l)/2;
    int left_ans = creat(pos<<1,l,mid,T);
    int right_ans = creat(pos<<1|1, mid+1, r,T);
    return T[pos].attacked = 0;
}
void update(int pos,bool sta, tree* T){
    int inf = T[1].left;
    int sup = T[1].right;
    int nowPos = 1;
    while(inf<sup) {
        int mid = inf+(sup-inf)/2;
        if(pos>mid) {
            nowPos = nowPos<<1|1;
            inf = T[nowPos].left;
        }else{
            nowPos = nowPos<<1;
            sup = T[nowPos].right;
        }
    }

    T[nowPos].attacked = sta? T[nowPos].attacked+1 : T[nowPos].attacked-1;
    while(nowPos!=1) {
        nowPos = nowPos>>1;
        T[nowPos].attacked = min(T[nowPos<<1|1].attacked ,T[nowPos<<1].attacked);
    }
}
int query(int l,int r,int pos, tree* T){
    if(l<=T[pos].left && T[pos].right <= r){
        return T[pos].attacked;
    }
    int mid = T[pos].left + (T[pos].right - T[pos].left)/2;
    int ans = INT_MAX;
    if(r>mid){
        ans = min(ans, query(l,r,pos<<1|1, T));
    }
    if(l<=mid) {
        ans = min(ans,query(l,r,pos<<1, T));
    }
    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
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