题解 AT3673 【[ARC085D] NRE】

Skyjoy · 2022-07-07 15:18:37 · 题解

upd ：修改了一些笔误

模拟赛见到了这道题并意外地做了出来。赛时觉得好像是我看到过但没去做的一道 ARC 的题，赛后发现还真的是 ARC 的原题。这题挺有意思的，写篇题解纪念一下。

思路

首先有一个很显然的 dp 思路。我们先讲区间按左端点排序。设 f_i 表示我们考虑完前 i 个区间并接受第 i 个区间时全局的最小海明距离。然后我们往 i 前面枚举区间 j 。假设原数组的前缀和数组为 sum ，第 i 个区间所对应的集合为 S_i ，那么我们可以得到下面的柿子：

\min{f_j+r_i-l_i+1-2(sum_{r_i}-sum_{l_i-1})},S_i\cap S_j=\varnothing\\ \min{f_j+r_i-r_j-2(sum_{r_i}-sum_{r_j})},S_i\cap S_j\neq\varnothing\ \text{且}\ S_i\subsetneq S_j\\ \min{f_j},S_i\subseteq S_j \end{cases}

最后答案就是 f_i 的最小值了。因为求的是所有 f_i 的最小值，所以上述转移方程中的第 3 条显然可以忽略，只需要前 2 条就可以转移了。如果暴力转移的话复杂度是 O(q^2) 的，那么怎么优化呢？
我们发现冗余的操作主要是出现在取 \min 部分的，所以我们要将这一部分简化。由于我们将区间按左端点排序，我们发现，当 j<i 时， S_i\cap S_j=\varnothing 的充要条件是 r_j<l_i ， S_i\cap S_j\neq\varnothing\ \text{且}\ S_i\subsetneq S_j 的充要条件是 r_j\in [l_i,r_i] 。所以我们只需要建两棵线段树分别维护两个方程就可以了。
具体地，我们根据区间的值域开线段树，当我们枚举到区间 i 时，我们将 f_i 和 f_i-r_i+2sum_{r_i} 分别插入两棵线段树的 r_i 处即可。查询时查询第 1 棵线段树的 [1,l_i-1] 区间和第 2 棵线段树的 [l_i,r_i] 区间再加上一些方程里的其他值比大小就行了。当然，不要忘了 f_i 一开始是要从 f_0 开始转移的。时间复杂度是 O(qlog_2n) ，可以通过此题。剩下的细节就看代码吧！

代码

#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
I love Elaina;
const int N=200010;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,m,a[N],sum[N],f[N],ans,res;
struct qry{
    int l,r;
    bool operator<(const qry &rhs)const{
        return (l!=rhs.l)?l<rhs.l:r<rhs.r;
    }
}qwq[N];
namespace AyaseEli{
    #define ls(k) (k<<1)
    #define rs(k) (k<<1|1)
    struct node{
        int minn,l,r;
    }tree[2][N<<2];
    void pushup(node *tree,int k){
        tree[k].minn=min(tree[ls(k)].minn,tree[rs(k)].minn);
    }
    void build(node *tree,int k,int l,int r){
        tree[k].l=l,tree[k].r=r,tree[k].minn=0x3f3f3f3f;
        if(l==r)return;
        int mid=(l+r)/2;
        build(tree,ls(k),l,mid),build(tree,rs(k),mid+1,r);
        pushup(tree,k);
    }
    void modify(node *tree,int k,int q,int v){
        if(tree[k].l==tree[k].r){
            tree[k].minn=v;
            return;
        }
        int mid=(tree[k].l+tree[k].r)/2;
        if(q<=mid)modify(tree,ls(k),q,v);
        else modify(tree,rs(k),q,v);
        pushup(tree,k);
    }
    int query(node *tree,int k,int ql,int qr){
        int res=0x3f3f3f3f;
        if(ql<=tree[k].l&&tree[k].r<=qr)return tree[k].minn;
        int mid=(tree[k].l+tree[k].r)/2;
        if(ql<=mid)res=min(res,query(tree,ls(k),ql,qr));
        if(mid<qr)res=min(res,query(tree,rs(k),ql,qr));
        return res;
    }
}
I love AyaseEli;
int main(){
    memset(f,0x3f,sizeof(f));
    n=read();
    build(tree[0],1,1,n),build(tree[1],1,1,n);
    for(int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i];
    ans=sum[n];
    m=read();
    for(int i=1;i<=m;i++)qwq[i]=(qry){read(),read()};
    sort(qwq+1,qwq+m+1);
    for(int i=1;i<=m;i++){
        f[i]=sum[n]+qwq[i].r-qwq[i].l+1-2*(sum[qwq[i].r]-sum[qwq[i].l-1]);
        if(qwq[i].l!=1)f[i]=min(f[i],query(tree[0],1,1,qwq[i].l-1)+qwq[i].r-qwq[i].l+1-2*(sum[qwq[i].r]-sum[qwq[i].l-1]));
        f[i]=min(f[i],query(tree[1],1,qwq[i].l,qwq[i].r)+qwq[i].r-2*sum[qwq[i].r]);
        modify(tree[0],1,qwq[i].r,f[i]),modify(tree[1],1,qwq[i].r,f[i]-qwq[i].r+2*sum[qwq[i].r]);
        ans=min(ans,f[i]);
    }
    printf("%d",ans);
    return 0;
}

祝各位大神们 NOI 加油！