直接做不好做,考虑离线。这个覆盖操作和这道题很像,可以直接对某些段暴力修改,可以直接上 ODT。发现当 ODT 执行这些操作时,是容易求出不执行某些操作后带来的值的影响的,即可以直接用树状数组维护每个位置现在是被那个操作覆盖,求出 \(1\) 到 \(x\) 操作还覆盖了那些位置,以及这些位置的值是容易的,用当前的总和减去这些值即可。
具体地,可以直接扫描 \(r\),vector 存储一下每个询问即可。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
#define pb push_back
const int N=5e5+10;
int n,m,Q,num;
ll ans[N];
struct node{
int l,r,v;
} q[N];
vector<pii> que[N];
struct BIT{
ll c[N];
void add(int x,ll y){
for(;x<=m+1;x+=x&-x)c[x]+=y;
}
ll ask(int x){
ll res=0;
for(;x;x-=x&-x)res+=c[x];
return res;
}
ll ask(int l,int r){
return ask(r)-ask(l-1);
}
} T;
struct ODT{
mutable ll t;
int l,r;
ODT(const int &tl,const int &tr,const ll &tt){l=tl,r=tr,t=tt;}
friend bool operator<(ODT a,ODT b){return a.l<b.l;}
};
set<ODT> s;
typedef set<ODT>::iterator iter;
iter split(int x){ // [l,x)[x,r]
iter it=--s.upper_bound(ODT{x,0,0});
if(it->l==x)return it;
int l=it->l,r=it->r;ll t=it->t;s.erase(it);
s.insert(ODT{l,x-1,t});
return s.insert(ODT{x,r,t}).first;
}
void assign(int l,int r,int tim){
iter itr=split(r+1),itl=split(l),it=itl;
for(;it!=itr;it++)T.add(it->t,-(it->r-it->l+1)*1ll*q[it->t].v);
s.erase(itl,itr);
s.insert(ODT{l,r,tim});
T.add(tim,(r-l+1)*1ll*q[tim].v);
}
int main(){
cin>>m>>n>>Q;
for(int i=2;i<=m+1;i++)cin>>q[i].l>>q[i].r>>q[i].v;
for(int i=1,l,r;i<=Q;i++){
cin>>l>>r;
que[r+1].pb(pii(l+1,i));
}
s.insert(ODT{1,n,1});
for(int tim=2;tim<=m+1;tim++){
assign(q[tim].l,q[tim].r,tim);
for(pii qi:que[tim])ans[qi.second]=T.ask(qi.first,tim);
}
for(int i=1;i<=Q;i++)cout<<ans[i]<<"\n";
return 0;
}