P8512 [Ynoi Easy Round 2021] TEST_152 题解

· · 题解

easy round 果然善良。

有一个性质是无论怎么覆盖总段数都是 O(n) 的。

证明比较显然，一开始只有一段，每次操作只可能在两边将两个段拆成不完整段，中间段全部覆盖，所以对于每一次操作增加段数是 O(1) 的，那么总段数就是 O(n)。

考虑没有区间限制，执行全部操作后询问全局和怎么做。直接搞一个 set 维护连续段即可。推平时减原段贡献，加上现贡献。

加了区间限制后可以直接将询问挂在 r 上扫描线，发现还要维护对于每一时间 l 的和是多少。那么在颜色段上再记录加入时间即可，被删除时就在原时间处 -len\times val。所以我们在时间维开个数据结构，需要支持单点加，区间查，简单树状数组即可。总共 O(n) 个段，每段插删复杂度 O(\log{n})，维护连续段，回答询问总共需要 O(n\log{n})，总复杂度 O(n\log{n})。

没啥实现难度，注释删了即可。

#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define int long long
int n,m,q,a[N],ta,t[N],l[N],r[N],w[N],out[N];
inline void add(int x,int v){if(x>0) while(x<=n) t[x]+=v,x+=(x&-x);}
inline int ask(int x){ta=0;while(x) ta+=t[x],x^=(x&-x);return ta;}
struct query{int l,id;};
vector<query> v[N];
struct node{mutable int l,r,t,v;};
bool operator<(const node &a,const node &b){return a.l<b.l;}
set<node> s;
#define It set<node>::iterator
It split(int x){
    It it=s.lower_bound((node){x,0,0,0});
    if(it->l==x) return it;
    it--;int l=it->l,r=it->r,v=it->v,t=it->t;
    s.erase(it);s.insert((node){l,x-1,t,v});
    return s.insert((node){x,r,t,v}).first;
}
void assign(int l,int r,int t,int v){
    It itr=split(r+1),itl=split(l);
    for(It it=itl;it!=itr;++it) add(it->t,-1ll*(it->r-it->l+1)*it->v);
    s.erase(itl,itr);add(t,(r-l+1)*v);s.insert((node){l,r,t,v});
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;++i) cin>>l[i]>>r[i]>>w[i];
    for(int i=1,l,r;i<=q;++i) cin>>l>>r,v[r].push_back((query){l,i});
    //s.insert((node){0,m+1,0,0});
    for(int Q=1;Q<=n;++Q){
        assign(l[Q],r[Q],Q,w[Q]);
        for(int i=0;i<v[Q].size();++i) out[v[Q][i].id]=ask(Q)-ask(v[Q][i].l-1);
    }
    for(int i=1;i<=q;++i) cout<<out[i]<<endl;
}