真让我给干出来了我去。已加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。

首先考虑 $k=0$ 的情况，我们在置换环上考虑，每次操作为选择若干对不交点对，并让每对点交换出边，最终目标是全部为自环。

首先考虑计算 $f(A)$。

引理：对于一个 $n(n\ge 3)$ 元环，可以一次操作将其变为若干二元环和自环。

证明：不妨将 $n$ 元环按有向边方向编号 $1$ 到 $n$。那么构造方案 $(1,n),(2,n-1),...$ 即可（若 $n$ 为奇数会剩下一个点不操作），证毕。

而二元环可以一步变为两个自环，于是 $f(A)\le 2$。具体的，若原图只有自环，则 $f(A)=0$；若原图只有二元环，则 $f(A)=1$；否则，$f(A)=2$。

接下来考虑计算 $g(A)$。

对于 $f(A)\le 1$ 的情况显然 $g(A)=1$。下面只考虑 $f(A)=2$ 的情况。

通过大量手玩，我们可以发现多元环的变化流程都能被概括为：$n (n\ge 3)$ 元环 $\to$ 若干二元环 $\to$ 若干自环。

由于第二步的操作是固定的，我们注重考虑第一步的方案数。首先注意到在两个环长不同的环间操作一定不能全部拆解为二元环，那么我们只需考虑在同种环间的操作。

对于 $n(n\ge 3)$ 元环，“拆解”有两种形式：

1. 一个 $n$ 元环自主拆解，有 $n$ 种方案。对于 $n$ 为奇数，同引理的证明的构造方式，可任选不操作的点。对于 $n$ 为偶数，引理证明的构造有 $\frac{n}{2}$ 种方案，再加上 $(2,n),(3,n-1),...$ 这种构造（$1$ 和 $\frac{n}{2}+1$ 都不操作）也有 $\frac{n}{2}$ 种方案，故共有 $n$ 中方案。

2. 两个 $n$ 元环配对，有 $n$ 种方案。记两个环的编号分别为 $x_i,y_i$，那么构造操作 $(x_1,y_n),(x_2,y_{n-1}),...,(x_n,y_1)$ 即可，由于 $y$ 可以旋转 $n$ 次，故共有 $n$ 种方案。

那么如果我们有 $m$ 个 $n$ 元环，方案数记作 $f_{n,m}$。考虑最后一个环是否去配对，有递推：

$$f_{n,m}=n[f_{n,m-1}+(m-1)f_{n,m-2}]$$

对于二元环，由于它不需要专门去变为二元环，它的“拆解”有三种形式：

1. 第一步变为自环，第二步不操作。

2. 第一步不操作，第二步变为自环。

3. 第一步找另一个二元环配对，操作后仍为两个二元环，第二步变为自环。

通过计算发现，最终的式子与 $n\ge3$ 时的形式一样。

对于自环，与 $n\ge3$ 时的情况类似，最终的式子也一样，留做练习。

由于每种环长是独立的，对每种环长计算方案数并相乘即为答案。至此，我们得到了一个复杂度 $O(nk!)$ 的做法。

接下来的优化是相对容易的。

观察每个未知点所在的联通块，它一定是一条链，其中未知点为链尾，其他未知点只能连向链首。那么我们可以将它视作一个带点权的大点，这样就转化为了 $k$ 个大点之间相互的连边情况。

注意到我们只关心最终环的集合，而不关心其内部的连边方式，那么我们只需要枚举这 $k$ 个大点的划分即可，共有 $bell(k)\le 4213597$ 种，可以接受。

考虑一种划分 $P$，那么其对应排列的方案数为 $\prod_{x\in P}(x-1)!$，累加答案时作为附加系数即可。

对于这新形成的 $O(k)$ 的环，我们考虑直接去维护它们的加入。具体的，对于原图中完整的环，它们一定不包含未知点，所以是固定的，我们预处理它们的答案，以及每个环长的出现次数 $cnt_i$。当加入一个新环时，直接将答案乘上 $\frac{f_{i,cnt_i+1}}{f_{i,cnt_i}}$ 即可。由于我们不能迅速求一个 $f_{i,j}$，但注意到新的 $cnt_i' \le cnt_i+k$，那么我们只需要预处理出 $f_{i,cnt_i},...,f_{i,cnt_i+k}$ 即可，由于我们可以递推求 $f$，那么这是简单的。

