记录编号	578121	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[统一省选 2021]图函数	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.095 s
提交时间	2023-02-02 15:39:17	内存使用	4.91 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
using pii = std::pair<int,int>;

const int maxn = 1e3 + 5;
const int maxm = 2e5 + 5;
int n,m,ans[maxm];
pii E[maxm];
std::bitset<maxn> a[2][maxn],r[2][maxn],G[2][maxn];

void add(int id,int u,int v,int t) {
	G[t][u][v] = true;
	std::queue<int> q;
	std::bitset<maxn> p = r[t][u] & ~r[t][v];
	for(int s = p._Find_first();s <= u&&s < v;s = p._Find_next(s)) {
		ans[id - 1] += a[!t][s][v];
		a[t][s][v] = r[t][v][s] = true;
		q.emplace(v);
		while(!q.empty()) {
			int j = q.front();
			q.pop();
			std::bitset<maxn> cur = G[t][j] & ~a[t][s];
			for(int k = cur._Find_next(s);k < maxn;k = cur._Find_next(k)) {
				ans[id - 1] += a[!t][s][k];
				a[t][s][k] = r[t][k][s] = true;
				q.emplace(k);
			}
		}
	}
	return ;
}

int main() {
	freopen("haoi2021_graph.in","r",stdin);
	freopen("haoi2021_graph.out","w",stdout);
	scanf("%d %d",&n,&m);
	ans[m] = n;
	for(int i = 1;i <= m;++ i)
		scanf("%d %d",&E[i].fir,&E[i].sec);
	for(int i = 1;i <= n;++ i)
		a[0][i][i] = a[1][i][i] = r[0][i][i] = r[1][i][i] = true;
	for(int i = m;i >= 1;-- i)
		add(i , E[i].fir , E[i].sec , 0),add(i , E[i].sec , E[i].fir , 1);
	for(int i = m - 1;~ i;-- i)
		ans[i] += ans[i + 1];
	for(int i = 0;i <= m;++ i)
		printf("%d ",ans[i]);
	return 0;
}