思路

首先考虑维护每个机器最后启动的时间，容易发现造零件的区间就是区间覆盖公差为 $1$ 的等差数列。

有了区间推平，所以尝试用 ODT 维护机器启动的过程，记录下数列开头的启动时间和段的长度，考虑查询怎么做，发现因为都是覆盖等差数列，所以如果一个开头需要检查，那么它所在的段都需要检查，在覆盖的时候把每个机器的使用间隔记录下来，因为覆盖的都是等差数列，所以一个段的机器的使用间隔都是相等的，同样，记录开头即可。

把间隔离线下来，从小到大排序，发现对于一个询问，答案一定是所有间隔的一个后缀，因为是 $\ge s_i$ 的计数，而且显然 $s_i$ 越小后缀越大，所以考虑双指针，对 $s$ 离线排序，$s$ 的指针从左往右，间隔的指针从右往左，如果开头 $\ge s$，那么整个段都要计入答案。

具体看代码

code

int n,m,q,l,r,cnt,now=1,ans[N];
struct ODT{
    int l,r;mutable int v;
    ODT(int L,int R=-1,int V=0):l(L),r(R),v(V){}
    bool operator<(const ODT&a)const{return l<a.l;}
};
struct node{int s,id;}a[N];
vector<PI> d;set<ODT> s;
bool cmp(node a,node b){return a.s>b.s;}
IT split(int p){
    IT it=s.lower_bound(p);
    if(it!=s.end()&&it->l==p) return it;
    --it;
    int l=it->l,r=it->r,vl=it->v;
    s.erase(it);
    s.insert(ODT(l,p-1,vl));                                                                                                                            
    return s.insert(ODT(p,r,vl+p-l)).ff;
}
void change(int l,int r,int v){
    IT tr=split(r+1),tl=split(l);
    int nw=v;
    for(IT it=tl;it!=tr;it++){                            
        d.pb(mk(nw-it->v,it->r-it->l+1));
        nw+=it->r-it->l+1;
    }s.erase(tl,tr);
    s.insert(ODT(l,r,v));
}
signed main(){
    read(n,m,q);
    s.insert(ODT(1ll,n,INF));
    rep(i,1,m){
        read(l,r);
        change(l,r,now);
        now+=r-l+1;
    }
    rep(i,1,q) read(a[i].s),a[i].id=i;
    sort(a+1,a+q+1,cmp);
    sort(d.begin(),d.end());
    rep(i,1,q){
        while(d.size()&&d.back().ff>a[i].s)
            cnt+=d.back().ss,d.pop_back();
        ans[a[i].id]=cnt;
    }
    rep(i,1,q) cout<<ans[i]<<" ";
    return 0;
}