【TOI2019 二模 pD】離不開的新手村

題目敘述

給定一張$\color{white}{\space N\space}$點$\color{white}{\space M\space}$邊的有向圖，每個點有他的難度滿足「難度介於$\color{white}{\space 1\sim N\space}$之間」且「任兩個點難度相異」。

一個數字$\color{white}{\space i\space}$滿足「從任意的難度$\color{white}{\space \leq i\space}$的節點出發時，怎麼走都不會走到難度$\color{white}{\space >i\space}$的節點」時，數字$\color{white}{\space i\space}$就是『好的』，請你計算這張圖『好的』數字種類(介於$\color{white}{\space 1\sim N\space}$之間)。

接下來會有$\color{white}{\space Q\space}$次修改，每次修改會交換某兩個節點上的難度，請在每次修改後輸出新的『好的』數字種類。

子任務1(5分)：$\color{white}{\space 1\leq N,M \leq 100,1\leq Q \leq 100\space}$。
子任務2(16分)：圖是一條有向路徑。
子任務3(13分)：$\color{white}{\space M=N-1\space}$，每個點皆存在走到節點$\color{white}{\space 1\space}$的有向路徑。
子任務4(10分)：$\color{white}{\space 1\leq Q \leq 1000,|a-b|\leq 10000\space}$。
子任務5(25分)：每個點的入度不超過$\color{white}{\space 10\space}$。
子任務6(31分)：$\color{white}{\space 1\leq N,M \leq 500000,1\leq Q \leq 50000\space}$。

Time limit: 15 second

範測測資

Input: 5 5 1 2 3 4 5 2 4 3 1 2 1 4 3 5 3 3 2 4 2 3 5 3

Output: 3 4 5 4

作法

在解題之前，我們需要通靈一些東西(?)。
如果我們考慮把點依照難度由小到大一個一個加進圖裡面，那等價我們要計算有幾個時刻，使得不存在一條邊指到空(未加入)的節點。

可以發現，對於每條邊難度$\color{white}{\space a\space}$指到難度$\color{white}{\space b\space}$，若$\color{white}{\space a\space}$的難度比$\color{white}{\space b\space}$的難度大，那就不會出事；可是若$\color{white}{\space a\space}$的難度比$\color{white}{\space b\space}$的難度小，表示在時刻$\color{white}{\space [a,b)\space}$這個區間內，這條邊會出現在圖裡，卻指到空的節點。

我們發現每一條邊都有可能打到一條時刻的區間，於是我們可以把原題轉換成線段覆蓋問題，等價於求有多少點介於$\color{white}{\space 1\sim N\space}$之間且沒有被任何一條邊覆蓋到。

很顯然的，交換兩個難度等價於兩次單點修改，而一個點的難度改變了就只會改變自己相鄰所有邊所打到的區間，所以我們需要一個支援「區間加值」、「查詢有多少點是$\color{white}{\space 0\space}$」的資料結構－－這點操作完全可以拿我們在寫矩形覆蓋面積使用到的線段樹來支援。

所以我們目前至少獲得了一個$\color{white}{\space O(QM\log N)\space}$的作法。

此時我們必須做一點觀察，看著所有進到同一個點(難度$\color{white}{\space h\space}$)的邊所對應到的區間都是形如$\color{white}{\space [x,h)\space}$的形式，也就是右界都是固定的，由於我們只在意每個時刻是否「沒被蓋到過」，蓋到一次以上後蓋幾次都不在意了，所以我們可以只找到$\color{white}{\space [x,h)\space}$中$\color{white}{\space x\space}$最小的那個線段去覆蓋就可以了。這裡我們可以對每個點都開一個multiset去維護指到自己的人的最小值。

這時可以發現，覆蓋的線段總數會是$\color{white}{\space O(N)\space}$的，修改一個點時除了處理自己蓋的這條邊外，還要跑過所有自己指到的點去看看會不會對其造成影響，這時很慘的我們的複雜度依舊是$\color{white}{\space O(Q(入度Max)\log N)\space}$，不過至少可以拿到subtask 2,3的分數。

若反過來思考的話，也可以獲得對稱的複雜度$\color{white}{\space O(Q(出度Max)\log N)\space}$，拿到subtask 5的分數，但還是拿不到滿分。

試著再觀察一下，雖然我們甚至可以把兩種做法合併起來，對於每一種點都維護出$\color{white}{\space [指到自己的\min ,指到自己的\max)\space}$的這種區間，但瓶頸完全在於修改一個點會需要更動到太多人的multiset－－那如果有multiset的點數不要太多呢？

這時候大膽的想法就出現了(?)，考慮用$\color{white}{\space degree\space}$去分割：

以下把$\color{white}{\space N,M\space}$之量級視為一樣。
令$\color{white}{\space degree\geq K\space}$的是大點，$\color{white}{\space <K\space}$的是小點

首先把每個大點維護出
$\color{white}{\space [min(可到自己的點的難度,自己的難度),max(自己可到的點的難度,自己的難度))\space}$
用兩個multiset搞掉
這樣可以cover到所有大→大、大→小、小→大的邊

把所有小→小的邊$\color{white}{\space a\to b\space}$都維護出$\color{white}{\space [a,b)\space}$這個區間

這樣在修改大點的時候
大點除了改自己的區間 ($\color{white}{\space \log N\space}$)
還要主動修改所有其他相鄰的大點的區間和multiset ($\color{white}{\space \frac{N}{K}\log N\space}$)

