二維$MLE$線段樹

關于二維線段樹，ta死了

先來看看兩種二維線段樹的打法

1.四叉樹

 然而ta死了，ta是$\Theta (n)$的,加上線段樹的常數,$T$飛穩

2.線段樹套線段樹

我盡量畫出來...

 圖中每個方塊是一棵線段樹

畫完長這樣(你們湊合看吧,作者已經半卒了)

 局部放大圖

 現在每個圓點代表真正的一個點

接下來的講解以今天的題為例(題面就不放了)

先說區間修改

 假設我們現在要給圖中的$9$個綠點賦值(仔細找,相信你能找到

按照一維線段樹的做法,我們會修改這六個綠點

但這是$\Theta (NlogN)$的,會$T$

我們可以是這對藍點進行操作

然后我們就可以只修改圖中的四個綠點了

代碼:

struct Tree
{
	struct tree
	{
		int tag;
	}t[maxn<<2];
	void down(int k)
	{
		int tmp=t[k].tag;
		t[l(k)].tag=max(t[l(k)].tag,tmp);
		t[r(k)].tag=max(t[r(k)].tag,tmp);
	}
	void change(int k,int l,int r,int L,int R,int v)
	{
		if(L<=l&&r<=R){t[k].tag=v;return;}
		down(k);int mid=(l+r)>>1;
		if(L<=mid)	change(l(k),l,mid,L,R,v);
		if(mid<R)	change(r(k),mid+1,r,L,R,v);
	}
}T[maxn<<2];

void change(int k,int l,int r,int L,int R,int ll,int rr,int v)
{
	if(L<=l&&r<=R){T[k].change(1,1,maxn-1,ll,rr,v);return;}
	int mid=(l+r)>>1;
	if(L<=mid)	change(l(k),l,mid,L,R,ll,rr,v);
	if(mid<R)	change(r(k),mid+1,r,L,R,ll,rr,v);
}

接下來是單點查詢

 我們要查圖中的綠點

 但是我們并不能只查詢這一個點,因為下圖中三個黃色的方塊里都有關于這個綠點的信息

 所以我們只要一邊向下走一邊查詢取$max/min$就可以了

代碼:

int query(int k,int l,int r,int p)
{
	if(l==r)	return t[k].tag;
	down(k);int mid=(l+r)>>1;
	if(p<=mid)	return query(l(k),l,mid,p);
	else		return query(r(k),mid+1,r,p);
}

int query(int k,int l,int r,int p1,int p2)
{
	if(l==r){return T[k].query(1,1,maxn-1,p2);}
	int ans=T[k].query(1,1,maxn-1,p2),mid=(l+r)>>1;
	if(p1<=mid)	return max(ans,query(l(k),l,mid,p1,p2));
	else		return max(ans,query(r(k),mid+1,r,p1,p2));
}

以及完整代碼:

struct Tree
{
	struct tree
	{
		int tag;
	}t[maxn<<2];
	void down(int k)
	{
		int tmp=t[k].tag;
		t[l(k)].tag=max(t[l(k)].tag,tmp);
		t[r(k)].tag=max(t[r(k)].tag,tmp);
	}
	void change(int k,int l,int r,int L,int R,int v)
	{
		if(L<=l&&r<=R){t[k].tag=v;return;}
		down(k);int mid=(l+r)>>1;
		if(L<=mid)	change(l(k),l,mid,L,R,v);
		if(mid<R)	change(r(k),mid+1,r,L,R,v);
	}
	int query(int k,int l,int r,int p)
	{
		if(l==r)	return t[k].tag;
		down(k);int mid=(l+r)>>1;
		if(p<=mid)	return query(l(k),l,mid,p);
		else		return query(r(k),mid+1,r,p);
	}
}T[maxn<<2];
void change(int k,int l,int r,int L,int R,int ll,int rr,int v)
{
	if(L<=l&&r<=R){T[k].change(1,1,maxn-1,ll,rr,v);return;}
	int mid=(l+r)>>1;
	if(L<=mid)	change(l(k),l,mid,L,R,ll,rr,v);
	if(mid<R)	change(r(k),mid+1,r,L,R,ll,rr,v);
}
int query(int k,int l,int r,int p1,int p2)
{
	if(l==r){return T[k].query(1,1,maxn-1,p2);}
	int ans=T[k].query(1,1,maxn-1,p2),mid=(l+r)>>1;
	if(p1<=mid)	return max(ans,query(l(k),l,mid,p1,p2));
	else		return max(ans,query(r(k),mid+1,r,p1,p2));
}

關于其他操作,有空在更(基本沒空了