Codeforces round 810 (Div. 2) d. rain (segment tree difference)

Codeforces Round #810 (Div. 2) D. Rain ( Segment tree difference )

Preface ： A problem that disgusted me for nearly a day , common $180$ OK, knock repeatedly $3$ Time , I do not know! $d$ How long has it been $bug$ , Or is there too little line segment tree theme .

---

The question ： Given a $n$ , this $n$ It will rain , Every rainy day has a $x$ And a $p$ , From $x$ Centered , Rainfall decreases to the left and right , for example $x=3$ 、$p=5$ In the case of ：

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

ask ： Statistics will turn any day into a non rainy day , Whether the maximum rainfall in all places does not exceed $m$ , No more than output $1$ Otherwise output $-1$

---

Ideas ： First of all, it is obvious that this problem is differential , That is, the center of rainfall to the left and right sides with tolerance $d=1$ Step by step , adopt Boring series ( Classical line segment tree difference ) We can know in $O(nlogn)$ Calculate this within the time complexity $n$ When it rains, all rainfall centers Rainfall value This can be achieved through a segment tree . The remaining steps are enumeration $1$ ~ $n$ One day in without rain , Whether the maximum rainfall in all places is less than $m$ , We open the second segment tree to maintain the three maximum values, namely $h[l]、h[l]-vec[l]、h[l]+vec[l]$ The first $h[l]$ It indicates the maximum rainfall in all regions in the case that the rainfall days are not involved in the current enumeration , Because the precipitation will not decrease . The other two are uphill and downhill Offset writing , Used to compare numbers on the same slash at the same level , Get the maximum precipitation in the interval .

---

Code ：

/* * @author: Snow * @Description: Algorithm Contest * @LastEditTime: 2022-07-27 10:51:20 */
#include<bits/stdc++.h>
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;
}