正题

题目链接:https://www.luogu.com.cn/problem/CF444C

题目大意

\(n\)个物品第\(i\)个颜色为\(i\)，权值为\(0\)。要求支持\(m\)次操作

给出\(l,r,x\)，对于所有区间\([l,r]\)中的物品，如果颜色为\(c\)，那么该位置的权值加上\(|c-x|\)，并且颜色改为\(x\)
询问区间权值和

解题思路

区间染色有一种简单的做法并且可以求出每个被染色的相同颜色段。

用\(set\)维护每个相同的连续颜色段，那么每次修改最多会产生\(3\)个新的颜色端。均摊下来就是\(O(n\log n)\)了。

然后加一个线段树维护权值就好了，总时间复杂度也是\(O(n\log n)\)的

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

#define ll long long

#define lowbit(x) (x&-x)

using namespace std;

const ll N=1e5+10;

struct node{

	ll l,r,w;

	node(ll L=0,ll rr=0,ll ww=0)

	{l=L;r=rr;w=ww;return;}

};

multiset<node> s;

ll n,m;

bool operator<(node x,node y)

{return x.r<y.r;}

struct TreeBinary{

	ll w[N<<2],lazy[N<<2];

	void Downdata(ll x,ll l,ll r){

		if(!lazy[x])return;

		ll mid=(l+r)>>1;

		w[x*2]+=lazy[x]*(mid-l+1);

		w[x*2+1]+=lazy[x]*(r-mid);

		lazy[x*2]+=lazy[x];lazy[x*2+1]+=lazy[x];

		lazy[x]=0;return;

	}

	void Change(ll l,ll r,ll val,ll L=1,ll R=n,ll x=1){

		if(L==l&&R==r){w[x]+=val*(r-l+1);lazy[x]+=val;return;}

		ll mid=(L+R)>>1;Downdata(x,L,R);

		if(r<=mid)Change(l,r,val,L,mid,x*2);

		else if(l>mid)Change(l,r,val,mid+1,R,x*2+1);

		else Change(l,mid,val,L,mid,x*2),Change(mid+1,r,val,mid+1,R,x*2+1);

		w[x]=w[x*2]+w[x*2+1];return;

	}

	ll Ask(ll l,ll r,ll L=1,ll R=n,ll x=1){

		if(L==l&&R==r)return w[x];

		ll mid=(L+R)>>1;Downdata(x,L,R);

		if(r<=mid)return Ask(l,r,L,mid,x*2);

		if(l>mid)return Ask(l,r,mid+1,R,x*2+1);

		return Ask(l,mid,L,mid,x*2)+Ask(mid+1,r,mid+1,R,x*2+1);

	}

}T;

signed main()

{

	multiset<node>::iterator it;

	scanf("%lld%lld",&n,&m);

	for(ll i=1;i<=n;i++)s.insert(node(i,i,i));

	while(m--){

		ll op,l,r,x;

		scanf("%lld%lld%lld",&op,&l,&r);

		if(op==1){

			scanf("%lld",&x);

			while(1){

				it=s.lower_bound(node(l,l,l));

				node tmp=*it;

				s.erase(it);

				if(tmp.l<l&&tmp.r>r)

					T.Change(l,r,abs(x-tmp.w));

				if(tmp.l<l){

					s.insert(node(tmp.l,l-1,tmp.w));

					if(tmp.r<=r)T.Change(l,tmp.r,abs(x-tmp.w));

				}

				if(tmp.r>r){

					s.insert(node(r+1,tmp.r,tmp.w));

					if(tmp.l>=l)T.Change(tmp.l,r,abs(x-tmp.w));

					break;

				}

				if(tmp.l>=l&&tmp.r<=r)T.Change(tmp.l,tmp.r,abs(x-tmp.w));

				if(tmp.r==r)break;

			}

			s.insert(node(l,r,x));

		}

		else printf("%lld\n",T.Ask(l,r));

	}

	return 0;

}

巴特西

CF444C-DZY Loves Colors【线段树,set】

正题

题目大意

解题思路

code

最新文章

热门文章