「JOI 2015 Final」城墙

「JOI 2015 Final」城墙

复杂度默认\(m=n\)

暴力

对于点\((i,j)\)，记录\(ld[i][j]=min(向下延伸的长度，向右延伸的长度)\)，\(rd[i][j]=min(向左延伸的长度，向上延伸的长度)\)（遇到不能放的停止）

那么枚举左上端点\((i,j)\)和右下端点\((i+len-1,j+len-1)\)，能够被计入答案要求\(ld[i][j] \geq len , rd[i+len-1][j+len-1] \geq len,len>=L\)。

复杂度\(o(n^3)\)。

优化

对于每个左上端点\((i,j )\)，是在区间\((i+K-1,j+K-1) (K \in [L,ld[i][j] ])\)，求有多少个点\((i+K,j+K)\),使得\(rd[i+K-1][j+K-1] \geq K\)。

这是一个经典的问题。

可以离线树状数组，或者可持久化线段树。

复杂度\(o(n^2 log(n))\)。

#include<bits/stdc++.h>
#define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)
#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)
#define mem(a,b) memset(a,b,sizeof a )
#define debug(a) cerr<<#a<<' '<<a<<"___"<<endl
using namespace std;
void in(int &r){
    static char c;
    r=0;
    while(c=getchar(),!isdigit(c));
    do r=(r<<1)+(r<<3)+(c^48);
    while(c=getchar(),isdigit(c));
}
bool cur1;
int n,m,lim,P;
const int mn=4005;
int mark[mn][mn];
int rd[mn][mn],ld[mn][mn],mid[mn][mn];
struct BIT{
    int c[mn];
    void clear(){
        rep(q,1,m)c[q]=0;
    }
    void add(int x,int v){
        while(x<=m)c[x]+=v,x+=x&-x;
    }
    int ask(int x){
        int ans=0;
        while(x)ans+=c[x],x&=x-1;
        return ans;
    }
    int ask(int l,int r){
        if(l>r)return 0;
        return ask(r)-ask(l-1);
    }
}ad;
struct nd{
    int l,r,v;
    bool operator <(const nd &A){
        return v>A.v;
    }
}an[mn],qr[mn];
long long ans;
void solve(int len){
    ad.clear();
    int tot=0;
    rep(q,1-min(0,len),min(m,n-len)){
        if(rd[q+len][q]){
            an[++tot]={q+len,q,rd[q+len][q]+q-1};
            qr[tot]={q-ld[q+len][q]+1,q-lim+1,q};
        }
    }
    sort(an+1,an+tot+1);
    int now=1,now1=tot;
    dep(q,m,1){
        while(now<=tot&&an[now].v==q){
            ad.add(an[now].r,1);
            ++now;
        }
        while(now1>0&&qr[now1].v==q){
            ans+=ad.ask(qr[now1].l,qr[now1].r);
            --now1;
        }
    }
}
bool cur2;
int main(){
//  cerr<<(&cur2-&cur1)/1024.0/1024.0;
    freopen("wall.in","r",stdin);
    freopen("wall.out","w",stdout);
    in(n),in(m),in(lim),in(P);
    int a,b;
    rep(q,1,P)in(a),in(b),mark[a][b]=1;
    rep(q,1,n)rep(w,1,m)ld[q][w]=!mark[q][w]?ld[q][w-1]+1:0;
    rep(w,1,m)rep(q,1,n)mid[q][w]=!mark[q][w]?mid[q-1][w]+1:0;
    rep(q,1,n)rep(w,1,m)ld[q][w]=min(ld[q][w],mid[q][w]);
    rep(q,1,n)dep(w,m,1)rd[q][w]=!mark[q][w]?rd[q][w+1]+1:0;
    rep(w,1,m)dep(q,n,1)mid[q][w]=!mark[q][w]?mid[q+1][w]+1:0;
    rep(q,1,n)rep(w,1,m)rd[q][w]=min(rd[q][w],mid[q][w]);
    
    rep(q,1-m,n-1)solve(q);
    
    printf("%lld",ans);
    return 0;
}

「JOI 2015 Final」城墙

原文：https://www.cnblogs.com/klauralee/p/11283645.html