# 11072: 【原1072】小X的生物实验

### 题目描述

author: 寿鹤鸣 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1072

## Hint

60%的测试数据中：$$1 \leq N \leq 1000$$

100%的测试数据中：$$1 \leq N \leq 20000$$

## Sample Input

2
1 1 2 2 1 1 2 1 2 2
1 2 2 2 1 1 2 2 1 1


## Sample Output

7


## FineArtz's solution

/* 小X的生物实验 */
#include <iostream>
using namespace std;

int pos[1000005][5], a[1000005];
int n;

inline int lowbit(int x){
return x & (-x);
}

void change(int x, int y){
while (x <= n){
a[x] = max(a[x], y);
x += lowbit(x);
}
}

int find(int x){
int ret = 0;
while (x != 0){
ret = max(ret, a[x]);
x -= lowbit(x);
}
return ret;
}

int main(){
cin >> n;
n *= 5;
for (int i = 1; i <= n; ++i){
int x, j = 0;
cin >> x;
while (pos[x][j])
++j;
pos[x][j] = i;
}
int ans = 0;
for (int i = 1; i <= n; ++i){
int x;
cin >> x;
for (int j = 4; ~j; --j){
int t = find(pos[x][j] - 1) + 1;
ans = max(t, ans);
change(pos[x][j], t);
}
}
cout << ans << endl;
return 0;
}


## yyong119's solution

#include <iostream>
#define MAX_N 20005
using namespace std;
int n;
int a[MAX_N * 5], tree[MAX_N * 5];
int map[MAX_N][6];
char ch = getchar(); int flag = 1, res = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
return res * flag;
}
void update(int x, int num) {
for (; x <= n * 5; x += x & -x)
tree[x] = max(tree[x], num);
}
int query(int x) {
int res = 0;
for (; x; x -= x & -x)
res = max(res, tree[x]);
return res;
}
int main() {