至此，我们得到了复杂度 $O(bell(k)k+nk)$ 的做法。

$\mathrm {Subtask}1: n\le 5$。

直接 $\mathcal O(n^m)$ 爆搜，暴力判强连通即可。

$\mathrm{Subtask} 2: n\le 15$。

这个我没有写，不知道对不对。

考虑状压 dp。

思考强连通图的形成过程，一定是从 $1$ 所在的强连通分量中的某个点出发，走到某些还不在这个强连通分量的点，然后走回 $1$ 所在的强连通分量中的某个点。

并且，我们并不关心起点终点具体是那个点。

据此，设 $f(S,t)$ 表示 $t$ 秒后 $1$ 所在的强连通分量为 $S$ 的方案数。

转移大概就是设 $g(S,t)$ 表示经过 $t$ 秒经过了 $S$ 中这些点的方案数，然后转移做一个二维的合并：$f(S_1,t_1)\times g(S_2,t_2)\to f(S_1\cup S_2, t_1+t_2)[S_1\cap S_2 = \emptyset]$。

复杂度 $\mathcal O(3^n \mathrm{poly}(n))$。

$\mathrm{Subtask 3}:n\le 300$。

考虑优化状压 dp。两种方法优化到正解：重构 dp 状态，分步转移。两者殊途同归。

因为我们并不关心 $1$ 所在的强连通分量具体是啥，所以设 $f(i,j,k)$ 表示 $i$ 次操作后 $1$ 所在的强连通分量大小为 $j$，目前往外扩展了 $k$ 个新点的方案数。

初始状态 $f(0,1,0)=1$。三种转移，分别对应走回 $1$ 所在的强连通分量，走一个新点，走到一个还在构建的点。

$$f(i,j,k)\times j\to f(i+1,j+k,0)$$

$$f(i,j,k)\times (n-j-k)\to f(i+1,j,k+1)$$

$$f(i,j,k)\times k\to f(i+1,j,k)$$

答案就是 $f(m,n,0)$。

注意！！！这里有个大坑点！！！

模数是 $10^9 + 7$ 而不是 $998244353$。有人缺省源里 $\mathrm{mod}=998244353$ 调了一年。

考虑线段树，显然操作 1,3,4 均能用线段树解决。

操作 2 并不好处理，如果直接硬除，操作复杂度为单次 $O(n)$。

考虑将其转化为便于线段树维护的操作。

对于区间 $[l,r]$，记 $p$ 为 $[l,r]$ 间的最大值，$q$ 为 $[l,r]$ 的最小值。

若 $p-\lfloor \frac{p}{d}\rfloor=q-\lfloor \frac{q}{d}\rfloor$，那么此时可以将这个操作转化为区间加法。

原因不难理解，显然 $a_i-\lfloor \frac{a_i}{d}\rfloor$ 单调不降，如果满足上述条件，显然 $a_i-\lfloor \frac{a_i}{d}\rfloor$ 都相等，那么直接作整体加（实际上是减）即可。

这种操作的复杂度如何？

根据直觉，其实会发现每次 2 操作 $a_i$ 减小得比 $\lfloor\frac{a_i}{d} \rfloor$ 快得多，主观上时间复杂度并不高。

严谨的时间复杂度证明需要势能分析。

（注：此处贺了 LOJ 讨论区的证明，加了点我自己的理解，大概率是错的，看个乐就行）

不妨设 $n,v$ 同阶。

定义势能为 $\sum \log_2 (|a_i-a_{i-1}|)$。

显然，开始时势能为 $O(n\log n)$。

一次区间加后，区间 $[l,r]$ 内部势能不变，两端各增加 $O(\log_2 n)$。总体来说变化量可以忽略（其实此时的势能为 $O((n+q)\log_2 n)$）。

