题目链接 : [Ynoi Easy Round 2021] TEST_152
一道思路接近却比这道题难点的题目 [Ynoi2012] NOIP2015 充满了希望
经典结论 : 无论怎么覆盖，总段数都是\(O(覆盖次数)\)的。
证明的话，考虑到每次推平只会使得左右端点的段分裂开，使得段数+1，而中间的段直接被覆盖，所以最多总段数只会为\(O(n)\)
如何维护全局和？直接用一个ODT维护连续段即可，推平时减去原贡献，加上新贡献。
but有一个操作的区间限制，直接将询问挂在r上扫描线。
用一个树状数组维护当前时间下每个时间的贡献，加减贡献都在这个树状数组上加减。
时间复杂度\(O(n\log n)\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e5 + 10;
struct BIT{
private:
ll tree[N];
#define lowbit(x) (x&(-x))
public:
int mx;
inline void update(int pos,ll val){
if(!pos) return;
for(int i = pos;i <= mx;i += lowbit(i))
tree[i] += val;
}
inline ll query(int pos){
ll res = 0;
for(int i = pos; i;i -= lowbit(i))
res += tree[i];
return res;
}
}Tr;
class ODT{
private:
struct node{
int l,r;mutable int val,tim;
bool operator < (node x) const {return l < x.l;};
node(int L,int R = 0,int Val = 0,int Tim = 0):l(L),r(R),val(Val),tim(Tim){}
};
set<node> s;
#define sit set<node>::iterator
public:
inline sit split(int pos){
sit it = s.lower_bound(node(pos));
if(it != s.end() && it->l == pos) return it;
it--;
int l = it->l,r = it->r,val = it->val,tim = it->tim;
s.erase(it);
s.insert(node(l,pos-1,val,tim));
return s.insert(node(pos,r,val,tim)).first;
}
inline void assign(int l,int r,int val,int tim){
sit it2 = split(r+1),it1 = split(l);
for(auto it = it1;it != it2; ++it)
Tr.update(it->tim,-1ll*(it->r - it->l + 1) *(it->val));
Tr.update(tim,1ll*(r-l+1)*val);
s.erase(it1,it2);
s.insert(node(l,r,val,tim));
}
inline void insert(int l,int r,int val){s.insert(node(l,r,val));}
}T;
int n,m,q;
ll ans[N];
struct node{int id,l;};
vector<node> Q[N];
struct node1{int l,r,val;}c[N];
inline void solve(){
cin>>n>>m>>q;
Tr.mx = n;
T.insert(1,m,0);
for(int i = 1,l,r,v;i <= n; ++i){
cin>>l>>r>>v;
c[i] = {l,r,v};
}
for(int i = 1,l,r;i <= q; ++i){
cin>>l>>r;
Q[r].push_back({i,l});
}
for(int i = 1;i <= n; ++i){
T.assign(c[i].l,c[i].r,c[i].val,i);
for(auto j:Q[i]) ans[j.id] = Tr.query(i) - Tr.query(j.l-1);
}
for(int i = 1;i <= q; ++i) cout<<ans[i]<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}