P11831 [省選聯(lián)考 2025] 追憶 題解
題意
有一個(gè) \(n\) 個(gè)點(diǎn) \(m\) 條邊的DAG。每個(gè)點(diǎn)有權(quán)值 \(a_i\) 和 \(b_i\)。有 \(q\) 次操作，每次操作為以下其中之一：
- 給出 $1\ x\ y $，交換 \(a_x\) 和 \(a_y\)。
- 給出 $2\ x\ y $，交換 \(b_x\) 和 \(b_y\)。
- 給出 \(3\ x\ l\ r\)，求出在 \(x\) 可達(dá)的點(diǎn)集 \(C\) 中，找到 \(y\in C\)，滿(mǎn)足 \(l\le a_y\le r\)，求這樣的 \(y\) 中最大的 \(b_y\)。
保證給出的邊 \((u,v)\) 滿(mǎn)足 \(u<v\)。
\(n,q\le 10^5,m\le 2\times 10^5\)。
思路
首先本題的查詢(xún)需要滿(mǎn)足三個(gè)： \(x\) 可達(dá)、 \(a\in [l,r]\)，以及最大的 \(b\)。其中可達(dá)性是不會(huì)改變的，其他的 \(a,b\) 值可能被修改。
首先對(duì)于DAG的可達(dá)性，不難想到用bitset去在 \(O(\frac{nm}w)\) 的時(shí)間復(fù)雜度求出。因?yàn)閷?duì)于DAG，確實(shí)很難用一些其他帶 $\log $ 的方式解決。
具體就是對(duì)于每一個(gè)節(jié)點(diǎn) \(i\) 開(kāi)一個(gè)bitset\(G\)，如果 \(G_x\) 的第 \(y\) 位是1，則說(shuō)明 \(x\) 可達(dá) \(y\)?？梢栽贒AG上用按位或求出。
接下來(lái)先考慮對(duì)于 \(a\) 的處理。
因?yàn)榭蛇_(dá)性我們已經(jīng)用bitset 處理了，需要讓后續(xù)的處理能與此處的bitset 快速結(jié)合。因此，此處我們同樣考慮用bitset處理 \(a\)。
但是 \(a\) 需要滿(mǎn)足一個(gè)值域上的 \([l,r]\) 之間，所以考慮同樣開(kāi) \(n\) 個(gè)bitset \(A\)。對(duì)于 \(A_i\) ，若其第 \(y\) 位為1，則說(shuō)明當(dāng)前 \(a_y\ge i\)。
于是在 \((A_{r+1}\ \text{xor}\ A_{l})\) 中是 1 的位置對(duì)應(yīng)的點(diǎn)的 \(a\) 值一定在 \([l,r]\) 之間。
但是，我們開(kāi)不下 \(2n\) 個(gè)長(zhǎng)為 \(n\) 的 bitset，而且進(jìn)行修改 \(a\) 時(shí)需要改 \(O(n)\) 個(gè)bitset，會(huì)掛掉。而可達(dá)性的bitset 又難以?xún)?yōu)化。所以考慮優(yōu)化 \(A\)。
我們可以考慮用分塊去優(yōu)化，塊長(zhǎng)為 \(T\)。對(duì)于整塊去維護(hù)上述一樣的后綴，散塊暴力求值即可。這樣就只用開(kāi) \(\frac nT\) 個(gè)bitset了。
進(jìn)行修改時(shí)只用修改 $\frac{n}T $ 個(gè)塊。而求在 \([l,r]\) 的 \(A\) 也只需 \(O(\frac nw+T)\)。
我們求出了在 \([l,r]\) 的 \(A\) 后，與 \(G_x\) 進(jìn)行按位與，即可求到合法的 \(y\) 的集合 \(C\)。
此時(shí)已經(jīng)求出了合法的 \(y\) 的集合。考慮如何在這個(gè)用bitset 表示的集合中找出最大的 \(b_y\)。
這里還可以再用bitset去與 \(a\) 一樣維護(hù) \(b\) 值，設(shè)其為 \(B\)。這樣修改也可以 \(O(\frac nT)\)。
我們需要找到 \(C\) 中 \(b\) 值最大的值所在的塊，也就是與 \(C\) 進(jìn)行按位與后存在 1 位的最大的 \(B\) 的塊。然后再暴力在塊中找到最大的且在 \(C\) 中的值，輸出即可。
但是這里找最大的 \(B\) 塊不能直接枚舉每個(gè)塊再進(jìn)行按位與，因?yàn)檫@樣單次是 \(O(\frac {n^2} {Tw})\)，完全過(guò)不了。
對(duì)于兩個(gè)bitset進(jìn)行按位與是 \(O(\frac nw)\)，但只對(duì)一位求按位與就只需 \(O(1)\)。
我們不妨開(kāi)一個(gè)指針 \(j\)，初始化為 \(B\) 的第一個(gè)塊。在對(duì)于 \(C\) 的每一位進(jìn)行判斷，如果 \(B_j\) 與 \(C\) 按位與后這一位是 1，就不斷讓 \(j\) 加一，直到這一位結(jié)果不為 1。
這樣最后的 \(B\) 塊就是 \(B_{j-1}\)。這樣做時(shí)間復(fù)雜度是 \(O(\frac nw+\frac nT)\)。然后再在塊中暴力找在 \(C\) 中的最大值，輸出即可。
這道題就做完了，碼量并不大。bitset 還是手寫(xiě)吧，能快點(diǎn)。
\(T\) 取 \(\sqrt n\) 最優(yōu)，時(shí)間復(fù)雜度 \(O(\frac {nm}w+q(\frac nw+\sqrt n))\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int W=1570,len=320;
int n,m,q,A[N],B[N],ida[N],k,idb[N];
//a[ida[x]]=x,b[idb[x]]=x;
vector<int> e[N];
#define ull unsigned long long
struct bitst//手寫(xiě)bitset
{
ull s[W];
void reset() {memset(s,0,sizeof(s));}
void set(int x) {s[(x>>6)]|=1ull<<(x&63);}
void flip(int x) {s[(x>>6)]^=1ull<<(x&63);}
void operator &=(const bitst &b)
{
for(int i=0;i<W;i++) s[i]&=b.s[i];
}
void operator |=(const bitst &b)
{
for(int i=0;i<W;i++) s[i]|=b.s[i];
}
void operator ^=(const bitst &b)
{
for(int i=0;i<W;i++) s[i]^=b.s[i];
}
int val(int x){ return s[(x>>6)]>>(x&63)&1;}
};
bitst g[N],a[len],b[len],c;
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*10+ch-'0';ch=getchar();}
return x*f;
}
int L(int x){return x*len;}
int R(int x){return min(n,x*len+len-1);}//找塊的左右端點(diǎn)
void solve()
{
n=read(),m=read(),q=read();
k=n/len;
for(int i=1;i<=n;i++) g[i].reset(),g[i].set(i),e[i].clear();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
e[u].push_back(v);
}
for(int i=n;i>=1;i--)
{
for(int j=0;j<e[i].size();j++) g[i]|=g[e[i][j]];//維護(hù)可達(dá)性
}
for(int i=0;i<=k+1;i++) a[i].reset(),b[i].reset();
for(int i=1;i<=n;i++) A[i]=read(),a[A[i]/len].set(i),ida[A[i]]=i;
for(int i=1;i<=n;i++) B[i]=read(),b[B[i]/len].set(i),idb[B[i]]=i;
for(int i=k-1;i>=0;i--) a[i]|=a[i+1],b[i]|=b[i+1];//預(yù)處理A、B bitset
while(q--)
{
int op=read(),x=read(),l=read(),r;
if(op==1)
{
for(int i=A[x]/len;i>=0;i--) a[i].flip(x);
for(int i=A[l]/len;i>=0;i--) a[i].flip(l);
swap(ida[A[x]],ida[A[l]]);
swap(A[x],A[l]);
for(int i=A[x]/len;i>=0;i--) a[i].flip(x);
for(int i=A[l]/len;i>=0;i--) a[i].flip(l);//修改A
}
else if(op==2)
{
for(int i=B[x]/len;i>=0;i--) b[i].flip(x);
for(int i=B[l]/len;i>=0;i--) b[i].flip(l);
swap(idb[B[x]],idb[B[l]]);
swap(B[x],B[l]);
for(int i=B[x]/len;i>=0;i--) b[i].flip(x);
for(int i=B[l]/len;i>=0;i--) b[i].flip(l);//修改B
}
else
{
r=read();
c=a[l/len];
if(r/len<k) c^=a[r/len+1];
for(int i=L(l/len);i<l;i++) c.flip(ida[i]);
for(int i=R(r/len);i>r;i--) c.flip(ida[i]);
c&=g[x];//求出可選的點(diǎn)集C
int pos=-1;
for(int i=0;i<W;i++)
{
while(c.s[i]&b[pos+1].s[i]) pos++;
}//找到C中b的最大值所在的塊
if(pos==-1)
{
printf("0\n");
continue;
}
for(int j=R(pos);j>=L(pos);j--) //暴力在塊中找
{
if(c.val(idb[j]))
{
printf("%d\n",j);
break;
}
}
}
}
}
int main()
{
int ID=read(),T=read();
while(T--) solve();
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)