每个势能的连续段在树上被分为 $\log$ 段，而每次区间除法操作珂以使两个相邻连续段之间的势能减 1。

相当于用 $\log$ 的代价减去了 1。

那么总的时间复杂度即为 $O((n+q)\log ^2 n)$。

#include <bits/stdc++.h>
typedef long long ll;
const ll INF = 1e18;

int read() {
    int s = 0,f = 1;
    char c = getchar();
    for(;c < '0'||c > '9';c = getchar())
        if(c == '-')f = -1;
    for(;c >= '0'&&c <= '9';c = getchar())
        s = (s << 1) + (s << 3) + (c ^ '0');
    return s * f;
}

const int maxn = 1e5 + 5;
int n,m;

int ls[maxn << 2],rs[maxn << 2];
ll sum[maxn << 2],lz[maxn << 2],maxv[maxn << 2],minv[maxn << 2];

void pushup(int i) {
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
    maxv[i] = std::max(maxv[i << 1] , maxv[i << 1 | 1]);
    minv[i] = std::min(minv[i << 1] , minv[i << 1 | 1]);
    return ;
}

void pushdown(int i) {
    if(!lz[i])return ;
    lz[i << 1] += lz[i];
    lz[i << 1 | 1] += lz[i];
    minv[i << 1] += lz[i];
    minv[i << 1 | 1] += lz[i];
    maxv[i << 1] += lz[i];
    maxv[i << 1 | 1] += lz[i];
    sum[i << 1] += 1ll * (rs[i << 1] - ls[i << 1] + 1) * lz[i];
    sum[i << 1 | 1] += 1ll * (rs[i << 1 | 1] - ls[i << 1 | 1] + 1) * lz[i];
    lz[i] = 0;
    return ;
}

void build(int i,int l,int r) {
    ls[i] = l;
    rs[i] = r;
    if(l == r) {
        sum[i] = maxv[i] = minv[i] = read();
        return ;
    }
    int mid = l + r >> 1;
    build(i << 1 , l , mid);
    build(i << 1 | 1 , mid + 1 , r);
    pushup(i);
    return ;
}

void modify(int i,int l,int r,int k) {
    if(ls[i] >= l&&rs[i] <= r) {
        sum[i] += 1ll * k * (rs[i] - ls[i] + 1);
        lz[i] += k;
        maxv[i] += k;
        minv[i] += k;
        return ;
    }
    if(ls[i] > r||rs[i] < l)return ;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    if(l <= mid)modify(i << 1 , l , r , k);
    if(r > mid)modify(i << 1 | 1 , l , r , k);
    pushup(i);
    return ;
}

void Maintain(int i,int l,int r,int k) {
    if(ls[i] >= l&&rs[i] <= r) {
        int x = maxv[i] - (int)std::floor((double)(1.0 * (double)maxv[i] / (double)k));
        int y = minv[i] - (int)std::floor((double)(1.0 * (double)minv[i] / (double)k));
        if(x == y) {
            sum[i] -= 1ll * (rs[i] - ls[i] + 1) * x;
            lz[i] -= x;
            maxv[i] -= x;
            minv[i] -= x;
            return ;
        }
    }
    if(ls[i] > r||rs[i] < l)return ;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    if(l <= mid)Maintain(i << 1 , l , r , k);
    if(r > mid)Maintain(i << 1 | 1 , l , r , k);
    pushup(i);
    return ;
}

ll Querymin(int i,int l,int r) {
    if(ls[i] >= l&&rs[i] <= r)return minv[i];
    if(ls[i] > r||rs[i] < l)return INF;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    ll s = INF;
    if(l <= mid)s = std::min(s , Querymin(i << 1 , l , r));
    if(r > mid)s = std::min(s , Querymin(i << 1 | 1 , l , r));
    return s;
}

ll Querysum(int i,int l,int r) {
    if(ls[i] >= l&&rs[i] <= r)return sum[i];
    if(ls[i] > r||rs[i] < l)return 0;
    pushdown(i);
    int mid = ls[i] + rs[i] >> 1;
    ll s = 0;
    if(l <= mid)s += Querysum(i << 1 , l , r);
    if(r > mid)s += Querysum(i << 1 | 1 , l , r);
    return s;
}

