ZJT's Blog

大変に気分がいい~

集训队作业之ARC063-F

2017-12-18 2:102017-12-18 2:10
集训队作业AtCoder分治单调队列

传送门

问题可以转化成选一个周长最长的矩形使其内部不包含任何点。

首先答案有一个性质就是一定穿过横竖两条中线之一。因为如果两条都不穿过,即缩整个矩形的四分之一里,是没有选$\max(H,W)$再加一条长度为1的边组成的矩形优的。我们先只考虑穿过竖中线的情况,横中线的情况可以把所有东西旋转九十度后转化成竖中线。

在穿过竖中线的同时,我们再对纵坐标分治,每次分治到纵坐标在$[y_l,y_r]$的区间时,我们选最中间的点的纵坐标$y_m$,先递归算出纵坐标在$[y_l,y_m]$或$[y_m,y_r]$中的答案,剩下的就只用考虑同时穿过$x=x_m=W/2$和$y=y_m$两条直线的矩形了。

我们从右往左枚举矩形左边那条边的横坐标$x_l$,并对每个$x_l$处理出所有横坐标在$[x_l,x_m]$且纵坐标在$[y_l,y_m]$中的点的最大的纵坐标$y_1$,以及所有横坐标在$[x_l,x_m]$且纵坐标在$[y_m,y_r]$中的点的最小的纵坐标$y_2$。最终的矩形底边一定在$y_1$上方,顶边一定在$y_2$下方。同样,我们也枚举右边的横坐标$x_r$,并处理出意义相同的$y_1$和$y_2$。这样,两个$x_l$和$x_r$围出来的矩形的底边就是两个$y_1$的较大值,顶边就是$y_2$的较小值。考虑对每个$x_l$找出最优的$x_r$,我们发现可以把右边的所有$x_r$分成三段,第一段的$[y_1,y_2]$完全包含$x_l$的$[y_1,y_2]$;第二段不完全包含,但不被$x_l$的$[y_1,y_2]$包含;第三段则完全被$x_l$的$[y_1,y_2]$包含。第一段的答案很好处理,直接取最靠右的$x_r$就行了,后两段也能通过分别维护单调队列来进行统计(其中第二段还要分为上下两种情况)。这样,在把横坐标排好序之后,我们可以线性地统计出同时穿过$x_m$和$y_m$的答案。排序也可以用归并排序来做到线性,这样总复杂度就是$O(n\log n)$了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#define MAXN 300010
#define y1 zjtsb_y1
using namespace std;

int w,h,n,w0;
pair<int,int> a[MAXN];
deque<int> S1,S2,S3;

bool cmp2(pair<int,int> x,pair<int,int> y){
    return x.second<y.second;
}

