Codeforces Round #810 (Div. 2) D. Rain (线段树差分)

Codeforces Round #810 (Div. 2) D. Rain (线段树差分)

前言： 一道恶心了我近一天的题,共 $180$ 行重复敲了 $3$ 次 ， 不知道 $d$ 了多久的 $bug$ ，还是线段树专题做的太少了。

---

题意： 给定一个 $n$ ，这 $n$ 天会降雨，每一个降雨天有一个 $x$ 和一个 $p$ ，表示自 $x$ 为中心，降雨量向左右两边递减，例如 $x=3$ 、$p=5$ 的情况为：

0 1 2 3 4 5 4 3 2 1 0
-2 -1 0 1 2 3 4 5 6 7 8

问：统计将任意一天天气变成非降雨天，所有地的最大降雨量是否不超过 $m$ ，不超过输出 $1$ 否则输出 $-1$

---

思路： 首先本题很明显得知具有差分性，即降雨中心向左右两边以公差 $d=1$ 逐步递减，通过 无聊的数列(经典线段树差分) 可知我们可以在 $O(nlogn)$ 的时间复杂度内计算出这 $n$ 天都下雨情况下所有降雨中心的 降雨值 这可以通过一个线段树实现。剩下的步骤就是枚举 $1$ ~ $n$ 中的某一天不降雨情况下，所有地的降雨最大值是否小于 $m$ ，我们开第二棵线段树用来维护三个最大值即 $h[l]、h[l]-vec[l]、h[l]+vec[l]$ 其中第一个 $h[l]$ 表示不被当前枚举的降雨天所涉及情况下各地中降雨的最大值，因为降水量不会减少 。 其余两个分别是上坡与下坡的 偏移量写法 ，用来将同一斜线上的数置于同一水平上比较，得出区间降水最大值。

---

代码：

/*
 * @author:  Snow
 * @Description:  Algorithm Contest
 * @LastEditTime: 2022-07-27 10:51:20
 */
#include
using namespace std;
#define int long long 
#pragma GCC optimize(3)
#define re register int
typedef pair<int,int>PII;
#define pb emplace_back
#define debug(a) cout<<a<<' ';
#define fer(i,a,b) for(re i=a;i<=b;i++)
#define der(i,a,b) for(re i=a;i>=b;i--)
int n,m;
const int N = 2e5+10;
int x[N],p[N];
vector<int>vec2;
int vec[N*4];
int h[N*4];
char ans[N];
struct Seg_tree1{
    struct Node{
        int l,r,k,d;
    }tr[N*16];
    void build(int u,int l,int r){
        if(l==r){
            tr[u]={l,r,0,0};
        }
        else{
            int mid=l+r>>1;
            tr[u]={l,r};
            build(u<<1,l,mid);
            build(u<<1|1,mid+1,r);
        }
    }
    void pushdown(int u){
        if(tr[u].k||tr[u].d){
            int mid=tr[u].l+tr[u].r>>1;
            tr[u<<1].k+=tr[u].k;
            tr[u<<1|1].k+=tr[u].k+(vec[tr[u<<1|1].l]-vec[tr[u].l])*tr[u].d;
            tr[u<<1].d+=tr[u].d;
            tr[u<<1|1].d+=tr[u].d;
            tr[u].d=tr[u].k=0;
        }
    }
    void modify(int u,int l,int r,int k,int d){
        if(tr[u].l>=l&&tr[u].r<=r){
            tr[u].k+=k+(vec[tr[u].l]-vec[l])*d;
            tr[u].d+=d;
        }
        else{
            pushdown(u);
            int mid=tr[u].l+tr[u].r>>1;
            if(l<=mid)modify(u<<1,l,r,k,d);
            if(r>mid)modify(u<<1|1,l,r,k,d);
        }
    }
    void floor(int u){
        if(tr[u].l==tr[u].r){
            h[tr[u].l]=tr[u].k;
        }
        else{
            pushdown(u);
            floor(u<<1);
            floor(u<<1|1);
        }
    }
}seg1;
struct Seg_tree2{
    struct Node{
        int l,r,v1,v2,v3;
    }tr[N*16];
    void pushup(int u){
        tr[u].v1=max(tr[u<<1].v1,tr[u<<1|1].v1);
        tr[u].v2=max(tr[u<<1].v2,tr[u<<1|1].v2);
        tr[u].v3=max(tr[u<<1].v3,tr[u<<1|1].v3);
    }
    void build(int u,int l,int r){
        if(l==r){
            tr[u]={l,r,h[l],h[l]-vec[l],h[l]+vec[l]};
        }
        else{
            tr[u]={l,r};
            int mid=l+r>>1;
            build(u<<1,l,mid);
            build(u<<1|1,mid+1,r);
            pushup(u);
        }
    }
    Node query(int u,int l,int r){
        if(tr[u].l>=l&&tr[u].r<=r){
            return tr[u];
        }
        int mid=tr[u].l+tr[u].r>>1;
        if(r<=mid)return query(u<<1,l,r);
        if(l>mid)return query(u<<1|1,l,r);
        Node res;
        Node left=query(u<<1,l,r);
        Node right=query(u<<1|1,l,r);
        res.v1=max(left.v1,right.v1);
        res.v2=max(left.v2,right.v2);
        res.v3=max(left.v3,right.v3);
        return res;
    }
}seg2;
void cf(){
    vec2.clear();
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>x[i]>>p[i];
    for(int i=1;i<=n;i++){
        vec2.push_back(x[i]);
        vec2.push_back(x[i]-p[i]+1);
        vec2.push_back(x[i]+1);
        vec2.push_back(x[i]+p[i]-1);
    }
    sort(vec2.begin(),vec2.end());
    vec2.erase(unique(vec2.begin(),vec2.end()),vec2.end());
    for(int i=1;i<=vec2.size();i++)vec[i]=vec2[i-1];
    int len=vec2.size();
    seg1.build(1,1,len);
    for(int i=1;i<=n;i++){
        int l=lower_bound(vec+1,vec+1+len,x[i]-p[i]+1)-vec;
        int r=lower_bound(vec+1,vec+1+len,x[i])-vec;
        if(l<=r){
            seg1.modify(1,l,r,1,1);
        } 
        l=lower_bound(vec+1,vec+1+len,x[i]+1)-vec;
        r=lower_bound(vec+1,vec+1+len,x[i]+p[i]-1)-vec;
        if(l<=r){
            seg1.modify(1,l,r,p[i]-1,-1);
        }
    }
    seg1.floor(1);
    seg2.build(1,1,len);
    fer(i,1,n){
        int maxv=0;
        int l=lower_bound(vec+1,vec+1+len,x[i]-p[i]+1)-vec;
        int r=lower_bound(vec+1,vec+1+len,x[i])-vec;
        if(l>1){
            int t=seg2.query(1,1,l-1).v1;
            maxv=max(maxv,t);
        }
        if(l<=r){
            int t=seg2.query(1,l,r).v2;
            maxv=max(maxv,t+vec[l]-1);
        }
        l=lower_bound(vec+1,vec+1+len,x[i]+1)-vec;
        r=lower_bound(vec+1,vec+1+len,x[i]+p[i]-1)-vec;
        if(r+1<=len){
            int t=seg2.query(1,r+1,len).v1;
            maxv=max(maxv,t);
        }
        if(l<=r){
            int t=seg2.query(1,l,r).v3;
            maxv=max(maxv,t-vec[r]-1);
        }
        ans[i]=maxv<=m?'1':'0';
    }
    fer(i,1,n)cout<<ans[i];
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        cf();
    }
    return 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
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
166
167
168
169
170
171
172