1. 信息传递

AKP和WWF住在河的两岸，他们在河的两岸都建了n座房子，而且恰巧都是正对着建的，如下所示：

AKP:  房子1                       房子2                 房子3                    房子4

=================河===============流==============

WWF:  房子3                    房子2                 房子4                     房子1

他们对于房子的编号不一样，可能AKP的房子1对应着WWF的房子3，等等，但是每个人的房子编号都是1~n的一个排列。为了方便，我们假定他们房子间隔相同。

他们在河中铺下了光缆来连接各自相同编号的房子，进行信息传递。为了信息传递的方便，他们需要知道：从总共n条光缆中选出最多的光缆，使得这几条光缆之间两两相交。

【题解】

转化为最长下降子序列后用$O(nlogn)$的方法解决。

# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>
 
using namespace std;

const int M = 200010;
int n;
int A[M], B[M];
int ta[M], tb[M], a[M], f[M], c[M];

int main() {
 
 	freopen("message.in", "r", stdin);
 	freopen("message.out", "w", stdout);
 	
    scanf("%d", &n);
     
    for (int i=1; i<=n; ++i)
        scanf("%d", &A[i]), ta[A[i]] = i;
     
    for (int i=1; i<=n; ++i)
        scanf("%d", &B[i]), tb[B[i]] = i;
         
    for (int i=1; i<=n; ++i)
        a[i] = tb[A[i]]; 

    int ans;
    f[1] = 1, ans = 1;
    c[1] = 1;
    a[n+1] = -2147483647; for (int i=2; i<=n; ++i) c[i] = n+1;
    for (int i=2; i<=n; ++i) {
        int l=1, r=ans, anst = 0;
        while(1) {
            if(r-l<=3) {
                for (int j=r; j>=l; --j)
                    if (a[c[j]] > a[i]) {
                        anst = c[j];
                        break;
                    }
                break;
            }
            int mid = l+r>>1;
            if(a[c[mid]] > a[i]) l = mid;
            else r = mid;
        }
        f[i] = f[anst] + 1;
        if(a[c[f[i]]] < a[i])
            c[f[i]] = i;
        ans = max(ans, f[i]);
    } 
     
    printf("%d\n", ans);
     
    return 0;
}

2. 树上问题

AKP觉得WWF对树上的问题不大熟悉，于是向他提出了一个树上的问题。

首先AKP画出了一个n个节点的有根树（其中根为1号点），他对于其中一些节点很喜爱，于是就在这个节点上标记一下，当然过一会儿他可能就忘了他标记过的节点，所以一个节点可以被重复标记。在最开始，有且仅有1号节点上有标记。

AKP有q次操作，操作类型有两种：

1. 选取一个点，把它标记一下。

2. 选取一个点，询问它的祖先中（包括自己），离它最近的被标记过的节点是哪一个。

现在，AKP要请你对于每一个2操作，输出你计算出的答案。

$n,q \leq 1500000$

【题解】

离线询问逆序做，并查集维护即可。

# include <stdio.h>
// # include <bits/stdc++.h>

using namespace std;

const int N = 2000010;
int n, q;
int opt[N], x[N];
int fa[N], f[N];
int tot = 0, next[N<<1], head[N], to[N<<1], tag[N];
int ans[N], an = 0;

