Vijos P1881 閃爍的繁星

Vijos P1881 閃爍的繁星

背景

微雨的山門下
石階濕著——
只有獨立的我
和縷縷的游雲
這也是'同參密藏'麼

描述

清晨, Alice與Bob在石階上玩磚塊.
他們每人都有屬於自己的一堆磚塊.
每人的磚塊都由N列組成且N是奇數.
Alice的第i列磚塊有m[i]個.
而Bob的第i列磚塊有s[i]個.

他們想建造城堡, 兩座一樣的城堡.
每一座城堡都是從正中間一列開始:
1)若往左側看去,數量逐次增加,每一列都比右側的一列多出恰一塊磚.
2)若往右側看去,數量逐次增加,每一列都比左側的一列多出恰一塊磚.

那麼,最左側與最右側的高度當然是一樣的呵.

每一次.
他們可以扔掉一塊磚頭,以減少某一列的磚頭數量.這算是一次操作.
他們可以再找一塊磚頭,以增加某一列的磚頭數量.這又算是一次操作.
但是.
不能從一列去除一塊磚頭,再放置到別的列中.
被扔掉的磚頭,永遠也不能再被使用.

最少,最少,需要多少次操作?

格式

輸入格式

輸入數據第一行: 一個奇數N, 1<=N<=300,000, 表示Alice和Bob分別有多少列磚頭.
第二行有N個整數, m[i], 0<=m[i]<=1,000,000,000,000. 表示Alice每一列的磚頭個數.
第三行有N個整數, s[i], 0<=s[i]<=1,000,000,000,000. 表示Bob每一列的磚頭個數.

輸出格式

輸出只有一行, 要求輸出最少的操作次數.

樣例1

樣例輸入1[復制]

3
1 2 3
3 2 2

樣例輸出1[復制]

3

樣例2

樣例輸入2[復制]

5
2 3 0 1 4
3 3 2 3 1

樣例輸出2[復制]

10

限制

對於40%的數據:N<=1000
對於60%的數據:N<=300,000;0<=s[i],m[i]<=1,000,000
對於100%的數據:N<=300,000;0<=s[i],m[i]<=1,000,000,000,000

提示

樣例1的解釋: Alice對於其第一列新添兩塊磚. Bob對於其第三列新添一塊磚.
那麼,兩人所建城堡每一列的磚頭個數為: 3 2 3 是相同的且滿足要求.

//這是島姐的題，線段樹都放到第一道了 ⊙﹏⊙b汗

這道題的重點在於PushUp()

#include
#include
#include
#define MAXN 200000
using namespace std;
struct tree
{
	int l,r;
	int lx,mx,rx; 
}t[MAXN*4];
int n,q;
int a[MAXN];


void init()
{
	freopen("P1881閃爍的繁星.in","r",stdin);
	freopen("P1881閃爍的繁星.out","w",stdout);
}
void PushUp(int u)
{
	/*
	if(t[u<<1].y!=t[u<<1|1].x)
	{
		t[u].len=t[u<<1].len+t[u<<1|1].len;
		return;
	}
	else
	{
		t[u].len=max(t[u<<1].len,t[u<<1|1].len);
		return; 
	}
	*/
	int len=t[u].r-t[u].l+1;
	int mid=(t[u].l+t[u].r)>>1;
    t[u].lx=t[u<<1].lx;
    t[u].rx=t[u<<1|1].rx;
    if(a[mid]!=a[mid+1])
	{
        t[u].mx=max(max(t[u<<1].mx,t[u<<1|1].mx),t[u<<1].rx+t[u<<1|1].lx);
        if(t[u].lx==len-(len>>1))
			t[u].lx+=t[u<<1|1].lx;
        if(t[u].rx==len>>1)
			t[u].rx+=t[u<<1].rx;
    }
	else 
		t[u].mx=max(t[u<<1].mx,t[u<<1|1].mx);
}

void Build(int u,int l,int r)
{
	t[u].l=l;t[u].r=r;
	if(t[u].l==t[u].r)
	{
		t[u].mx=1;
		t[u].lx=1;
		t[u].rx=1;
		return;
	}
	int mid=(t[u].l+t[u].r)>>1;
	Build(u<<1,l,mid);
	Build(u<<1|1,mid+1,r);
	PushUp(u);
}

void Updata(int u,int x)
{
	if(t[u].l==t[u].r)
	{
		a[x]^=1;
		return;
	}
	int mid=(t[u].l+t[u].r)>>1;
	if(x<=mid)	Updata(u<<1,x);
	if(x>mid)	Updata(u<<1|1,x);
	PushUp(u);
}

int main()
{
	init();
	cin>>n>>q;
	Build(1,1,n);
	int x;
	for(int i=1;i<=q;i++)
	{
		scanf("%d",&x);
		Updata(1,x);
		printf("%d\n",t[1].mx);
	}
	return 0;
}