A50543.聊天室 题解

如果开始聊天的时刻 $l'$ 确定，那么最早结束时间 $r'$ 是多少？显然为 $l'+d-1$。

那么开始聊天的时刻是什么时候呢？显然是 $u_i$ 或者 $l_j$ 中的一个。

如果网友上线比 Alice 晚，也就是 $l_j \geq u_i$ 的时候。不难想到按照 $r_j-l_j$ 从大到小排序，再按照 $d_i$ 从大到小排序，然后双指针求解。（这样就需要我们离线处理）当我们找到了一个满足条件的区间 $[l_j,r_j]$ 的时候，记录 $l_i$，最后判断 $[u_i,v_i]$ 中是否有记录即可。

这个过程暴力做是 $O(nm)$ 的，可以使用树状数组，将 $l_i$ 这个点增加 $1$，最后查询 $[u_i,v_i]$ 范围内的和是否为正数。这样是 $O((m+q) \log n)$ 的。

如果网友上线比 Alice 早，也就是 $l_j<u_i$ 的时候，不难想到按照 $l_j$ 和 $u_i$ 从小到大排序，也可以双指针求解。如果区间 $[l_j,r_j]$ 满足 $l_j<u_i$，那么记录 $r_j$，最后判断记录中，${r_j}_{\max}$ 是否满足 ${r_j}_{\max} \geq u_i+d_i-1$ 即可。同样地，暴力做是 $O(nm)$，我使用的是大根堆优化，时间复杂度是 $O((m+q) \log m)$ 的复杂度。

能想到，如果这两种讨论中，满足任意一种，就是 Yes。这样就做完了。

时间复杂度：$O((m+q) \log n+(m+q) \log m)$.

空间复杂度：$O(n+m+q)$.

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5e5+55;
struct node{
    ll l,r,d,id;
};
ll n,m,q,l,r;
ll bitr[MAXN];
bool vis[MAXN];
node a[MAXN],b[MAXN];
priority_queue<ll> pq;
inline ll lowbit(const ll &x){return x&-x;}
inline void update(const ll &q,const ll &c){
    for(ll i=q;i<=n;i+=lowbit(i)) bitr[i]+=c;
    return;
}
inline ll query(const ll &q){
    ll res=0;
    for(ll i=q;i;i-=lowbit(i)) res+=bitr[i];
    return res;
}
int main(){
    cin>>n>>m>>q;
    for(ll i=1;i<=m;i++) cin>>a[i].l>>a[i].r;
    for(ll i=1;i<=q;i++){
        cin>>b[i].l>>b[i].r>>b[i].d;
        b[i].id=i;
    }
    //网友上线比Alice晚
    sort(a+1,a+1+m,[](const node &a,const node &b){
        return a.r-a.l>b.r-b.l;
    });
    sort(b+1,b+1+q,[](const node &a,const node &b){
        return a.d>b.d;
    });
    l=r=1;
    while(r<=q){
        while(l<=m){
            if(a[l].r-a[l].l+1<b[r].d) break;
            update(a[l].l,1);
            l++;
        }
        if(query(b[r].r-b[r].d+1)-query(b[r].l-1)) vis[b[r].id]=true;
        r++;
    }
    //网友上线比Alice早
    sort(a+1,a+1+m,[](const node &a,const node &b){
        return a.l<b.l;
    });
    sort(b+1,b+1+q,[](const node &a,const node &b){
        return a.l<b.l;
    });
    l=r=1;
    while(r<=q){
        while(l<=m&&a[l].l<b[r].l) pq.push(a[l++].r);
        if(!pq.empty()&&pq.top()>=b[r].l+b[r].d-1) vis[b[r].id]=true;
        r++;
    }
    for(ll i=1;i<=q;i++){
        if(vis[i]) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}