[省选联考 2025] 追忆题解

思路可以见游记。

这是一个很暴力的考场做法，似乎没看见跟我一样的。

首先有向图可达性算是比较典的

O(\frac{n^2}{\omega})

，正好题目也提示了我们空间和时间都很大，所以这个肯定对完了。具体地，预处理

n

个 bitset

C_{i}

表示

i

是否可达

j

。查询的时候相当于查询

f_i

中所有

a

在值域中的

b

的最大值。

然后这两个带修看上去都非常不容易，好像只会 ABC 性质但是又没有。考察思考的方向，注意到如果

i

可达集合是

[i,n]

所有点的话不弱于动态二维数点，而这个题已经有一个平方级别的暴力部分了所以不妨完全放弃 polylog 开始想分块之类的暴力结构。

尝试解决

a

上的值域限制。一个基于

a

静态的想法是，处理

a

的每个值域前缀对应的下标和。即

A_i

表示所有

a_j\le i

的

j

的集合组成的 bitset。这样至少可以在每次询问中

O(\frac n\omega)

地去除

a

的限制，似乎是不错的。再仔细一想，这个空间似乎已经是两倍的

\frac{n^2}{\omega}

，一定会很卡，所以考虑放弃。

这种前缀和相关的题需要注意到，如果查询的复杂度和预处理的复杂度很不平衡，可以套用一些看上去几乎无意义的分块来压缩空间（有一个较深的印象是我和 irris 的这个题的这篇题解）。注意到我们分块之后，查询的时候的单点修改的复杂度是非常小的，是小常数

O(1)

，然而查询整块非常耗费时间。而我们非常经得起大量的散块查询，在

n\le 10^5

的时候把块长开到

2000

都可以接受。于是可以细想分块了！

不妨按

B

分块。说人话就是只维护所有

i\equiv 0(\bmod B)

的

i

的

A_i

。这样还有一个好处是，对

a

的单点修改只会改到

\frac{n}{B}

个

A_i

，所以

op=1

也可以接受了。查询的时候相当于需要支持查询单点

A_r

，可以先调用

A_{B\lfloor\frac{r}{B}\rfloor}

，再把缺的单点部分暴力补上。这整个部分时间复杂度是

O(\frac{n^2}{\omega}+q(B+\frac{n}{\omega}+\frac nB))

。

实际上这个时候写一个取出所有符合要求的点求

b_{\max}

可以在最后一个大样例跑 7s，几乎可以通过了。

然后考虑如何优化

b

的部分。可以发现即使是静态问题都没有什么优秀的做法。直接枚举或者直接分块显然没有什么理论低于

O(nq)

的做法。

考虑为什么要我们求

b_{\max}

呢？有一个直接的想法是二分答案，变成判定给定 bitset 和

b

的值域区间是否有交。不妨把

b

的值域取反变成前缀（方便我自己理解），类似上面地设计

D_{i}

表示所有

b_j\le i

的

j

组成的 bitset（这里似乎和块长的字母重复了，那就随便新取一个）。在不带修的时候可以做到

O(\frac{nq}{\omega}\log n)

。感觉很蠢，还不能带修。但是

b

的修改是否可以参考

a

的修改呢？

这就不得不提到 WC 文艺汇演的相声（这句话也给了我相当的启发）：

找一个数在有序序列中的出现位置的时候，先分块！二分它在哪个块里，然后在块里二分！就做到了 $O(\log\sqrt n)$ ！

可以想到仍然对

b_i

分块，维护方法同

a_i

。查询的时候直接二分它在哪个块里（因为只维护了整块信息，查询还方便），然后暴力查询块内，这样完美平衡了一下单点查询的

O(1)

和整块前缀查询的

O(\frac n\omega)

！

具体地，维护所有整块代表的 bitset 的前缀和。查询的时候在大块上查询，可以极大的削掉

\log n

的部分。check 的时候只需要拿

D_{iB}

和当前询问的 bitset 判断交是否非空即可。对于散块，暴力查询的

O(1)

还是很可观的！同时分块仍然可以支持带修！这部分时间复杂度

O(q(\frac{n\log{\frac nB}}{\omega}+B+\frac{n}{B}))

。具体

B

取啥的时候最优懒得算了，反正我直接取

B=2000

在大样例跑了 2.3s。此时

\log \frac nB

只有

6

，至少少了三倍常数。上下取同一个

B

，总时间复杂度就是

O(\frac{n^2}{\omega}+q(\frac{n\log{\frac nB}}{\omega}+B+\frac{n}{B}))

。

建议手写 bitset，理由不知道。

考场代码：

CPP

