题解 | #弩蚊怒夏#

假如 个蚊子的位置都不一样的话，维护区间最大值。因为每个位置只会被访问一遍，所以复杂度还是 。当遇到这个区间的最大值小于要拍死的体型最小值时，就退出，不然递归到叶子节点。现在因为 个蚊子的位置可能重叠，那么其实我们可以排个序拍扁序列，重新排列一下位置，记录下来即可。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;

int ml[maxn],mr[maxn],vs[maxn],n,m,ct;
struct nd{
    int pos,w;
    inline bool operator<(const nd&x)const{
        return pos!=x.pos?pos<x.pos:w<x.w;
    }
}a[maxn];
struct node{
    int l,r;
    ll w,mx;
}t[maxn<<2];

inline void pushup(int k)
{
    t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
    t[k].w=t[k<<1].w+t[k<<1|1].w;
} 

inline void build(int k,int l,int r)
{
    t[k].l=l,t[k].r=r;
    if(l==r){t[k].w=t[k].mx=a[l].w; return;}
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k); return;
}

inline ll update(int k,int l,int r,int p)
{
    int x=t[k].l,y=t[k].r;
    if(l<=x&&y<=r&&t[k].mx<p)return 0;
    if(x==y)
    {
        ll res=t[k].w;
        t[k].w=t[k].mx=0;
        return res;
    }
    int mid=x+y>>1; ll res=0;
    if(l<=mid)res+=update(k<<1,l,r,p);
    if(mid<r)res+=update(k<<1|1,l,r,p);
    pushup(k); return res; 
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>ct>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i].pos>>a[i].w;
    sort(a+1,a+1+n); memset(ml,127/5,sizeof(ml));
    for(int i=1;i<=n;i++)
    {
        vs[a[i].pos]=3;
        ml[a[i].pos]=min(ml[a[i].pos],i);
        mr[a[i].pos]=max(mr[a[i].pos],i);
    }
    for(int i=1;i<=n;i++)
    {
        if(vs[i]>2)
        {
            for(int j=i-1;j>=1;j--)
            {
                if(vs[j]>2)break; ml[j]=ml[i];
            }
            for(int j=i+1;j<=n;j++)
            {
                if(vs[j]>2)break; mr[j]=mr[i];
            }
        }
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int l,r,p; cin>>l>>r>>p;
        if(ml[l]<=mr[r])cout<<update(1,ml[l],mr[r],p)<<"\n";
        else cout<<0<<"\n";
    }
    return 0;
}