题解CF286D Tourists

· · 题解

题意

阴间翻译。。。

平面上有 n 面墙，第 i 面在 (0,l_i) 到 (0,r_i) 之间（包括端点），从时刻 t_i 开始出现，之后不会消失。

$1\le n,m\le 10^5,0\le l_i<r_i\le 10^9,0\le t_i,q_i\le 10^9$。

实际题面的 n,m 和这里是相反的，但是“n 次询问”实在不太顺眼。

题解

每个时刻两人所在位置显然是相同且固定的。

假设所有墙不相交，我们只需计算每面墙的贡献，加起来即可。

第 i 面墙对从 x 时刻出发的人贡献为 \min(r_i-l_i,\max(r_i+x-t_i,0))，也就是一个关于 x 的分段函数。

可以离线所有询问，把分段点扔进小根堆里，然后从小到大枚举 x 并维护这个和。

现在有墙相交的情况，但是每个位置的墙只需要取那个出现时间最早的。也就是我们直接预处理出最早出现时间的连续段即可。显然这个连续段数是 O(n) 的。

怎么找连续段？先把墙按 t_i 从小到大排序，那么现在要支持对某个区间中所有空位置进行覆盖。用 set 维护所有空的段，每次类似 ODT 进行空段的分裂和合并即可。

实际上这一步也可以离散化后用线段树解决。

总时间复杂度 O((n+m)\log n)。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
struct node{
    int l,r,x;
    bool operator <(const node &b)const{return x<b.x;}
}a[100005],b[300005];int cnt;
set<pair<int,int>>S;
struct Query{
    int x,id;
    bool operator <(const Query &b)const{return x<b.x;}
}que[100005];
int ans[100005];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x);
    sort(a+1,a+n+1);
    S.insert(make_pair(0,1e9));
    for(int i=1;i<=n;i++){
        int l=a[i].l,r=a[i].r;
        auto it=S.lower_bound(make_pair(l,0));
        if(it!=S.begin()){
            auto p=*--it;
            if(l<p.second){
                S.erase(p);
                S.insert(make_pair(p.first,l));
                S.insert(make_pair(l,p.second));
            }
        }
        it=S.lower_bound(make_pair(r,0));
        if(it!=S.begin()){
            auto p=*--it;
            if(r<p.second){
                S.erase(p);
                S.insert(make_pair(p.first,r));
                S.insert(make_pair(r,p.second));
            }
        }
        it=S.lower_bound(make_pair(l,0));
        while(it!=S.end()&&(*it).first<r){
            b[++cnt]=(node){(*it).first,(*it).second,a[i].x};
            S.erase(it);
            it=S.lower_bound(make_pair(l,0));
        }
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>que1,que2;
    for(int i=1;i<=cnt;i++)que2.push(make_pair(b[i].x-b[i].r,i));
    for(int i=1;i<=m;i++)scanf("%d",&que[i].x),que[i].id=i;
    sort(que+1,que+m+1);
    ll sum=0;int tot=0;
    for(int i=1;i<=m;i++){
        while(!que2.empty()&&que2.top().first<=que[i].x){
            int j=que2.top().second;que2.pop();
            sum+=b[j].r-b[j].x;tot++;
            que1.push(make_pair(b[j].x-b[j].l,j));
        }
        while(!que1.empty()&&que1.top().first<=que[i].x){
            int j=que1.top().second;que1.pop();
            sum+=b[j].x-b[j].l;tot--;
        }
        ans[que[i].id]=sum+1ll*tot*que[i].x;
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}