【DS】CF765F Souvenirs

FxorG · 2022-01-07 15:14:02 · 题解

想了 2 天好像还是只会带 log 的。

一上来，这不就是 #246. 【UER #7】套路，但第二个做法不是很好做。由于第一个做法是 O(n^2) 的，那就分块（块长为 T）。整块的贡献很好做，对于每个块维护个值域前后驱就可以合并，大致就是记 f[l][r] 为块 l 与块 r 间的贡献，然后 f[l][r]=\min(f[l+1][r],f[l][r-1],cal(l,r))，其中 cal(l,r) 可以 O(T) 求。但散块不是很好维护。

然后我就弃了，冲了 2 个做法，回滚莫队+set，分块+主席树。带 log 显然冲不过。

滚回来继续想，发现贡献可以再拆。拆成 2 个散块分别与整块的贡献以及 2 个散块合并起来的贡献。前者也是可以通过类整块的思路维护，合并的话就只需要计算单点与一个整块的贡献（可以通过维护每个块的值域链表 O(1) 求出），但是这个东西写起来很烦！细节多的要死。散块间相互的贡献怎么办？把其当成一个块暴力排序的话就要带 log，假如用链表形式的话离散化后就是 O(n) 的。二者显然不行。考虑假如能够不排序，而是变成直接合并，那就是 O(T) 的。那么我们直接对于原来的块排序之后再类归并排序维护好像就行了，想到这转念一想前面的 cal，发现根本不用链表形式维护，也只需要类归并即可。排序复杂度 O(\dfrac{n}{T}T\log T)，即 O(n\log n)。

复杂度 O(n\log n+(\dfrac{n}{T})^2T+mT)，T 取根号即可。

AC Code

//qwq
#include <bits/stdc++.h>
using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
void pr(int x) {
    int f=1,tot=0; static int st[30];
    if(x<0) x=-x,f=-1;
    while(x) st[++tot]=x%10,x/=10;
    if(!tot) putchar('0');
    else for(int i=tot;i>=1;i--) putchar(st[i]+'0');
}
#define N (int)(1e5+5)
#define M 320
#define inf (int)(2e9)
vector<int>vec[M],tmp,tmp2,tmp3;
int n,m,bl,b[N],lsh[N],cnt[N],LLas[M][N],NNex[M][N],
a[N],id[N],L[M],R[M],f[M][M],ff[N][M],fff[M][N],tf[M][M],g[M];

bool cmp(const int &x,const int &y) {
    return a[x]<a[y];
}

void init(int x) {
    memset(cnt,0,sizeof(int)*(n+1));
    for(int i=L[x];i<=R[x];i++) ++cnt[b[i]];
    int qwq=-1;
    for(int i=1;i<=n;i++) {
        if(cnt[i]) qwq=i;
        LLas[x][i]=qwq; 
    }
    qwq=n+1;
    for(int i=n;i>=1;i--) {
        if(cnt[i]) qwq=i;
        NNex[x][i]=qwq;
    }
    vec[x].clear();
    for(int i=L[x];i<=R[x];i++) vec[x].push_back(i);
    sort(vec[x].begin(),vec[x].end(),cmp); 
    g[x]=inf;
    for(int i=L[x];i<=R[x];i++)
        for(int j=i+1;j<=R[x];j++)
            g[x]=min(g[x],abs(a[i]-a[j]));
}

int ssolve(int x,int y) {
    int res=inf;
    if(LLas[y][b[x]]!=-1) res=abs(a[x]-lsh[LLas[y][b[x]]]);
    if(NNex[y][b[x]]!=n+1) res=min(res,abs(lsh[NNex[y][b[x]]]-a[x]));
//  printf("%d %d %d %d %d\n",x,y,L[y],R[y],res);
    return res;
}

int solve(const vector<int>&x,const vector<int>&y) {
    if(!x.size()||!y.size()) return inf;
    tmp.clear();
    int nw1=0,nw2=0,res=inf;
    while(1) {
        if(a[x[nw1]]<a[y[nw2]]) {
            if(!tmp.empty()) res=min(res,a[x[nw1]]-tmp.back());
            tmp.push_back(a[x[nw1]]); ++nw1;
        } else {
            if(!tmp.empty()) res=min(res,a[y[nw2]]-tmp.back());
            tmp.push_back(a[y[nw2]]); ++nw2;
        }
    //  cout<<nw1<<" : "<<nw2<<endl;
        if(nw1>=x.size()||nw2>=y.size()) break;
    }
    while(nw1<x.size()) res=min(res,a[x[nw1]]-tmp.back()),tmp.push_back(a[x[nw1]]),++nw1;
    while(nw2<y.size()) res=min(res,a[y[nw2]]-tmp.back()),tmp.push_back(a[y[nw2]]),++nw2;
//  cout<<res<<endl;
    return res;
}
/*
int cal1(int x,int y) {
    int res=inf;
    for(int i=id[x]+1;i<=y;i++) 
        for(int j=x;j<=R[id[x]];j++)
            res=min(res,ssolve(j,i));
    for(int i=x;i<=R[id[x]];i++)
        for(int j=x;j<i;j++)
            res=min(res,abs(a[j]-a[i]));
    return res;
}

int cal(int x,int y) {
    int res=inf;
        for(int i=x;i<=y;i++)
            for(int j=i+1;j<=y;j++)
                res=min(res,abs(a[i]-a[j]));
    return res;
}
*/
int Solve(int x,int y) {
    if(id[x]==id[y]) { //假，但能过，也可以离线下来逐块处理 
        int res=inf;
        for(int i=x;i<=y;i++)
            for(int j=i+1;j<=y;j++)
                res=min(res,abs(a[i]-a[j]));
        return res;
    } else {
        int res=f[id[x]+1][id[y]-1];
        res=min(res,min(ff[x][id[y]-1],fff[id[x]+1][y]));
        tmp2.clear(); tmp3.clear();
    //  printf(": %d %d\n",x,y);
        for(int i=0;i<vec[id[x]].size();i++) if(vec[id[x]][i]>=x) tmp2.push_back(vec[id[x]][i]);
    //  puts("");
        for(int i=0;i<vec[id[y]].size();i++) if(vec[id[y]][i]<=y) tmp3.push_back(vec[id[y]][i]);
    //  puts("");
        res=min(res,solve(tmp2,tmp3));
        return res;
    }
}