int main() {
    n = read();
    m = read();

    build(1 , 1 , n);

    while(m --) {
        int op = read(),l = read() + 1,r = read() + 1,k;
        switch(op) {
            case 1: {
                k = read();
                modify(1 , l , r , k);
                break ;
            }
            case 2: {
                k = read();
                Maintain(1 , l , r , k);
                break ;
            }
            case 3: {
                printf("%lld\n",Querymin(1 , l , r));
                break ;
            }
            case 4: {
                printf("%lld\n",Querysum(1 , l , r));
                break ;
            }
        }
    }
    return 0;
}

注意：这道题的“先到先得”是让我们按照飞机到达的时间升序排序。

首先发现，国内和国外可以分开处理，最后枚举统计。

这就要求我们对国内和国外求出分配 $i$ 个廊桥时的飞机数。

观察到一个性质：如果分配 $i$ 个廊桥时飞机 $j$ 有位置，则分配 $i+1$ 个廊桥时飞机仍有位置。

观察一下样例的那张图，手玩一下样例，不难发现这个性质。

那么我们只需要求出每个飞机 $j$ 所需的最小廊桥数，再用前缀和统计即可。

不妨把廊桥按照 $1\sim m$ 标号，用两个优先队列维护空闲和非空闲的廊桥，设为 $q_1,q_2$。

当遍历到一个新飞机，弹出 $q_2$ 中飞走的飞机，把这些廊桥放入 $q_1$，再从 $q_1$ 取出最小的廊桥。

国内国外的飞机都处理一遍，用前缀和维护一下，然后枚举即可。

时间复杂度 $O(N\log N)$。

// Problem: #3542. 「CSP-S 2021」廊桥分配
// Contest: LibreOJ
// URL: https://loj.ac/p/3542
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
const int maxn = 1e5 + 5;
typedef pair<int,int> pii;
struct node {
	int x,y;
	node() {
		x = y = 0;
	}
}a[maxn],b[maxn];
int n,m,k;
int sum1[maxn],sum2[maxn];
priority_queue<pii,vector<pii>,greater<pii> > q;
priority_queue<int,vector<int>,greater<int> > s;
int main() {
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
	scanf("%d %d %d",&n,&m,&k);
	for(int i = 1;i <= m;++ i) {
		scanf("%d %d",&a[i].x,&a[i].y);
	}
	sort(a + 1 , a + 1 + m , [&](const node& p,const node& q) {
		return p.x < q.x;
	});
	for(int i = 1;i <= k;++ i) {
		scanf("%d %d",&b[i].x,&b[i].y);
	}
	sort(b + 1 , b + 1 + k , [&](const node& p,const node& q) {
		return p.x < q.x;
	});
	while(!q.empty())q.pop();
	while(!s.empty())s.pop();
	for(int i = 1;i <= m;++ i)s.push(i);
	for(int i = 1;i <= m;++ i) {
		for(;!q.empty()&&q.top().fir < a[i].x;q.pop())s.push(q.top().sec);
		int ans = s.top();
		s.pop();
		++ sum1[ans];
		q.push(mp(a[i].y , ans));
	}
	while(!q.empty())q.pop();
	while(!s.empty())s.pop();
	for(int i = 1;i <= k;++ i)s.push(i);
	for(int i = 1;i <= k;++ i) {
		for(;!q.empty()&&q.top().fir < b[i].x;q.pop())s.push(q.top().sec);
		int ans = s.top();
		s.pop();
		++ sum2[ans];
		q.push(mp(b[i].y , ans));
	}
	for(int i = 1;i <= n;++ i)sum1[i] += sum1[i - 1],sum2[i] += sum2[i - 1];
	int ans = 0;
	for(int i = 0;i <= n;++ i)ans = max(ans , sum1[i] + sum2[n - i]);
	printf("%d\n",ans);
	return 0;
}