先考虑没有区间限制怎么做，即执行完所有操作在询问全局和。用 \(set\) 维护连续段,就是珂朵莉树，写个模板即可。
加上区间限制呢？先将询问按照 \(r\) 排序。又因为还要维护每个 \(l\)，就在颜色段上在记录加入时间。我们在时间维开个数据结构，简单的树状数组即可。时间复杂度 \(O(nlogn)\)
#include<bits/stdc++.h>
#define ll long long
#define N 500001
#define It set<node>::iterator
using namespace std;
ll n,m,q,ql,qr,ans[N],tr[N];
struct xs{ll l,r,v;}opt[N];
vector<pair<ll,ll> > g[N];
struct node{ll l,r,t,v;
bool operator<(node x)const{return l<x.l;}
};
set<node> s;
void add(ll x,ll d){if(x>0)for(;x<=n;x+=(x&(-x)))tr[x]+=d;}
ll ask(ll x){ll sum=0;for(;x;x-=(x&(-x)))sum+=tr[x];return sum;}
It spl(ll x){It it=s.lower_bound({x,0,0,0});
if(it->l==x)return it;
it--;
ll l=it->l,r=it->r,v=it->v,t=it->t;
s.erase(it),s.insert({l,x-1,t,v});
return s.insert({x,r,t,v}).first;
}
void ass(ll l,ll r,ll id,ll v){It itr=spl(r+1),itl=spl(l);
for(It it=itl;it!=itr;++it)add(it->t,-1ll*(it->r-it->l+1)*it->v);
s.erase(itl,itr),add(id,(r-l+1)*v),s.insert({l,r,id,v});
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++)cin>>opt[i].l>>opt[i].r>>opt[i].v;
for(int i=1;i<=q;i++)cin>>ql>>qr,g[qr].push_back({ql,i});
s.insert({0,m+1,0,0});
for(int i=1;i<=n;i++){ass(opt[i].l,opt[i].r,i,opt[i].v);
for(auto v:g[i])ans[v.second]=ask(i)-ask(v.first-1);
}
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}