有三个维度,序列维,操作维,询问维。
尝试扫描线,枚举一下扫哪个维能做。
或者考虑序列维上有颜色段均摊的性质。
这样不难想到在操作维上从小到大扫描线,或者说对询问维的 \(r\) 作扫描线,用 set
维护序列维上的连续段。
现在将询问 \((l,r)\) 挂在了 \(r\) 上,扫描线扫到 \(r\) 时,要询问 “只看 \(\geq l\) 的操作后所有数的总和”
换而言之,只需要询问插入时间 \(\geq l\) 的颜色段的总和。
于是在 set
维护连续颜色段的时候,用树状数组在时间维上维护一个后缀和即可。
时间复杂度 \(\mathcal{O}((n+q)\log n)\)
#include<cstdio> #include<vector> #include<queue> #include<cstring> #include<set> #include<iostream> #include<algorithm> #include<ctime> #include<random> #include<assert.h> #define pb emplace_back #define mp make_pair #define fi first #define se second #define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'; #define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int>pii; typedef pair<ll,int>pli; typedef pair<ll,ll>pll; typedef pair<int,ll>pil; typedef vector<int>vi; typedef vector<ll>vll; typedef vector<pii>vpii; typedef vector<pil>vpil; template<typename T>T cmax(T &x, T y){return x=x>y?x:y;} template<typename T>T cmin(T &x, T y){return x=x<y?x:y;} #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) char buf[1<<21],*p1=buf,*p2=buf; template<typename T> T &read(T &r){ r=0;bool w=0;char ch=getchar(); while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar(); while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar(); return r=w?-r:r; } template<typename T1,typename... T2> void read(T1 &x,T2& ...y){read(x);read(y...);} const int N=500010; int n,m,q; int l[N],r[N],v[N]; ll ans[N],tree[N]; vpii vec[N]; inline int lowbit(int x){return x&(-x);} inline void modify(int x,ll v){for(;x;x-=lowbit(x))tree[x]+=v;} inline ll query(int x){ll s=0;for(;x<=m;x+=lowbit(x))s+=tree[x];return s;} struct Node{ int l,r,c,t; bool operator<(const Node &x)const{return l<x.l;} }; set<Node>st; auto split(int pos){ auto it=st.lower_bound({pos,pos,0,0}); if(it!=st.end()&&(*it).l==pos)return it; --it; int L=it->l,R=it->r,C=it->c,T=it->t; st.erase(it); st.insert({L,pos-1,C,T}); return st.insert({pos,R,C,T}).first; } void assign(int l,int r,int c,int t){ auto itr=split(r+1),itl=split(l); auto it=split(l); for(;it!=itr;++it)modify(it->t,-1ll*((it->r)-(it->l)+1)*(it->c)); st.erase(itl,itr); st.insert({l,r,c,t}); modify(t,1ll*(r-l+1)*c); } signed main(){ read(m,n,q); for(int i=1;i<=m;i++)read(l[i],r[i],v[i]); for(int i=1;i<=q;i++){ int x,y;read(x,y);vec[y].pb(mp(x,i)); } st.insert({1,n,0,0}); for(int i=1;i<=m;i++){ assign(l[i],r[i],v[i],i); for(auto o:vec[i]) ans[o.se]=query(o.fi); } for(int i=1;i<=q;i++)cout << ans[i] << '\n'; return 0; }