CF765F

highkj · 2024-09-05 17:31:02 · 题解

前言

为什么没人写压位 Trie 啊？

思路

对于 |a_i-a_j| 的 a_i 和 a_j 一定是对于原序列排序之后相邻的两个数（及一个是前驱一个是后缀），那么很好想到可以一个 O(n\times \sqrt{n}\times \log(n)) 的莫队做法，但是它过不了所以考虑优化成回滚莫队，这样就可以避免删除时要更新最小值了，然后我们发现还是需要求出一个数的前驱和后缀，所以我们还是需要用一个 set 做法，但是这里有一个经典优化，就是可以用压位 Trie 在 O(\log_w(n)) 的时间复杂度求出前去和后缀，如果不会 可以进去学习一下，大致思想就是用 s_{i,j} 表示到第 i 层前缀之和为 j 是这一个点儿子节点是否存在（这里用了状压，如果第 i 为有儿子那么 s_{i,j} 在二进制下第 i 位为 1 否则为 0）我们发现这样状压之后树的深度很小所以基本可以当作是一个常数。

还是细讲一下压位 Trie，不然没东西写了。

考虑插入一个数，我们遍历时必须从下往上遍历及每次要将 x 右移 6 如果 s_{i,x>>6} 的第 x\&63 位（因为每 64 个归为一位）有值了就不需要向上递归了毕竟它的上面的位置已经都相同了。

void ins(int x) {
    rep1(i,3,0) {
        if(s[i][x>>6]>>(x&63)&1) return;//如果已经有了就不需要继续递归了
        s[i][x>>6]|=(1ll<<(x&63));//将此位标记成1
        x>>=6;
    }
}

因为这个莫队不需要删除只需要清空所以直接暴力枚举然后将 s_{i,j} 都等于 0 即可。

void shan(int x) {
    rep1(i,3,0) {
        s[i][x>>6]=false;
        x>>=6;
        if(s[i][x]) return;//因为如果将自己的删掉之后还有之前的与自己相同的就不需要再往上清空了毕竟后面会清空到
    }
}

求前驱也很简单，也是从下往上遍历找到第一个自己的位置之前还有 1 的地方（就是这一位上不仅 x\&63 是 1 还有 x\&63 之前的位置也是 1）那么就可以将这一位的 x\&63 之前的最靠后的 1 的位置一定会算再加上还未算的和（x 将最后 6 位删除之后再左移 6 位）然后还要填的位置都填能填的最大值即可。

int highest(ull x) {
    return 63-__builtin_clzll(x);//找到 x 中从右往左最靠后的 1 的位置
}
int pre(int x) {
    rep1(i,3,0) {
        ull val=false;
        val=s[i][x>>6];
        val<<=(64-(63&x));
        if((x&63)==false) val=0;//特判左移 64
        if(val) {
            val>>=(64-(63&x));
            ull now=highest(val)|(x>>6<<6);//加上前面未加的那一坨
            while(++i<=3) now=(now<<6)|(highest(s[i][now])); //取能取的最大的
            return now;
        }
        x>>=6;
    }
    return false;
}

至于后缀其实差不多，就是找到第一个满足 x\&63 之后有的位置，然后前面的直接加上后面的取能取的最小值即可。

int lowest(ull x) {
    return __builtin_ctzll(x);
}
int nxt(int x) {
    rep1(i,3,0) {
        ull val=false;
        val=s[i][x>>6];
        val>>=((x&63)+1);
        if((x&63)==63) val=0;//特判
        if(val) {
            val<<=((x&63)+1);
            ull now=lowest(val)|(x>>6<<6);
            while(++i<=3) now=(now<<6)|(lowest(s[i][now]));
            return now;
        }
        x>>=6;
    }
    return false;
}

对于回滚莫队只需要将 l 回滚的那些用一个 Trie 维护再用另一个 Trie 维护 r 的即可。

注意：压位 Trie 不能处理一个数有相同的前驱和后缀所以要新开一个桶来看答案是否为 0。

其他就都是模板了。

时间复杂度 O(n\times \sqrt{n}\times \log_{64}(n)) 能过。

代码

