Description

There is a rectangle in the xy-plane, with its lower left corner at (0,0) and its upper right corner at (W,H). Each of its sides is parallel to the x-axis or y-axis. Initially, the whole region within the rectangle is painted white.

Snuke plotted N points into the rectangle. The coordinate of the i-th (1≤i≤N) point was (x_i,y_i).

Then, for each 1≤i≤N, he will paint one of the following four regions black:

• the region satisfying x<x_i within the rectangle
• the region satisfying x>x_i within the rectangle
• the region satisfying y<y_i within the rectangle
• the region satisfying y>y_i within the rectangle

Find the longest possible perimeter of the white region of a rectangular shape within the rectangle after he finishes painting.

 

题意：给定一个$W\times H$的二维平面，初始均为白色，有$n$个关键点$(x_{i},y_{i})$，对于每一个关键点选择一个方向，并将该方向上的所有网格涂成黑色。易得操作后白色部分一定是一个矩形，请最大化矩形周长。

分析：

观察可以得到一个性质，答案矩形一定会经过直线$x=\frac{W}{2}$或$y=\frac{H}{2}$。两种情况可以用相同的方式处理出答案。

将坐标离散化后，枚举矩形的上下边界，可以直接计算出矩形的左右边界。考虑用线段树进行优化。左右各开一个单调栈，在维护单调栈时在线段树上进行区间加减即可。（其实画图比较方便理解。

 

1 #include
       
         2 #include
        
           3 #include
         
           4 #define LL long long 5 #define lc(x) x<<1 6 #define rc(x) x<<1|1 7 using namespace std; 8 const int N=3e5+5; 9 int w,h,n,ans,L,R;10 int mx[N*4],tag[N*4];11 struct node{
     int x,y;node(int _x=0,int _y=0):x(_x),y(_y){};}p[N],a[N],b[N]; 12 int read()13 {14     int x=0,f=1;char c=getchar();15     while(c<'0'||c>'9'){
     if(c=='-')f=-1;c=getchar();}16     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}17     return x*f;18 }19 void modify(int x,int l,int r,int v)20 {21     if(L<=l&&r<=R){mx[x]+=v;tag[x]+=v;return;}22     int mid=(l+r)>>1;23     if(L<=mid)modify(lc(x),l,mid,v);24     if(R>mid)modify(rc(x),mid+1,r,v);25     mx[x]=max(mx[lc(x)],mx[rc(x)])+tag[x];26 }27 bool cmp(node a,node b){
     return a.x
          
           
            p[i].y)50             {51                 L=b[r].x;R=nxt;nxt=b[r].x-1;52                 modify(1,1,n,p[i].y-b[r].y);r--;53             }54             if(nxt!=i-1)b[++r]=node(nxt+1,p[i].y);55         }56         a[++l]=node(i,0);b[++r]=node(i,h);57         L=i;R=i;modify(1,1,n,h-p[i].x);58         ans=max(ans,mx[1]+p[i+1].x);59     }60 }61 int main()62 {63     w=read();h=read();n=read();64     for(int i=1;i<=n;i++)p[i].x=read(),p[i].y=read();65     p[++n]=node(0,0);p[++n]=node(w,h);work();66     for(int i=1;i<=n;i++)swap(p[i].x,p[i].y);67     swap(w,h);work();68     printf("%d",ans*2);69     return 0;70 }