int gao(int l,int r,int y0,int y1){
    if(l==r) return max(max(w+a[l].second-y0,w+y1-a[l].second),max(y1-y0+a[l].first,y1-y0+w-a[l].first));
    int mid=(l+r)>>1;
    int ymid=a[mid].second;
    int res1=gao(l,mid,y0,a[mid].second);
    int res2=gao(mid+1,r,a[mid+1].second,y1);
    sort(a+l,a+r+1);
    int mid2=l-1;
    while(mid2<r && a[mid2+1].first<=w0) mid2++;
    static int s1[MAXN][3],s2[MAXN][3];
    int ls1=0,ls2=0;
    int t0=y0,t1=y1;
    for(int i=mid2;i>=l;i--){
        s1[++ls1][0]=t0;
        s1[ls1][1]=t1;
        s1[ls1][2]=a[i].first;
        if(a[i].second<=ymid && a[i].second>t0) t0=a[i].second;
        if(a[i].second>ymid && a[i].second<t1) t1=a[i].second;
    }
    s1[++ls1][0]=t0;
    s1[ls1][1]=t1;
    s1[ls1][2]=0;
    t0=y0; t1=y1;
    for(int i=mid2+1;i<=r;i++){
        s2[++ls2][0]=t0;
        s2[ls2][1]=t1;
        s2[ls2][2]=a[i].first;
        if(a[i].second<=ymid && a[i].second>t0) t0=a[i].second;
        if(a[i].second>ymid && a[i].second<t1) t1=a[i].second;
    }
    s2[++ls2][0]=t0;
    s2[ls2][1]=t1;
    s2[ls2][2]=w;
    S1.clear();
    S2.clear();
    S3.clear();
    int now1=1,now2=1;
    for(int i=1;i<=ls2;i++){
        while(!S3.empty() && s2[S3.front()][1]-s2[S3.front()][0]+s2[S3.front()][2]<s2[i][1]-s2[i][0]+s2[i][2])
            S3.pop_front();
        S3.push_front(i);
    }
    int res=0;
    for(int i=1;i<=ls1;i++){
        while(now1<=ls2 && s2[now1][0]<=s1[i][0]){
            while(!S1.empty() && s2[S1.front()][1]+s2[S1.front()][2]<s2[now1][1]+s2[now1][2])
                S1.pop_front();
            S1.push_front(now1++);
        }
        while(now2<=ls2 && s2[now2][1]>=s1[i][1]){
            while(!S2.empty() && s2[S2.front()][2]-s2[S2.front()][0]<s2[now2][2]-s2[now2][0])
                S2.pop_front();
            S2.push_front(now2++);
        }
        while(!S1.empty() && s2[S1.back()][1]>=s1[i][1]) S1.pop_back();
        while(!S2.empty() && s2[S2.back()][0]<=s1[i][0]) S2.pop_back();
        while(!S3.empty() && (s2[S3.back()][0]<=s1[i][0] || s2[S3.back()][1]>=s1[i][1])) S3.pop_back();
        res=max(res,s1[i][1]-s1[i][0]+s2[min(now1-1,now2-1)][2]-s1[i][2]);
        if(!S1.empty()) res=max(res,s2[S1.back()][1]-s1[i][0]+s2[S1.back()][2]-s1[i][2]);
        if(!S2.empty()) res=max(res,s1[i][1]-s2[S2.back()][0]+s2[S2.back()][2]-s1[i][2]);
        if(!S3.empty()) res=max(res,s2[S3.back()][1]-s2[S3.back()][0]+s2[S3.back()][2]-s1[i][2]);
    }
    res=max(res,max(res1,res2));
    return res;
}

int solve(){
    w0=w/2;
    sort(a+1,a+n+1,cmp2);
    return gao(1,n,0,h);
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d%d",&w,&h,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
    int ans1=solve()*2;
    swap(w,h);
    for(int i=1;i<=n;i++) swap(a[i].first,a[i].second);
    int ans2=solve()*2;
    printf("%d\n",max(ans1,ans2));
    return 0;
}

查看详细内容

集训队作业之ARC066-F

2017-12-13 22:282017-12-13 22:28
集训队作业AtCoder分治DP斜率优化

传送门

这题好神啊qwq

考虑没有询问的情况,显然是个斜率优化DP,拿个单调栈维护转移。这里,我们先预处理出前缀和后缀的DP值,分别记为$f_1[i]$和$f_2[i]$,以后要用。

假设现在第$x$个位置的值发生了更改,我们根据最终最优解里面这个位置是否被选取来讨论。如果这个位置没有被选,那答案就是$f_1[x-1]+f_2[x+1]$。否则,我们可以预处理出必选第$x$个位置时的最大得分,记为$g[x]$,则答案为$g[x]+v_0-v_{now}$,其中$v_0$表示第$x$个位置原来的值,$v_{now}$表示更改后的值。

现在问题变成了如何预处理出$g[x]$。考虑一个包含$x$的区间$[l,r]$,我们可以用$f_1[l-1]+f_2[r+1]+(r-l+1)(r-l+2)/2-(s[r]-s[l+1])$来更新$g[x]$(其中$s[x]$表示原数组的前缀和),$g[x]$的值为所有这样的区间的最大值。这个过程可以分治进行,对于每个分治区间,我们处理经过区间中点的所有$[l,r]$。首先我们把左半区间的点都加进单调栈中,然后再用跟之前DP一样的方法,依次询问以右半区间中的每个点作为区间右端点时,最大的DP值是多少。这样就可以完成对右半区间的所有$g[x]$的更新,左半区间也一样,反过来就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 300010
#define LL long long
using namespace std;

