CodeForces 527C. Glass Carving （SBT，线段树，set，最长连续0）

原题地址：http://codeforces.com/problemset/problem/527/C

Examples

input

H

V

V

V

output

input

H

V

V

H

V

output

题意是给定一个矩形，不停地纵向或横向切割，问每次切割后，最大的矩形面积是多少。

最大矩形面积=最长的长*最宽的宽
这题，长宽都是10^5，所以，用0 1序列表示每个点是否被切割，然后，
最长的长就是长的最长连续0的数量+1
最长的宽就是宽的最长连续0的数量+1
于是用线段树维护最长连续零

问题转换成：
目标信息：区间最长连续零的个数
点信息：0 或 1
由于目标信息不符合区间加法，所以要扩充目标信息。

转换后的线段树结构：
区间信息：从左，右开始的最长连续零，本区间是否全零，本区间最长连续零。
点信息：0 或 1
然后还是那2个问题：

1.区间加法：
这里，一个区间的最长连续零，需要考虑3部分：
-（1）：左子区间最长连续零
-（2）：右子区间最长连续零
-（3）：左右子区间拼起来，而在中间生成的连续零（可能长于两个子区间的最长连续零）
而中间拼起来的部分长度，其实是左区间从右开始的最长连续零+右区间从左开始的最长连续零。
所以每个节点需要多两个量，来存从左右开始的最长连续零。
然而，左开始的最长连续零分两种情况，
--（1）：左区间不是全零，那么等于左区间的左最长连续零
--（2）：左区间全零，那么等于左区间0的个数加上右区间的左最长连续零
于是，需要知道左区间是否全零，于是再多加一个变量。
最终，通过维护4个值，达到了维护区间最长连续零的效果。

2.点信息->区间信息：
如果是0，那么最长连续零=左最长连续零=右最长连续零=1 ，全零=true。
如果是1，那么最长连续零=左最长连续零=右最长连续零=0，全零=false。

至于修改和查询，有了区间加法之后，机械地写一下就好了。
由于这里其实只有对整个区间的查询，所以查询函数是不用写的，直接找根的统计信息就行了。

递归线段树：

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <queue>

 #include <set>

 #include <math.h>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int maxn=2e5+;

 using namespace std;

 struct SegTree{

     int ls;//左最长连续零

     int rs;//右最长连续零

     int max0;//最长连续零

     bool is_all0;//是否全为零

 }tree[][maxn<<];

 void PushUp(int rt,int flag)//区间加法

 {

     SegTree &root=tree[flag][rt];

     SegTree &lc=tree[flag][rt<<];

     SegTree &rc=tree[flag][rt<<|];

     root.ls=lc.ls+(lc.is_all0?rc.ls:);

     root.rs=rc.rs+(rc.is_all0?lc.rs:);

     root.max0=max(lc.rs+rc.ls,max(lc.max0,rc.max0));

     root.is_all0=lc.is_all0&&rc.is_all0;

 }

 void Build(int l,int r,int rt,int flag)//建树

 {

     if(l==r)

     {

         tree[flag][rt].ls=tree[flag][rt].rs=tree[flag][rt].max0=;

         tree[flag][rt].is_all0=true;

         return ;

     }

     int m=(l+r)>>;

     Build(l,m,rt<<,flag);

     Build(m+,r,rt<<|,flag);

     PushUp(rt,flag);

 }

 void Update(int l,int r,int rt,int pos,int flag)//更新

 {

     if(l==r)

     {

         tree[flag][rt].ls=tree[flag][rt].rs=tree[flag][rt].max0=;

         tree[flag][rt].is_all0=false;

         return ;

     }

     int m=(l+r)>>;

     if(pos<=m)

         Update(l,m,rt<<,pos,flag);

     else

         Update(m+,r,rt<<|,pos,flag);

     PushUp(rt,flag);

 }

 int main()

 {

     int W,H,q,t;

     char c[];

     scanf("%d %d %d",&W,&H,&q);

     Build(,W-,,);

     Build(,H-,,);

     while(q--)

     {

         scanf("%s %d",&c,&t);

         if(c[]=='V')

             Update(,W-,,t,);

         else if(c[]=='H')

             Update(,H-,,t,);

         printf("%lld\n",LL(tree[][].max0+)*(tree[][].max0+));//相乘可能整数溢出，记得类型装换

     }

     return ;

 }

