圖 解題報告

線段樹合并

圖

題意：對一個聯通無向圖，每次找到一個點标号\(a<b<c\)的三元組滿足\((a,b),(a,c)\)有邊，然後連接配接\((b,c)\)，直到最後找不到三元組，問最終得到的圖的\(n\)種顔色染色方案數。

計數問題有一個常見的思路是想辦法把每個問題獨立出來，考慮如何計算每個點的貢獻能夠獨立的計算。

注意到有一個标号的條件看起來很關鍵，于是我們可以想辦法利用一下。

如果先把圖建出來，每個點與與它直接相連的大于它的點顔色一定不同，那麼這個點的染色方案是n-與它直接相連大于它的點的個數，并且我們發現這個确實也是獨立的，用乘法原理合并一下就可以了。

然後場上沒幾個人找到這個結論...

考慮我們統計的實際上是每個點向右邊連的度數。

可以按标号從小到大掃描，維護每個聯通塊向目前位置右邊的點連邊的個數，那麼目前位置的答案就是它所在聯通塊向右邊點連邊的個數。

實作的時候直接線段樹啟發式合并就可以了

#include <cstdio>
#include <cctype>
#include <algorithm>
namespace io
{
    const int SIZE=(1<<21)+1;
    char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];
    int f,qr;
    // getchar
    #define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
    // print the remaining part
    inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
    // putchar
    inline void putc(char x){*oS++=x;if(oS==oT)flush();}
    // input a signed integer
    template <class I>
    inline void read(I &x)
    {
        for(f=1,c=gc();c<'0'||c>'9';c=gc()) if(c=='-') f=-1;
        for(x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15);x*=f;
    }
    // print a signed integer
    template <class I>
    inline void print(I &x)
    {
        if(!x)putc('0');if(x<0) putc('-'),x=-x;
        while(x)qu[++qr]=x%10+'0',x/=10;
        while(qr)putc(qu[qr--]);
    }
    //no need to call flush at the end manually
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io::read;
using io::putc;
using io::print;
const int N=1e6+10;
const int mod=998244353;
int n,m,root[N],sum[N*40],ch[2][N*40],tot;
#define ls ch[0][now]
#define rs ch[1][now]
void ins(int &now,int l,int r,int p)
{
    if(!now) now=++tot;
	if(l==r) {sum[now]=1;return;}
	int mid=l+r>>1;
	if(p<=mid) ins(ls,l,mid,p);
	else ins(rs,mid+1,r,p);
	sum[now]=sum[ls]+sum[rs];
}
void del(int &now,int l,int r,int p)
{
    if(l==r) {now=0;return;}
    int mid=l+r>>1;
    if(p<=mid) del(ls,l,mid,p);
    else del(rs,mid+1,r,p);
    sum[now]=sum[ls]+sum[rs];
    if(!sum[now]) now=0;
}
int qryle(int now,int l,int r)
{
	if(l==r) return l;
	int mid=l+r>>1;
	if(sum[ls]) return qryle(ls,l,mid);
	else return qryle(rs,mid+1,r);
}
void Merge(int &now,int v,int l,int r)
{
	if(!now||!v) {now=now^v;return;}
	if(l==r) return;
	int mid=l+r>>1;
	Merge(ls,ch[0][v],l,mid);
	Merge(rs,ch[1][v],mid+1,r);
	sum[now]=sum[ls]+sum[rs];
}
int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
	read(n),read(m);
	for(int u,v,i=1;i<=m;i++)
	{
		read(u),read(v);
		ins(root[u],1,n,v);
	}
	int ans=1;
	for(int i=1;i<=n;i++)
	{
		ans=1ll*ans*(n-sum[root[i]])%mod;
		if(sum[root[i]])
		{
		    int v=qryle(root[i],1,n);
			Merge(root[v],root[i],1,n);
			del(root[v],1,n,v);
		}
	}
	print(ans);
	return 0;
}