$$WhyDidtheCowCrosstheRoadIIG$$

$$\&$$

$$WhyDidtheCowCrosstheRoadIIP$$

题目链接：

G：$luoguP6119$ \ $jozj6689$ \ $\mathrm{n}\mathrm{o}\mathrm{w}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}24073$

P：$luoguP3657$ \ $jozj6685$

题目

$FarmerJohn$ 饲养了 $N$ 种奶牛，编号从 $1$ 到 $N$。一些品种的奶牛和其他奶牛间相处良好，事实证明，如果两个品种的奶牛编号分别为 $a,b$，当 $|a-b|\le 4$ 时，这两个品种的奶牛能友好相处，否则不能友好相处。

一条长长的道路贯穿整个农场，道路的左侧有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场），道路的右侧也有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场）。为了让奶牛们安全穿过马路，$FarmerJohn$ 希望能在马路上画出一些人行道（牛行道？），要求这些人行道满足如下条件：

人行道从左侧的某个牧场出发，连接到右侧的某个牧场；
人行道连接的两个牧场的奶牛要能友好相处；
人行道不能在道路中间相交；
每个牧场只能与一条人行道相连。
你需要帮 $FJ$ 求出最多能有多少条人行道。

输入

输入第一行一个整数 $N$。

接下来 $N$ 行，每行一个整数 $a_i$，代表道路左侧第 $i$ 个牧场的奶牛品种编号。

接下来 $N$ 行，每行一个整数 $b_i$，代表道路右侧第 $i$ 个牧场的奶牛品种编号。

输出

输出最多能画多少条人行道。

样例输入

6
1
2
3
4
5
6
6
5
4
3
2
1

样例输出

5

数据范围

$G：1\le N\le 10^5$
$P：1\le N\le 1000$

思路

这道题还是树状数组。

我们先记录$b$序列中每个值的位置，然后我们依次枚举左侧的数，然后枚举能连的点，把这一条路作为最后一条路，（就是说只能在它的上面建路，其实就是前缀和），看最多能画多少条，再把这一条路加入树状数组中。

最后，我们只需要再输出前缀和的第$n$个（就是最后一个）就可以了。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

struct node{
	int to, go, op, next;
}e[800001];
int n, a[100001], b[100001], pl[100001], an[100001], bit[100001];
queue<int>q;

int find(int now) {//单点查值
	int re = 0;
	for (; now; now -= (now & -now))
		re = max(re, bit[now]);
	return re;
}

void build(int x, int y) {//单点加值
	for (; x <= n; x += (x & -x))
		if (y > bit[x]) bit[x] = y;
			else return ;
}

int main() {
//	freopen("nocross.in", "r", stdin);
//	freopen("nocross.out", "w", stdout);
	
	scanf("%d", &n);//读入
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);//读入
	for (int i = 1; i <= n; i++) {
		scanf("%d", &b[i]);//读入
		pl[b[i]] = i;//记录b序列中每个值的位置
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = max(1, a[i] - 4); j <= min(n, a[i] + 4); j++)//可以连边的点
			an[j] = find(pl[j] - 1);//单点求值
		for (int j = max(1, a[i] - 4); j <= min(n, a[i] + 4); j++)
			build(pl[j], an[j] + 1);//单点加值（因为加上了这条边，所以要加一）
	}
	
	printf("%d", find(n));//输出
	
//	fclose(stdin);
//	fclose(stdout);
	
	return 0;
}