以下是大神写的，原地址：https://blog.csdn.net/zearot/article/details/44759437

多次切割求最大矩形面积：

大致思路，对两条边分别找出被切割出的每一段长度的最大值，相乘就是答案。

有三种实现方法：

一：线段树

用1和0 表示每一条可被切割的线是否被切割，然后用线段树统计最长连续零的个数。

时间复杂度O(n* max( log2(w) , log2(h)))

二：SBT（Size Balanced Tree）

直接按顺序存下被切割之后的每一个小段的长度，每次切割的操作就是把其中的某个数分解成两个数。

比如开始长度为【11】，在3处切割：【3，8】。然后在5处切割：【3，2，6】，在4处切割：【3，1，1，6】。

时间复杂度O(n * log2(n))

三：使用std::set

使用set存下被切割的横坐标，然后求该点的前驱和后继。就可以知道被切割的区间的长度。

然后另有数组存下每个区间长度出现的次数，每次操作维护这个次数。

方法比较：SBT: 202ms 4700KB 线段树：187ms 20400KB std::set 171ms 7888KB

总的来说就是SBT占用空间小，但稍微慢一点（可能实现上还可以改进）

线段树占用空间大，但比SBT快一点（我试过了改成非递归线段树并没有比递归的快多少）

由于SBT的时间复杂度只与n有关，所以可以处理更大的w和h，通用性更强一些，但写起来也复杂一些。

相比之下，使用set由于不需要自己写一个树结构，编程复杂度比较低。

非递归线段树：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #define maxn 200001

 using namespace std;

 int L[maxn<<][];//从左开始连续零个数

 int R[maxn<<][];//从右

 int Max[maxn<<][];//区间最大连续零

 bool Pure[maxn<<][];//是否全零

 int M[];

 void PushUp(int rt,int k){//更新rt节点的四个数据

     Pure[rt][k]=Pure[rt<<][k]&&Pure[rt<<|][k];

     Max[rt][k]=max(R[rt<<][k]+L[rt<<|][k],max(Max[rt<<][k],Max[rt<<|][k]));

     L[rt][k]=Pure[rt<<][k]?L[rt<<][k]+L[rt<<|][k]:L[rt<<][k];

     R[rt][k]=Pure[rt<<|][k]?R[rt<<|][k]+R[rt<<][k]:R[rt<<|][k];

 }

 void Build(int n,int k){//建树，赋初值

     for(int i=;i<M[k];++i) L[M[k]+i][k]=R[M[k]+i][k]=Max[M[k]+i][k]=Pure[M[k]+i][k]=i<n;

     for(int i=M[k]-;i>;--i) PushUp(i,k);

 }

 void Change(int X,int k){//切割，更新

     int s=M[k]+X-;

     Pure[s][k]=Max[s][k]=R[s][k]=L[s][k]=;

     for(s>>=;s;s>>=) PushUp(s,k);

 }

 int main(void)

 {

     int w,h,n;

     while(cin>>w>>h>>n){

         //以下3行，找出非递归线段树的第一个数的位置。

         M[]=M[]=;

         while(M[]<h-) M[]<<=;

         while(M[]<w-) M[]<<=;

         //建树

         Build(h-,);Build(w-,);

         for(int i=;i<n;++i){

             //读取数据

             char x;int v;

             scanf(" %c%d",&x,&v);

             //切割

             x=='H'?Change(v,):Change(v,);

             //输出

             printf("%I64d\n",(long long)(Max[][]+)*(Max[][]+));

         }

     }

     return ;

 }