修改小點的時候
主動修改所有其他相鄰的大點的區間和multiset
暴力修改所有連到自己的小->小的邊維護出的區間
(兩者加起來不超過$\color{white}{\space K\log N\space}$)

若$\color{white}{\space K\space}$取$\color{white}{\space \sqrt N\space}$總共的複雜度即為$\color{white}{\space Q\sqrt N\log N\space}$，而根據題目那時間限制感覺就可行XD。

實際上修改大點的常數可能會略大，所以我後來把$\color{white}{\space K\space}$取到3000才過。

附上code：

	#pragma GCC optimize("O3")
	#include <bits/stdc++.h>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define pb push_back
	#define MP make_pair
	#define F first
	#define S second
	#define ET cout << "\n"
	#define MEM(i,j) memset(i,j,sizeof i)
	#define ALL(v) v.begin(),v.end()
	#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll,ll> pll;
	vector<int> G[500005],nG[500005],rG[500005],nrG[500005];
	multiset<int> mso[500005],msi[500005];
	set<pii> st;
	const int root=3000;
	int seg[2000005],lazy[2000005],deg[500005],diff[500005],rdiff[500005],n;
	void modify(int L,int R,int l,int r,int rt,int val)
	{
	if(L<=l&&R>=r)
	return lazy[rt]+=val,void();
	int m=l+r>>1;
	if(L<=m) modify(L,R,l,m,rt<<1,val);
	if(R>m) modify(L,R,m+1,r,rt<<1|1,val);
	seg[rt]=0;
	if(lazy[rt<<1]) seg[rt]+=m-l+1;
	else seg[rt]+=seg[rt<<1];
	if(lazy[rt<<1|1]) seg[rt]+=r-m;
	else seg[rt]+=seg[rt<<1|1];
	}
	int gv()
	{
	if(lazy[1]) return 0;
	return n-seg[1];
	}
	void range(int a,int b,int v)
	{
	if(a>=b) return;
	modify(a,b-1,1,n,1,v);
	}
	void mdfy(int a,int b)
	{
	if(deg[a]>=root)
	{
	range(*msi[a].begin(),*mso[a].rbegin(),-1);
	msi[a].erase(msi[a].find(diff[a])),msi[a].insert(b);
	mso[a].erase(mso[a].find(diff[a])),mso[a].insert(b);
	range(*msi[a].begin(),*mso[a].rbegin(),1);
	for(int j:nG[a])
	{
	range(*msi[j].begin(),*mso[j].rbegin(),-1);
	msi[j].erase(msi[j].find(diff[a])),msi[j].insert(b);
	range(*msi[j].begin(),*mso[j].rbegin(),1);
	}
	for(int j:nrG[a])
	{
	range(*msi[j].begin(),*mso[j].rbegin(),-1);
	mso[j].erase(mso[j].find(diff[a])),mso[j].insert(b);
	range(*msi[j].begin(),*mso[j].rbegin(),1);
	}
	}
	else
	{
	for(int j:G[a])
	if(deg[j]>=root)
	{
	range(*msi[j].begin(),*mso[j].rbegin(),-1);
	msi[j].erase(msi[j].find(diff[a])),msi[j].insert(b);
	range(*msi[j].begin(),*mso[j].rbegin(),1);
	}
	else
	range(diff[a],diff[j],-1),range(b,diff[j],1);
	for(int j:rG[a])
	if(deg[j]>=root)
	{
	range(*msi[j].begin(),*mso[j].rbegin(),-1);
	mso[j].erase(mso[j].find(diff[a])),mso[j].insert(b);
	range(*msi[j].begin(),*mso[j].rbegin(),1);
	}
	else
	range(diff[j],diff[a],-1),range(diff[j],b,1);
	}
	diff[a]=b;
	}
	int main()
	{jizz
	int m,q,a,b;
	cin >> n >> m;
	for(int i=1;i<=n;++i)
	cin >> diff[i],rdiff[diff[i]]=i;
	while(m--)
	{
	cin >> a >> b;
	if(a!=b)
	st.insert(MP(a,b));
	}
	for(auto i:st)
	G[i.F].pb(i.S),rG[i.S].pb(i.F);
	for(int i=1;i<=n;++i)
	deg[i]=G[i].size()+rG[i].size();
	for(int i=1;i<=n;++i)
	if(deg[i]>=root)
	{
	mso[i].insert(diff[i]),msi[i].insert(diff[i]);
	for(int j:G[i])
	{
	mso[i].insert(diff[j]);
	if(deg[j]>=root)
	nG[i].pb(j);
	}
	for(int j:rG[i])
	{
	msi[i].insert(diff[j]);
	if(deg[j]>=root)
	nrG[i].pb(j);
	}
	range(*msi[i].begin(),*mso[i].rbegin(),1);
	}
	else
	{
	for(int j:G[i])
	if(deg[j]<root&&i<j)
	range(diff[i],diff[j],1);
	for(int j:rG[i])
	if(deg[j]<root&&i<j)
	range(diff[j],diff[i],1);
	}
	cout << gv() << "\n";
	for(cin >> q;q--;)
	cin >> a >> b,mdfy(rdiff[a],b),mdfy(rdiff[b],a),swap(rdiff[a],rdiff[b]),cout << gv() << "\n";
	}

view raw Stay.cpp hosted with ❤ by GitHub