写的像 史 一样，又臭又长。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ull unsigned long long
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define fire signed
#define il inline
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
int n;
const int N=1e5+10,M=3e5+10;
ull s[5][N],s1[5][N];
vector<pair<int,int>>v[N];
vector<int>le;
int cc[N],cc1[N];
int len,m,b[N],a[N];
#define bl(i) ((i-1)/len+1)
void ins(int x) {
    rep1(i,3,0) {
        if(s[i][x>>6]>>(x&63)&1) return;
        s[i][x>>6]|=(1ll<<(x&63));
        x>>=6;
    }
}
void ins1(int x) {
    rep1(i,3,0) {
        if(s1[i][x>>6]>>(x&63)&1) return;
        s1[i][x>>6]|=(1ll<<(x&63));
        x>>=6;
    }
}
void shan(int x) {
    rep1(i,3,0) {
        s[i][x>>6]=false;
        x>>=6;
        if(s[i][x]) return;
    }
}
int highest(ull x) {
    return 63-__builtin_clzll(x);
}
int lowest(ull x) {
    return __builtin_ctzll(x);
}
int pre(int x) {
    rep1(i,3,0) {
        ull val=false;
        val=s[i][x>>6];
        val<<=(64-(63&x));
        if((x&63)==false) val=0;
        if(val) {
            val>>=(64-(63&x));
            ull now=highest(val)|(x>>6<<6);
            while(++i<=3) now=(now<<6)|(highest(s[i][now]));
            return now;
        }
        x>>=6;
    }
    return false;
}
int pre1(int x) {
    rep1(i,3,0) {
        ull val=false;
        val=s1[i][x>>6];
        if((x&63)==false) val=0;
        val<<=(64-(63&x));
        if(val) {
            val>>=(64-(63&x));
            ull now=highest(val)|(x>>6<<6);
            while(++i<=3) now=(now<<6)|(highest(s1[i][now]));
            return now;
        }
        x>>=6;
    }
    return false;
}
int nxt(int x) {
    rep1(i,3,0) {
        ull val=false;
        val=s[i][x>>6];
        val>>=((x&63)+1);
        if((x&63)==63) val=0;
        if(val) {
            val<<=((x&63)+1);
            ull now=lowest(val)|(x>>6<<6);
            while(++i<=3) now=(now<<6)|(lowest(s[i][now]));
            return now;
        }
        x>>=6;
    }
    return false;
}
int nxt1(int x) {
    rep1(i,3,0) {
        ull val=false;
        val=s1[i][x>>6];
        val>>=((x&63)+1);
        if((x&63)==63) val=0;
        if(val) {
            val<<=((x&63)+1);
            ull now=lowest(val)|(x>>6<<6);
            while(++i<=3) now=(now<<6)|(lowest(s1[i][now]));
            return now;
        }
        x>>=6;
    }
    return false;
}
int ans[M];
void solve() {
    in(n);
    rep(i,1,n) in(a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    int ll=unique(b+1,b+1+n)-b-1;
    rep(i,1,n) a[i]=lower_bound(b+1,b+1+ll,a[i])-b;
    in(m);
    len=sqrt(n);
    rep(i,1,m) {
        int l,r;
        in(l),in(r);
        v[bl(l)].pb({r,i});
        le.pb(l);
    }
    rep(i,1,bl(n)) sort(v[i].begin(),v[i].end());
    rep(i,1,bl(n)) {
        rep(j,0,3) rep(k,0,ll) s[j][k]=s1[j][k]=false;
        rep(j,1,ll) cc[j]=false;
        int R=min(n,i*len),lst=INT_MAX;
        for(auto to:v[i]) {
            int l=le[to.second-1],r=to.first;
            int L=min(n,i*len);
            int res=INT_MAX;
            if(bl(l)==bl(r)) {
                rep(j,l,r) {
                    int pr=pre(a[j]),nx=nxt(a[j]);
                    if(pr) res=min(res,b[a[j]]-b[pr]);
                    if(nx) res=min(res,b[nx]-b[a[j]]);
                    cc[a[j]]++;
                    if(cc[a[j]]>=2) {
                        res=0;
                        break;
                    }
                    ins(a[j]);
                }
                ans[to.second]=res;
                rep(j,l,r) cc[a[j]]=false,shan(a[j]);
            }else {
                ins(a[L]);
                cc1[a[L]]++;
                if(cc1[a[L]]+cc[a[L]]>=2) res=0;
                int ppr=pre1(a[L]),nxx=nxt1(a[L]);
                if(ppr) res=min(res,abs(b[ppr]-b[a[L]]));
                if(nxx) res=min(res,abs(b[a[L]]-b[nxx]));
                while(L>l) {
                    L--;
                    int pr=pre(a[L]),pr1=pre1(a[L]),nx=nxt(a[L]),nx1=nxt1(a[L]);
                    if(pr) res=min(res,b[a[L]]-b[pr]);
                    if(pr1) res=min(res,b[a[L]]-b[pr1]);
                    if(nx) res=min(res,b[nx]-b[a[L]]);
                    if(nx1) res=min(res,b[nx1]-b[a[L]]);
                    cc1[a[L]]++;
                    if(cc[a[L]]+cc1[a[L]]>=2) {
                        res=0;
                        break;
                    }
                    ins(a[L]);
                }
                while(R<r) {
                    R++;
                    int pr=pre(a[R]),pr1=pre1(a[R]),nx=nxt(a[R]),nx1=nxt1(a[R]);
                    if(pr) res=min(res,b[a[R]]-b[pr]);
                    if(pr1) res=min(res,b[a[R]]-b[pr1]);
                    if(nx) res=min(res,b[nx]-b[a[R]]);
                    if(nx1) res=min(res,b[nx1]-b[a[R]]);
                    if(pr1) lst=min(lst,abs(b[pr1]-b[a[R]]));
                    if(nx1) lst=min(lst,abs(b[nx1]-b[a[R]]));
                    cc[a[R]]++;
                    if(cc[a[R]]>=2) {
                        lst=res=false;
                        continue;
                    }
                    if(cc[a[R]]+cc1[a[R]]>=2){
                        res=0;
                        continue;
                    } 
                    ins1(a[R]);
                }
                ans[to.second]=min(res,lst);
                rep(j,L,min(n,i*len)) shan(a[j]),cc1[a[j]]=false;
            }
        }
    }
    rep(i,1,m) printf("%d\n",ans[i]);
}
fire main() {
    while(T--) {
        solve();
    }
    return false;
}

Submission