SBT：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #define maxn 200007

 using namespace std;

 int L[maxn],R[maxn],Size[maxn];

 int Max[maxn],Sum[maxn],Key[maxn];

 int IP;

 void Init(){//初始化

     L[]=R[]=Size[]=;

     Max[]=Sum[]=Key[]=;

     IP=;

 }

 void PushUp(int rt){//更新节点

     Size[rt]=+Size[L[rt]]+Size[R[rt]];

     Sum[rt]=Key[rt]+Sum[L[rt]]+Sum[R[rt]];

     Max[rt]=max(Key[rt],max(Max[L[rt]],Max[R[rt]]));

 }

 void zig(int &rt){//左旋

     int t=R[rt];R[rt]=L[t];L[t]=rt;

     PushUp(rt);PushUp(t);rt=t;

 }

 void zag(int &rt){//右旋

     int t=L[rt];L[rt]=R[t];R[t]=rt;

     PushUp(rt);PushUp(t);rt=t;

 }

 void maintain(int &rt){//平衡

     if(Size[L[L[rt]]]>Size[R[rt]]) {zag(rt);maintain(R[rt]);maintain(rt);return;}

     if(Size[R[R[rt]]]>Size[L[rt]]) {zig(rt);maintain(L[rt]);maintain(rt);return;}

     if(Size[R[L[rt]]]>Size[R[rt]]) {zig(L[rt]);zag(rt);maintain(L[rt]);maintain(R[rt]);return;}

     if(Size[L[R[rt]]]>Size[L[rt]]) {zag(R[rt]);zig(rt);maintain(R[rt]);maintain(L[rt]);return;}

 }

 void InsertLeft(int &rt,int X){//在rt这课树的最左端插入，Insert的辅助函数

     if(rt) {

         InsertLeft(L[rt],X);PushUp(rt);maintain(rt);

     }

     else {

         rt=++IP;

         Sum[rt]=Max[rt]=Key[rt]=X;

         Size[rt]=;L[rt]=R[rt]=;

     }

 }

 void Insert(int &rt,int X){//在X处切割

     if(X < Sum[L[rt]]) {Insert(L[rt],X);PushUp(rt);maintain(rt);return;}

     X-=Sum[L[rt]];

     if(X > Key[rt]){Insert(R[rt],X - Key[rt]);PushUp(rt);maintain(rt);return;}

     InsertLeft(R[rt],Key[rt]-X);

     Key[rt]=X;PushUp(rt);

 }

 int w,h,n;

 int main(void)

 {

     while(cin>>w>>h>>n){

         //初始化

         Init();

         int H=,V=;

         InsertLeft(H,h);InsertLeft(V,w);

         for(int i=;i<n;++i){

             //读取

             char x;int v;

             scanf(" %c%d",&x,&v);

             //切割

             x=='H'?Insert(H,v):Insert(V,v);

             //输出

             printf("%I64d\n",(long long)Max[H]*Max[V]);

         }

     }

     return ;

 }

std::set代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <set>

 #define maxn 200001

 using namespace std;

 set<int>::iterator i,j;

 set<int> H,V;

 int Hn[maxn],Vn[maxn];

 void Cut(set<int> &A,int *N,int v){//切割

     A.insert(v);i=j=A.find(v);

     --i,++j,--N[*j-*i];

     ++N[v-*i],++N[*j-v];

 }

 int main(void)

 {

     int w,h,n;

     while(cin>>w>>h>>n){

         memset(Hn,,sizeof(Hn));H.clear();H.insert(h);H.insert();Hn[h]=;

         memset(Vn,,sizeof(Vn));V.clear();V.insert(w);V.insert();Vn[w]=;

         int MaxH=h,MaxW=w; //MaxH表示H的最大值

         for(int i=;i<n;++i){

             //读取数据

             char x;int v;

             scanf(" %c%d",&x,&v);

             //切割

             x=='H'?Cut(H,Hn,v):Cut(V,Vn,v);

             //输出

             while(!Hn[MaxH]) --MaxH;//更新最大值，由于最大值一定不增，所以整个这个操作是O(h)的

             while(!Vn[MaxW]) --MaxW;//同上

             printf("%I64d\n",(long long)MaxH*MaxW);

         }

     }

     return ;

 }

巴特西

CodeForces 527C. Glass Carving （SBT，线段树，set，最长连续0）

Examples

input

output

input

output

最新文章

热门文章