题目描述
数轴上有 $n$ 个定点，其中点 $1$ 位于原点，点 $i(i\ge 2)$ 位于数轴上表示数 $x_i$ 的位置（$x_i\lt x_{i+1}$）。
这条数轴上还有 $m$ 条线段，第 $i$ 条线段的中点位于数轴上表示数 $z_i$ 的位置（$z_i$ 单调递增），从中点到线段两端点的距离都为 $l$（本题中，所有线段的 $l$ 都相同）。
对 $m$ 条线段进行 $d$ 次操作，第 $i$ 次操作将中点位于 $p_i$ 的一条线段移动至数轴上另一处，使得移动后线段的中点位置为 $r_i$（$p_i\neq r_i$）。保证移动前存在符合要求的线段，且移动后不会有其他线段的中点与该线段重合。
对于 $i=1,2,...,d$，输出执行第 $i$ 次操作之前，$n$ 个定点中被至少一条线段覆盖的点的数量（位于端点也算）。你还需要输出所有操作都完成后，$n$ 个定点中被至少一条线段覆盖的点的数量。
数据范围：$2\le n,m\le 5\times 10^5$，$1\le d\le 5\times 10^5$，$1\le l\le 10^9$，$0\lt x_i\le 10^9$，$0\le z_i,p_i,r_i\le 10^9$。
分析
注意到，题面中的操作很像扫描线中的“求线段长度并”的操作。那我们不妨就用扫描线的思想解决这道题。
显然，存在题目给定的数轴这一维和时间这一维。时间这一维由于题目的条件不用多加处理，因此我们只需处理数轴这一维。
开一棵线段树，区间对应题目中的定点区间。每次增加或删除一条线段就等价于增加或减少一次区间覆盖。
区间覆盖对应的线段树上操作是：如果当前节点表示的区间被修改区间完全包含，就直接执行覆盖/去覆盖的指令。否则向下递归，然后 Push_up。具体操作为：
- 每个节点维护该节点被完整覆盖的次数 $k$（初始为 $0$）和被覆盖的位置的个数 $sum$（初始也为 $0$），覆盖时把 $k$ 加上 $1$，去覆盖时把 $k$ 减去 $1$。
- 修改后，如果 $k=0$，叶子结点的 $sum$ 修改为 $0$，其他节点的 $sum$ 修改为两子节点的 $sum$ 之和；如果 $k\gt 0$，各节点的 $sum$ 修改为节点所对应的区间长度。(如果不注意加粗部分那么
恭喜你数组越界了）
一个节点的 Push_up 的操作与修改后的操作一致。
初始时，二分（或使用 lower_bound 和 upper_bound 找出）线段左右端点的位置，如果存在受影响的位置（端点未越界且区间存在/右端点在左端点右边），那么就将对应的连续区间进行覆盖就可以了。
执行操作时，先删除线段，再添加线段，操作细节同初始时的操作。不要忘记输出初始时和结束时的答案哦！
建立线段树的时间复杂度是 $\mathcal{O}(n)$，初始覆盖及所有操作的总时间复杂度为 $\mathcal{O}((m+d)\log n)$，对于 4s 的时间限制还是绰绰有余的。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define N 500007
int n,x[N];//由于 Seg 函数，需要把 n 定义在全局
struct qwq{int l,r,k,sum;}t[N<<2];//线段树
#define L(u) u<<1
#define R(u) u<<1|1
inline void build(int u,int l,int r){//建树
t[u]={l,r,0,0};
if(l<r){
int mid=(l+r)>>1;
build(L(u),l,mid),build(R(u),mid+1,r);
}
}
inline void Push_U(int u){//更新 sum
if(t[u].k) t[u].sum=t[u].r-t[u].l+1;//被完整覆盖过
else t[u].sum=t[L(u)].sum+t[R(u)].sum;//没被完整覆盖过
}
inline void Modify(int u,int l,int r,int val){
if(l<=t[u].l&&t[u].r<=r){//完全包含
t[u].k+=val;
if(t[u].l==t[u].r) t[u].sum=min(t[u].k,1)*(t[u].r-t[u].l+1);//注意对叶子的特判（WA+RE*2）
else Push_U(u);
return;
}
int mid=(t[u].l+t[u].r)>>1;
if(l<=mid) Modify(L(u),l,r,val);
if(r>mid) Modify(R(u),l,r,val);
Push_U(u);//更新当前节点
}
int l;//由于 Seg 函数，需要把 l 定义在全局，但线段树相关操作中存在以 l 命名的变量，故定义在此处
inline void Seg(int pos,int val){//线段覆盖/去覆盖
int pl=lower_bound(x+1,x+n+1,pos-l)-x;//对应的区间左端点
int pr=upper_bound(x+1,x+n+1,pos+l)-x-1;//对应的区间右端点
if(pl<=pr) Modify(1,pl,pr,val);//如果区间合法，那么修改
}//左右端点别写反！！！
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int m,d;
cin>>n>>m>>d>>l;
for(int i=2;i<=n;i++) cin>>x[i];
build(1,1,n);//别忘了建树！！
while(m--){
int z;
cin>>z;
Seg(z,1);
}
cout<<t[1].sum<<'\n';//初始答案
while(d--){
int p,r;
cin>>p>>r;
Seg(p,-1),Seg(r,1);//先删后加
cout<<t[1].sum<<'\n';//操作后答案
}
return 0;
}感谢您的阅读！