AGC061C First Come First Serve 做题记录

有 $n$ 个人来过，第 $i$ 个人在 $a_i$ 时刻来在 $b_i$ 时刻走，每个人可以在来时或走时登记，问可能的登记顺序有多少种。

$n\leqslant 5\times 10^5$，$a_i,b_i$ 互不相同，$\forall i<n,a_i<a_{i+1},b_{i}<b_{i+1}$。

容斥。

观察到一个 $i$ 选 $a_i$ 和选 $b_i$ 本质不同当且仅当 $[a_i,b_i]$ 中有其他人选。

那么容斥一下，钦定 $y$ 个不同的 $i$ 满足 $[a_i,b_i]$ 中没有其他人选，则对答案的贡献为 $2^{x}(-1)^y$，其中 $x$ 为与这 $y$ 个区间没有交的区间个数。

那么设 $f_{i}$ 表示算完了前 $i$ 个人，钦定了 $[a_i,b_i]$ 中没有其他人选的总贡献和。

转移直接枚举上一个钦定的人即可。

可以用前缀和优化，时间复杂度 $O(n)$。

代码如下：（$O(n\log n)$ 树状数组）

// Problem: [AGC061C] First Come First Serve
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_agc061_c
// Memory Limit: 1 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=500005,p=998244353,inv2=499122177;

struct node
{
	int l,r;
}a[S];

int n;
int iv2[S],pw2[S];
int lst[S],nxt[S];
int f[S],sum[S*2];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline void addt(int p,int y)
{
	if(p==0) return add(sum[p],y);
	for(int i=p;i<=2*n;i+=i&-i) add(sum[i],y);
}

inline int quet(int p)
{
	int res=sum[0];
	for(int i=p;i>=1;i-=i&-i) add(res,sum[i]);
	return res;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
	iv2[0]=pw2[0]=1;
	for(int i=1;i<=S-3;i++) iv2[i]=1ll*iv2[i-1]*inv2%p;
	for(int i=1;i<=S-3;i++) pw2[i]=1ll*pw2[i-1]*2%p;
	for(int i=1;i<=n;i++)
	{
		lst[i]=i==1?1:lst[i-1];
		while(a[lst[i]].r<a[i].l) lst[i]++;
	}
	for(int i=n;i>=1;i--)
	{
		nxt[i]=i==n?n:nxt[i+1];
		while(a[nxt[i]].l>a[i].r) nxt[i]--;
	}
	f[0]=1;
	addt(0,1ll*f[0]*iv2[0]%p);
	for(int i=1;i<=n;i++)
	{
		int pre=p-1ll*pw2[lst[i]-1]*quet(a[i].l-1)%p;
		addt(a[nxt[i]].r,1ll*pre*iv2[nxt[i]]%p);
	}
	printf("%d\n",1ll*pw2[n]*quet(2*n)%p);
	return 0;
}