int read() {
    int n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' ||  a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

inline int getf(int x) {
	return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

inline void add(int u, int v) {
	++tot;
	next[tot] = head[u];
	head[u] = tot;
	to[tot] = v;
}

inline void dfs(int x, int father=0) {
	if(father) f[x] = father;
	for (int i=head[x]; i; i=next[i]) 
		if(to[i] != father) 
			dfs(to[i], x);
}

int main() {
	
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	
	n = read(), q = read();
	for (int i=1, u, v; i<n; ++i) {
		u = read(), v = read();
		add(u, v);
		add(v, u);
	}
	
	dfs(1);
	
	tag[1] = 1;
	for (int i=1; i<=n; ++i) fa[i] = i;
	
	for (int i=q; i>=1; --i) {
		opt[i] = read(), x[i] = read();
		if(opt[i] == 1) tag[x[i]]++;
	}
	
	for (int i=2; i<=n; ++i) {
		if(tag[i] != 0) continue;
		int fu = getf(i), fv = getf(f[i]);
		if(fu != fv) fa[fu] = fv;
	}
	
	for (int i=1; i<=q; ++i) {
		if(opt[i] == 1) {
			tag[x[i]] --;
			if(tag[x[i]] == 0) {
				int fu = getf(x[i]), fv = getf(f[x[i]]);
				if(fu != fv) fa[fu] = fv;
			}
		} else {
			ans[++an] = getf(x[i]);
		}
	}
	
	for (int i=an; i>=1; --i) printf("%d\n", ans[i]);
	
	return 0;
}

3. 对抗比赛

AKP和WWF要进行一场对抗比赛。

AKP有n名记者，WWF也有n名记者，他们要比赛谁跑得快。AKP的每名记者有速度值，WWF的每名记者有速度值。记者们一共进行n轮比赛，每轮AKP选出一名记者，WWF选出一名记者进行比赛，速度值大的记者所在的一方获得一轮的胜利，胜利的一方获得1分，失败的一方不获得分数，一名记者只能比赛一次。在n轮比赛过后，AKP想知道，如果他和WWF的分差（取绝对值）在之间的话，那么一共有多少种方案？由于AKP好学，所以他一共问了q次问题。

方案数对于998244353取模。

$n,q \leq 3000$。

【题解】

首先，$f_{i,j}$表示到了第i个，AKP一定得了j分（其他可得可不得）的方案。

那么令$g_i$表示AKP得到至少i分的方案，$g_i = f_{n,i} \times (n-i)!$

令$h_i$表示AKP恰好得到$i$分的方案，$h_i = g_i - C_{j}^{i} \times \sum_{j>i}h_j$。

逆推即可。复杂度$O(n^2+qn)$。

# include <stdio.h>
# include <algorithm>
 
using namespace std;
 
const int M = 3010;
int n, a[M], b[M], q, f[M][M], hv[M], g[M], h[M];
const int mod = 998244353;
 
int fac[M], inv[M];
 
inline int pwr(int x, int y) {
    int ret = 1;
    while(y) {
        if(y&1) ret = 1ll * ret*x % mod;
        x = 1ll * x*x % mod;
        y = y/2;
    }
    return ret;
}

inline void cadd(int &a, int b) {
    a = (a+b) % mod;
    a = (a+mod) % mod;
}
 
inline void csub(int &a, int b) {
    b = -b;
    b = (b+mod) % mod;
    cadd(a, b);
}
 
inline int C(int n, int k) {
    return 1ll * fac[n] * inv[k] % mod * inv[n-k] % mod;
}
 
int main() {
	
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	
    scanf("%d%d", &n, &q);
    fac[0] = 1;
    for (int i=1; i<=n; ++i)
        fac[i] = 1ll * fac[i-1] * i % mod;     
    for (int i=0; i<=n; ++i)
        inv[i] = pwr(fac[i], mod-2);
      
    for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
    for (int i=1; i<=n; ++i) scanf("%d", &b[i]);
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    for (int i=1; i<=n; ++i) hv[i] = upper_bound(b+1, b+n+1, a[i]) - b - 1;
    
    f[0][0] = 1;
    for (int i=1; i<=n; ++i)
        for (int j=0; j<=i; ++j) {
            f[i][j] = f[i-1][j];
            if(j!=0 && hv[i]-(j-1)>0) cadd(f[i][j], 1ll * f[i-1][j-1] * (hv[i]-(j-1)) % mod);
        }
     
    for (int i=0; i<=n; ++i)
        g[i] = 1ll * f[n][i] * fac[n-i] % mod;
    //for (int i=0; i<=n; ++i) cerr<<i<<":"<<f[n][i]<<"\n";
    for (int i=n; i>=0; --i) {
        h[i] = g[i];
        for (int j=i+1; j<=n; ++j)
            csub(h[i], 1ll * h[j] * C(j, i) % mod);
    }
	
	for (int i=1, L, R; i<=q; ++i) {
		int ans = 0;
		scanf("%d%d", &L, &R);
		/*
		for (int j=L; j<=R; ++j) {
			if((n+j)&1) continue;
			int A = (n+j)/2, B = (n-j)/2;
			if(A!=B) cadd(ans, (1ll * h[A] + h[B]) % mod);
			else cadd(ans, 1ll * h[A] % mod);
		}
		*/
		for (int j=0; j<=n; ++j) {
			int k = n-j;
			if(abs(j-k)>=L && abs(j-k)<=R)
				cadd(ans, h[j]);
		}
		printf("%d\n", ans);
	}
    
    return 0; 

}