[Ynoi Easy Round 2021] TEST_152(颜色段数均摊+扫描线)

题目传送门

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;
}