当前位置: 代码迷 >> 综合 >> 【线段树】[LUOGU Glass Carving] 区间连续最大
  详细解决方案

【线段树】[LUOGU Glass Carving] 区间连续最大

热度:54   发布时间:2024-01-17 00:04:53.0

题目:

题目链接:[LUOGU Glass Carving]
题解:
仔细想一下,纵着切和横着切是互不影响的。这样就是可以用线段树维护横坐标和纵坐标就行,,
所以这个题的关键就是在线段树进行对于连续0的合并(这里不是线段树合并),现在节点的最大值就是左边最大值,右边最大值,以及左边中从右边开始的0+右边中从左边开始的0的和,这样就是在up中解决一下就行了。

代码:

#include<bits/stdc++.h>
#define LL long long
#define lk (k<<1a)
#define rk (k<<1|1)
using namespace std;
inline LL read()
{
    LL s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=201000;
struct hit{
    LL l,r,s;bool f;}t[sea*4][2];//这里的l,r就是左边的最大连续0的个数,右边的最大连续0的个数
LL hi,wi,m,x;
char ch;
void up(LL k,LL l,LL r,LL ff)
{
    t[k][ff].f=t[lk][ff].f&&t[rk][ff].f;//t[k][ff].s=max(t[lk][ff].r+t[rk][ff].l,max(t[lk][ff].s,t[rk][ff].s));//答案就更新为max(左边的最大值,右边的最大值,左边中从右边开始的0+右边中从左边开始的0的和)t[k][ff].l=t[lk][ff].f==1?t[lk][ff].l+t[rk][ff].l:t[lk][ff].l;//(当左边从右数有零时)左边=左儿子的左边+右儿子的左边 //(当左边从右数只有1时)左边=左儿子的左边t[k][ff].r=t[rk][ff].f==1?t[lk][ff].r+t[rk][ff].r:t[rk][ff].r;//右边同理
}
void build(LL k,LL l,LL r,LL ff)
{
    if(l==r){
    t[k][ff].l=t[k][ff].r=t[k][ff].s=1;t[k][ff].f=true;return ;}//刚开始全都赋成1LL mid=(l+r)/2;build(lk,l,mid,ff);build(rk,mid+1,r,ff);up(k,l,r,ff);
}
void alter(LL k,LL l,LL r,LL ff)
{
    if(l==r){
    t[k][ff].l=t[k][ff].r=t[k][ff].s=0;t[k][ff].f=false;return ;}//修改的时候就赋成0即可LL mid=(l+r)/2;if(x<=mid) alter(lk,l,mid,ff); else alter(rk,mid+1,r,ff);up(k,l,r,ff);
}
int main()
{
    wi=read(),hi=read(); m=read();build(1,1,wi-1,0);build(1,1,hi-1,1);for(int i=1;i<=m;i++){
    scanf("%c",&ch); x=read();if(ch=='H') alter(1,1,hi-1,1);else alter(1,1,wi-1,0);printf("%lld\n",(t[1][0].s+1)*(1+t[1][1].s));}	return 0;
}

Continue……