首页 > 代码库 > 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<iostream>
#include<cstdio>
#include<cstring>
#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;
}
Vijos P1881 闪烁的繁星