int Pos(int x,int y) {
    return L[x]+y-1;
}

int main() {
    n=rd(); bl=sqrt(n);
    for(int i=1;i<=n;i++) id[i]=(i-1)/bl+1,lsh[i]=a[i]=rd();
    sort(lsh+1,lsh+1+n);
    for(int i=1;i<=n;i++) b[i]=lower_bound(lsh+1,lsh+1+n,a[i])-lsh;
    for(int i=1;i<=id[n];i++) L[i]=(i-1)*bl+1,R[i]=i*bl; R[id[n]]=n;
    for(int i=1;i<=id[n];i++) init(i);
    memset(f,0x3f,sizeof(f)); memset(ff,0x3f,sizeof(ff)); memset(fff,0x3f,sizeof(fff));
    // 块与块 
    for(int i=1;i<=id[n];i++) f[i][i]=g[i];
    for(int len=2;len<=id[n];len++)
        for(int l=1,r=l+len-1;r<=id[n];l++,r=l+len-1)
            f[l][r]=min(f[l+1][r],min(f[l][r-1],solve(vec[l],vec[r]))); 
    for(int i=1;i<=id[n];i++) ff[L[i]][i]=g[i],fff[i][R[i]]=g[i];
    // 端点到块，可理解为 ff[i][j]:[i,R[j]]
    // 类 f 转移即可，需要注意的是，类 f 转移要记得考虑散块内部的贡献，所以每次我们都要跑一遍 n 方的 
    for(int i=id[n]-1;i>=1;i--) {
        memset(tf,0x3f,sizeof(tf));
        int qwq=R[i]-L[i]+1;
        for(int j=1;j<qwq;j++) tf[j][j+1]=abs(a[Pos(i,j)]-a[Pos(i,j+1)]);
        for(int len=3;len<=qwq;len++) {
            for(int l=1,r=l+len-1;r<=qwq;l++,r=l+len-1)
                tf[l][r]=min(tf[l+1][r],min(tf[l][r-1],abs(a[Pos(i,l)]-a[Pos(i,r)]))); 
        }
        for(int j=R[i];j>=L[i];j--) ff[j][i+1]=min(ff[j+1][i+1],min(tf[j-L[i]+1][R[i]-L[i]+1],ssolve(j,i+1)));
        for(int j=i+2;j<=id[n];j++) {
            for(int k=R[i];k>=L[i];k--) {
                ff[k][j]=min(ff[k+1][j],min(ff[k][j-1],ssolve(k,j)));
            }
        } 
    }
    // fff[i][j]:[L[i],j] 块到点 
    for(int i=id[n]-1;i>=1;i--) {
        memset(tf,0x3f,sizeof(tf));
        int qwq=R[i]-L[i]+1;
        for(int j=1;j<qwq;j++) tf[j][j+1]=abs(a[Pos(i,j)]-a[Pos(i,j+1)]);
        for(int len=3;len<=qwq;len++) {
            for(int l=1,r=l+len-1;r<=qwq;l++,r=l+len-1)
                tf[l][r]=min(tf[l+1][r],min(tf[l][r-1],abs(a[Pos(i,l)]-a[Pos(i,r)]))); 
        }
        for(int j=L[i+1];j<=R[i+1];j++) fff[i][j]=min(fff[i][j-1],ssolve(j,i));
        for(int j=R[i+1]+1;j<=n;j++) fff[i][j]=min(fff[i][j-1],min(fff[i+1][j],ssolve(j,i)));
    }
    // 有些没转移到，即散块内部的 
    for(int i=1;i<=id[n];i++) {
        memset(tf,0x3f,sizeof(tf));
        int qwq=R[i]-L[i]+1;
        for(int j=1;j<qwq;j++) tf[j][j+1]=abs(a[Pos(i,j)]-a[Pos(i,j+1)]);
        for(int len=3;len<=qwq;len++) {
            for(int l=1,r=l+len-1;r<=qwq;l++,r=l+len-1)
                tf[l][r]=min(tf[l+1][r],min(tf[l][r-1],abs(a[Pos(i,l)]-a[Pos(i,r)]))); 
        }
        for(int j=L[i];j<=R[i];j++) ff[j][i]=min(ff[j][i],tf[j-L[i]+1][R[i]-L[i]+1]),fff[i][j]=min(fff[i][j],tf[1][j-L[i]+1]);
        for(int j=1;j<i;j++)
            for(int k=L[i];k<=R[i];k++)
                fff[j][k]=min(fff[j][k],tf[1][k-L[i]+1]);
    }
    m=rd();
    while(m--) {
        int x=rd(),y=rd();
        printf("%d\n",Solve(x,y));
    }
    return 0;
}

其他代码