题目传送门
solution
简单题，考虑正着做扫描线，维护最后一次覆盖每个位置的修改时间，这个可以用 \(set\) 维护颜色段数均摊。
那么显然对于一个以当前位置为右端点的询问，其答案就是所有最后修改时间大于等于左端点的位置的数的和。
开一个树状数组维护最后一次修改时间是 \(i\) 的位置上的数的和即可。
复杂度 \(O(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
struct Info
{
int l,r,c;
};
bool operator <(Info A,Info B)
{
return A.l<B.l;
}
int n,m,q;
set<Info> col;
typedef long long LL;
LL C[N];
void upd(int x,LL v)
{
for(int i=x;i;i-=i&-i)C[i]+=v;
}
LL ask(int x)
{
LL res=0;
for(int i=x;i<=m;i+=i&-i)res+=C[i];
return res;
}
#define pot set<Info>::iterator
pot Split(int x)
{
if(x>n)return col.end();
pot it=(--col.upper_bound((Info){x,0,0}));
if((*it).l==x)return it;
int l=(*it).l,r=(*it).r,c=(*it).c;
col.erase(it);
col.insert((Info){l,x-1,c});
return col.insert((Info){x,r,c}).first;
}
int lp[N],rp[N],w[N];
void Cov(int len,int t,int op)
{
upd(t,1ll*len*w[t]*op);
}
void Assign(int l,int r,int c)
{
pot itr=Split(r+1),itl=Split(l);
for(auto it=itl;it!=itr;it++) Cov((*it).r-(*it).l+1,(*it).c,-1);
Cov(r-l+1,c,1);
col.erase(itl,itr);
col.insert((Info){l,r,c});
}
#define PII pair<int,int>
#define mk(x,y) make_pair(x,y)
#define X(x) x.first
#define Y(x) x.second
vector<PII> G[N];
LL Ans[N];
int main()
{
cin>>m>>n>>q;
for(int i=1;i<=m;i++)scanf("%d %d %d",&lp[i],&rp[i],&w[i]);
col.insert((Info){1,n,0});
for(int i=1;i<=q;i++)
{
int l,r;
scanf("%d %d",&l,&r);
G[r].push_back(mk(l,i));
}
for(int i=1;i<=m;i++)
{
Assign(lp[i],rp[i],i);
for(auto U:G[i])Ans[U.second]=ask(U.first);
}
for(int i=1;i<=q;i++)printf("%lld\n",Ans[i]);
return 0;
}