#include<bits/stdc++.h>
#define MOD 998244353
#define int long long
#define REP(i,a,n) for(int i=(a);i<(int)(n);++i)
#define pii pair<int,int>
#define pb push_back
#define all(v) v.begin(),v.end()
#define over {cout<<x<<"\n";return;}
using namespace std;
int read(){
    int res=0;char c=getchar();
    while(c<48||c>57)c=getchar();
    do res=(res<<1)+(res<<3)+(c^48),c=getchar();while(c>=48&&c<=57);
    return res;
}
int qpow(int a,int b,int m=MOD){
    int res=1;
    while(b)res=b&1? res*a%m:res,a=a*a%m,b>>=1;
    return res;
}
#define ui unsigned int
int ID;
vector<int>v[100005];
int n,m,q,BL,CL;
ui C[100000][1563];
ui A[400][1563];
ui B[400][1563];
int a[100000],b[100000],ia[100000],ib[100000];
ui qr[1563];
void updA(int x,int y){
    REP(i,x/BL,CL)A[i][y>>6]^=1ull<<(y&63);
}
void updB(int x,int y){
    REP(i,x/BL,CL)B[i][y>>6]^=1ull<<(y&63);
}
void opA(int x){
    int d=x/BL-1;
    if(x>=BL){
        REP(j,0,m)qr[j]^=A[d][j];
    }
    REP(i,x/BL*BL,x+1)qr[ia[i]>>6]^=1ull<<(ia[i]&63);
}
void Main(){
    n=read();m=read();q=read();
    REP(i,0,n)v[i].clear();
    REP(i,0,m){
        int x,y;
        x=read()-1;y=read()-1;
        v[x].pb(y);
    }
    m=(n-1)>>6;++m;
    for(int i=n-1;i>=0;--i){
        REP(j,i>>6,m)C[i][j]=0;
        C[i][(i>>6)]=1ull<<(i&63);
        for(auto j:v[i]){
            REP(l,j>>6,m)C[i][l]|=C[j][l];
        }
    }
    BL=sqrt(n*7);BL=min(BL,n);
    BL=min(2000ll,n);
    CL=(n-1)/BL+1;
    REP(i,0,n){
        a[i]=read()-1;
        ia[a[i]]=i;
    }
    REP(i,0,n){
        int d=i/BL;
        if(i%BL==0){
            if(i){
                REP(j,0,m)A[d][j]=A[d-1][j];
            }else{
                REP(j,0,m)A[d][j]=0;
            }
        }
        A[d][ia[i]>>6]|=1ull<<(ia[i]&63);
    }
    REP(i,0,n)b[i]=n-read(),ib[b[i]]=i;
    REP(i,0,n){
        int d=i/BL;
        if(i%BL==0){
            if(i){
                REP(j,0,m)B[d][j]=B[d-1][j];
            }else{
                REP(j,0,m)B[d][j]=0;
            }
        }
        B[d][ib[i]>>6]|=1ull<<(ib[i]&63);
    }
    REP(i,0,q){
        int op,x,y,l,r;
        op=read();
        if(op==1){
            x=read()-1;y=read()-1;
            swap(a[x],a[y]);
            x=a[x];y=a[y];
            updA(x,ia[x]);updA(x,ia[y]);
            updA(y,ia[y]);updA(y,ia[x]);
            swap(ia[x],ia[y]);
        }else if(op==3){
            x=read()-1;l=read()-1;r=read()-1;
            REP(j,0,m)qr[j]=0;
            if(l)opA(l-1);
            opA(r);
            REP(j,0,m)qr[j]&=C[x][j];
            int ans=0,fl=0;
            REP(j,0,m){
                if(qr[j])fl=1;
            }
            if(!fl){
                cout<<0<<'\n';
                continue;
            }
            int l=0,r=CL-1,res=r;
            while(l<=r){
                int mid=(l+r)>>1,f=0;
                REP(j,0,m)if(B[mid][j]&qr[j]){f=1;break;}
                if(f)res=mid,r=mid-1;
                else l=mid+1;
            }
            for(int i=res*BL;i<n;++i){
                int x=ib[i];
                if(qr[x>>6]&(1ull<<(x&63))){
                    ans=i;
                    break;
                }
            }
            cout<<n-ans<<'\n';
        }else{
            x=read()-1;y=read()-1;
            swap(b[x],b[y]);
            x=b[x];y=b[y];
            updB(x,ib[x]);updB(x,ib[y]);
            updB(y,ib[y]);updB(y,ib[x]);
            swap(ib[x],ib[y]);
        }
    }
}
signed main(){
    freopen("recall.in","r",stdin);
    freopen("recall.out","w",stdout);
    int tc=1;
    ID=read();tc=read();
    while(tc--)Main();
    return 0;
}

[省选联考 2025] 追忆题解

文章操作

相关推荐

评论

[省选联考 2025] 追忆题解