BZOJ 3995 Sdoi2015 道路修建 線段樹

BZOJ 3995 Sdoi2015 道路修建 線段樹

題目大意：給定一個2*n的網格圖，多次改變某條邊的權值或詢問y坐標在[l,r]中的2*(r-l+1)個點的MST

這真是一道好題= =

我們用線段樹維護每個區間內的MST

然後考慮合並

合並兩個區間 我們會加入兩條邊 這樣一定會形成一個環 切掉環上最大邊 這題沒了

然後就是一坨亂七八糟的細節討論= =

首先最大邊一定在圖中的彩色部分內 綠色部分可以O(1)求 我們需要維護的是紅色和藍色部分

然後如果切掉的邊是橫邊或者切掉的豎邊不是區間唯一的豎邊(如圖中藍色豎邊) 那麼紅框和藍框直接用左右區間的即可

但是如果切掉了區間唯一的豎邊(圖中紅色豎邊)，那麼就有些麻煩了

首先我們需要知道切掉的是不是豎邊 因此我們要記錄每個區間的MST上最左側和最右側的豎邊的權值

然後還要記錄區間內MST上豎邊的數量

然後如果切掉了紅色的豎邊 那麼左側的框被更新成了【左區間所有橫邊】【綠色邊】【藍色邊】的最大值

因此還要記錄區間所有橫邊的最大長度

然後更新時候討論一下……就沒了……

P.S.終於把SDOI2015的六道題都搞完了 居然搞了整整一下午+一天 我是不是可以退役了QAQ

#include 
#include 
#include 
#include 
#define M 60600
using namespace std;
int n,m;
int a[M][2],b[M];
struct abcd{
	int l,r;//區間左右端點
	int sum;//MST的權值
	int max_val;//區間內所有橫邊的最大邊權
	int cnt;//MST上豎邊的個數
	int l_val,r_val;//左/右側第一個豎邊的權值
	int l_max,r_max;//左/右側第一個豎邊以左/右的所有樹邊的最大權值
	abcd() {}
	abcd(int pos)
	{
		int x=b[pos];
		l=r=pos;
		sum=x;
		max_val=0;
		cnt=1;
		l_val=r_val=x;
		l_max=r_max=x;
	}
	friend abcd operator + (const abcd &x,const abcd &y)
	{
		abcd re;
		re.l=x.l;
		re.r=y.r;
		re.max_val=max(max(a[x.r][0],a[x.r][1]),max(x.max_val,y.max_val));
		int max_val=max(max(a[x.r][0],a[x.r][1]),max(x.r_max,y.l_max));//環上最大邊
		re.sum=x.sum+y.sum+a[x.r][0]+a[x.r][1]-max_val;
		re.cnt=x.cnt+y.cnt;
		re.l_val=x.l_val;
		re.r_val=y.r_val;
		re.l_max=x.l_max;
		re.r_max=y.r_max;
		if( x.r_val==max_val )
		{
			re.cnt--;
			if(x.cnt==1)
			{
				re.l_val=y.l_val;
				re.l_max=max(max(x.max_val,y.l_max),max(a[x.r][0],a[x.r][1]));
			}
		}
		else if( y.l_val==max_val )
		{
			re.cnt--;
			if(y.cnt==1)
			{
				re.r_val=x.r_val;
				re.r_max=max(max(y.max_val,x.r_max),max(a[x.r][0],a[x.r][1]));
			}
		}
		return re;
	}
};
struct Segtree{
	Segtree *ls,*rs;
	abcd status;
	void* operator new (size_t)
	{
		static Segtree mempool[M<<1],*C=mempool;
		return C++;
	}
	void Build_Tree(int x,int y)
	{
		int mid=x+y>>1;
		if(x==y)
		{
			status=abcd(mid);
			return ;
		}
		(ls=new Segtree)->Build_Tree(x,mid);
		(rs=new Segtree)->Build_Tree(mid+1,y);
		status=ls->status+rs->status;
	}
	void Refresh1(int x,int y,int pos)
	{
		int mid=x+y>>1;
		if(x==y)
		{
			status=abcd(mid);
			return ;
		}
		if(pos<=mid)
			ls->Refresh1(x,mid,pos);
		else
			rs->Refresh1(mid+1,y,pos);
		status=ls->status+rs->status;
	}
	void Refresh2(int x,int y,int pos)
	{
		int mid=x+y>>1;
		if(mid==pos)
		{
			status=ls->status+rs->status;
			return ;
		}
		if(pos<=mid)
			ls->Refresh2(x,mid,pos);
		else
			rs->Refresh2(mid+1,y,pos);
		status=ls->status+rs->status;
	}
	abcd Query(int x,int y,int l,int r)
	{
		int mid=x+y>>1;
		if(x==l&&y==r)
			return status;
		if(r<=mid)
			return ls->Query(x,mid,l,r);
		if(l>mid)
			return rs->Query(mid+1,y,l,r);
		return ls->Query(x,mid,l,mid) + rs->Query(mid+1,y,mid+1,r) ;
	}
}*root=new Segtree;
void Modify(int x0,int y0,int x1,int y1,int z)
{
	if(y0==y1)//修改了一條豎邊
	{
		b[y0]=z;
		root->Refresh1(1,n,y0);
	}
	else//修改了一條橫邊
	{
		if(y0>y1) swap(y0,y1);
		a[y0][x0-1]=z;
		root->Refresh2(1,n,y0);
	}
}
int main()
{
	int i,x0,y0,x1,y1,x,y,z;
	char p[10];
	cin>>n>>m;
	for(i=1;iBuild_Tree(1,n);
	for(i=1;i<=m;i++)
	{
		scanf("%s",p);
		if(p[0]=='C')
		{
			scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&z);
			Modify(x0,y0,x1,y1,z);
		}
		else
		{
			scanf("%d%d",&x,&y);
			abcd ans=root->Query(1,n,x,y);
			printf("%d\n",ans.sum);
		}
	}
	return 0;
}