[線段樹][LayzFlag]444C - DZY Loves Colors

Sylveon

原題：http://codeforces.com/problemset/problem/444/C

做線段樹時，維護Flag : color，如果 [tex]color = -1[/tex]代表該區間所涵蓋的所有點為同一顏色，還算簡單，稍微維護一下標記就行了，各個操作就能以對數時間完成。
要開long long XD

[C++] 純文本查看 復制代碼

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct node{
	long long sum;
	long long size;
	long long color;
	long long etd;
	long long s()const{
		return sum+size*etd; 
	}
};
node d[400000] = {0,0,0,0};
int N,M;
#define LI(X) ((X)*2+1)
#define RI(X) ((X)*2+2)
#define rmq 1,N,0
void down(int I)
{
	if(d[I].color==-1)return ;
	if(d[I].size == 1){
		d[I].sum+=d[I].etd;
		d[I].etd = 0;
	}
	d[I].sum = d[I].s();
	d[LI(I)].etd+=d[I].etd;
	d[RI(I)].etd+=d[I].etd;
	d[I].etd = 0;
	d[LI(I)].color = d[I].color;
	d[RI(I)].color = d[I].color;
}
node merge(node a,node b)
{
	node c;
	c.size = a.size + b.size ;
	c.sum  = a.s()  + b.s();
	c.etd  = 0;
	c.color= (a.color==b.color)?a.color:-1;
	return c;
}
void update(int l,int r,int c,bool init,int L,int R,int I)
{
	
	if(l==L&&R==r&&d[I].color!=-1||l==L&&R==r&&l==r)
	{
		int add = abs( d[I].color - c );
		if(init){
			d[I].sum=d[I].etd=0;
		}
		else{
			d[I].etd+=add;
		}
		d[I].color=c;
		d[I].size =R-L+1;
		return ;
	}
	down(I);
	int M=(L+R)/2;
	if( r<=M ) 		update(l,r,c,init,L  ,M,LI(I));
	else if( M< l ) update(l,r,c,init,M+1,R,RI(I));
	else { 	update(l  ,M,c,init,L  ,M,LI(I)); 
			update(M+1,r,c,init,M+1,R,RI(I)); 
	}
	d[I] = merge(d[LI(I)],d[RI(I)]);
}

node query(int l,int r,int L,int R,int I)
{
	if(l==L&&r==R)return d[I];
	down(I);
	int M=(L+R)/2;
	if( r<=M )return query(l,r,L  ,M,LI(I));
	if( M< l )return query(l,r,M+1,R,RI(I));
	return merge(	query(l  ,M,L  ,M,LI(I)) ,  
					query(M+1,r,M+1,R,RI(I)) );
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>M;
	int a,b,c,d;
	for(int i=1;i<=N;++i)
		update(i,i,i,true,rmq);
	while(M--)
	{
		cin>>a;
		if(a==1)
		{
			cin>>b>>c>>d;
			update(b,c,d,false,rmq);
		}
		else //a==2
		{
			cin>>b>>c;
			node tmp = query(b,c,rmq);
			cout<<tmp.s()<<'\n';
		}
	}
}