int n,m;
LL a[MAXN],s1[MAXN],s2[MAXN];
int pre[MAXN];
LL f1[MAXN],f2[MAXN];
LL ans[MAXN],temp[MAXN];

namespace Convex{
    LL xp[MAXN],yp[MAXN];
    int q[MAXN],head,tail;

    void init(){
        head=0;
        tail=-1;
    }

    void addPoint(int id,LL x,LL y){
        xp[id]=x;
        yp[id]=y;
        while(head<tail && (yp[q[tail]]-yp[q[tail-1]])*(xp[id]-xp[q[tail]]) 
                                                    <=
                           (yp[id]-yp[q[tail]])*(xp[q[tail]]-xp[q[tail-1]])) tail--;
        q[++tail]=id;
    }

    int query(int i){
        while(head<tail && (yp[q[tail]]-yp[q[tail-1]])<=(xp[q[tail]]-xp[q[tail-1]])*i) tail--;
        return q[tail];
    }
}

void init(){
    for(int i=1;i<=n;i++) s1[i]=a[i]+s1[i-1];
    for(int i=1;i<=n;i++) s2[i]=a[n-i+1]+s2[i-1];
    Convex::init();
    Convex::addPoint(0,0,0);
    for(int i=1;i<=n;i++){
        int j=Convex::query(i);
        f1[i]=max(f1[i-1],f1[j]+(LL)(i-j)*(i-j+1)/2-(s1[i]-s1[j]));
        pre[i]=j;
        if(f1[i]==f1[i-1]) pre[i]=i;
        Convex::addPoint(i,i,f1[i]+((LL)i*i-i)/2+s1[i]);
    }
    Convex::init();
    Convex::addPoint(0,0,0);
    for(int i=1;i<=n;i++){
        int j=Convex::query(i);
        f2[i]=max(f2[i-1],f2[j]+(LL)(i-j)*(i-j+1)/2-(s2[i]-s2[j]));
        Convex::addPoint(i,i,f2[i]+((LL)i*i-i)/2+s2[i]);
    }
    for(int i=1;i<=n;i++) if(i<n-i+1) swap(f2[i],f2[n-i+1]);
    for(int i=1;i<=n;i++) ans[i]=-(1LL<<60);
}

void gao(int l,int r){
    if(l==r){
        ans[l]=max(ans[l],f1[l-1]+f2[l+1]+1-a[l]);
        return;
    }
    int mid=(l+r)>>1;
    Convex::init();
    for(int i=l-1;i<mid;i++)
        Convex::addPoint(i,i,f1[i]+((LL)i*i-i)/2+s1[i]);
    for(int i=mid+1;i<=r;i++){
        int j=Convex::query(i);
        temp[i]=f2[i+1]+f1[j]+(LL)(i-j)*(i-j+1)/2-(s1[i]-s1[j]);
    }
    LL tmax=-(1LL<<60);
    for(int i=r;i>mid;i--){
        if(temp[i]>tmax) tmax=temp[i];
        if(tmax>ans[i]) ans[i]=tmax;
    }
    Convex::init();
    for(int i=r+1;i>mid+1;i--){
        int i2=r+1-i;
        Convex::addPoint(i,i2,f2[i]+((LL)i2*i2-i2)/2+s2[n-i+1]);
    }
    for(int i=mid;i>=l;i--){
        int j=Convex::query(r+1-i);
        temp[i]=f1[i-1]+f2[j]+(LL)(j-i)*(j-i+1)/2-(s1[j-1]-s1[i-1]);
    }
    tmax=-(1LL<<60);
    for(int i=l;i<=mid;i++){
        if(temp[i]>tmax) tmax=temp[i];
        if(tmax>ans[i]) ans[i]=tmax;
    }
    gao(l,mid);
    gao(mid+1,r);
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    init();
    gao(1,n);
    scanf("%d",&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        LL ans1=f1[x-1]+f2[x+1];
        LL ans2=ans[x]-y+a[x];
        printf("%lld\n",max(ans1,ans2));
    }
}

查看详细内容