C++(g++ 7.5.0) 解法, 执行用时: 87ms, 内存消耗: 4856K, 提交时间: 2022-09-01 09:25:39

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;

using ll = long long ;
using pii = pair<int,int> ;

const int N = 1e5 + 100 ;

int n,m,k ;
int id[N] ;
pii q[N] ;
struct Node{
    int l,r ;
    int mx ;
}tr[N * 4];

void pushup(int u){
    tr[u].mx = max(tr[u<<1].mx,tr[u<<1|1].mx) ;
}

void build(int u,int l,int r){
    tr[u] = {l,r,q[l].second} ;
    if(l == r) return ;
    int mid = l + r >> 1 ;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r) ;
    pushup(u) ;
}

ll query(int u,int l,int r,int x){
    if(l > r || tr[u].mx < x) return 0 ;
    if(tr[u].l == tr[u].r){
        int tot = tr[u].mx ;
        tr[u].mx = 0 ;
        return tot ;
    }

    int mid = tr[u].l + tr[u].r >> 1 ; 
    ll ans = 0 ;
    if(l <= mid) ans += query(u<<1,l,r,x) ;
    if(r >= mid + 1) ans += query(u<<1|1,l,r,x) ;
    pushup(u) ;
    return ans ;
}

int main(){
    scanf("%d%d%d",&n,&m,&k) ;
    for(int i = 1 ; i <= m ; i ++) scanf("%d%d",&q[i].first,&q[i].second) ;
    sort(q+1,q+m+1) ;
    for(int i = 1 ; i <= m ; i ++) id[i] = q[i].first ;
    build(1,1,m) ;
    while(k --){
        int l,r,p ;
        scanf("%d%d%d",&l,&r,&p) ;
        l = lower_bound(id+1,id+m+1,l) - id ;
        r = lower_bound(id+1,id+m+1,r+1) - id - 1 ;
        
        printf("%lld\n",query(1,l,r,p)) ;
    }
    return 0 ;
}

C++(clang++ 11.0.1) 解法, 执行用时: 280ms, 内存消耗: 12044K, 提交时间: 2022-10-08 19:16:45

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll sum[N<<2];
int n,m,k;
multiset<int> ss[N];
int id[N];
ll ans=0;
void build(int p,int pl,int pr){
	if(pl==pr){
		for(auto v:ss[pl]) sum[p]+=v;
		return;
	}
	int mid=(pl+pr)>>1;
	build(p<<1,pl,mid);build(p<<1|1,mid+1,pr);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
void change(int p,int pl,int pr,int l,int r,int pp){
	if(pl==pr){
		auto it=ss[pl].end();it--;
		while((*(it))>=pp){
			sum[p]-=*it;
			ss[pl].erase(it);
			if(ss[pl].empty()) break;
			it=ss[pl].end();it--;
		}
		return;
	}
	int mid=(pl+pr)>>1;
	if(l<=mid&&sum[p<<1]) change(p<<1,pl,mid,l,r,pp);
	if(r>mid&&sum[p<<1|1]) change(p<<1|1,mid+1,pr,l,r,pp);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int pos,x;cin>>pos>>x;
		ss[pos].insert(x);
	}
	build(1,1,n);
	for(int i=1;i<=k;i++){
		int l,r,p;cin>>l>>r>>p;
		ll pre=sum[1];
		change(1,1,n,l,r,p);
		cout<<pre-sum[1]<<endl;
	}
	return 0;
}