题意
网上常有人说：看 XX 只能度过一个相对成功/失败的人生。不妨假设把这个句式套用在“参加睿抗比赛“以及“玩手机游戏”上，那么有：
- “参加睿抗比赛”必然比“不参加睿抗比赛”要成功；
- “玩手机游戏“必然比“不玩手机游戏”要失败。
现在有 N 个人，已知这些人自己填写的是否参加了睿抗比赛以及是否玩手机游戏的情况，以及他们实际上的成功程度的排序顺序，请问最少有多少人在填写情况时说谎了？
输入格式:
输出第一行为一个正整数 T (1≤T≤5)，表示数据组数。
每组数据第一行是一个正整数 N (1≤N≤105)，表示总共的人数。
接下来的 N 行，第 i 行有两个数字 Ai,Bi，表示第 i 位参赛选手是否参加了睿抗比赛以及是否玩手机游戏，0 为没有参加/没有玩，1 为参加了/玩了。
最后一行有 N 个数，为一个选手编号 1 到 N 的排列，表示选手成功程度的排序。排序顺序从最成功到最失败。
选手编号从 1 开始。
输出格式:
对于每组数据，输出一个整数，表示最少的说谎人数。
输入样例:
3
5
1 0
1 0
0 0
0 0
0 1
1 2 3 4 5
5
1 0
1 0
0 0
0 0
0 1
5 4 3 2 1
5
1 0
0 1
0 0
0 1
1 1
4 2 1 3 5输出样例:
0
3
2题解
首先算得分，只有两种事情，打比赛+1，没看手机+1，否则为0 也就是只有三种得分 2，1，0
按照输入可以直接算出得分
得到当前得分后，要怎么和给出的真正排名联系起来?
先对给出的数据做排序，得到现有情况下的排名，注意由于等级只有三种，排名是会重复的
在此之后，按照现有的排名结果对真正的排名结果做排名，得到错误的排名结果在真正排名结果中的映射，只要这个映射的相对位置和真正排名的一样，这一段排名就可以是正确的，而真正的排名中从第一名开始往后排名递增，如果映射的结果也是不减的序列，那么其相对位置就正确。
求最长上升子序列
由于给出的数据n^2的求法会超时，用二分加速，注意不是严格上升而是不减，应该是每次找最后一个尾数小于等于该数的子序列，更新这个序列长度+1的子序列尾数
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
void solve()
{
int t;
cin >> t;
while(t --)
{
int n;
cin >> n;
bool a[N], b[N];
int ans[N] = {};
int res[N] = {};
map<int, int> m;
//一共三种排名
for(int i = 1; i <= n; i ++)
{
cin >> a[i] >> b[i];
b[i] = 1 - b[i];
ans[i] += a[i] + b[i];
if(ans[i] == 1) m[i] = 2;
else if(ans[i] == 2) m[i] = 1;
else m[i] = 3;
}
int q[N] = {};
for(int i = 1; i <= n; i ++)
{
cin >> res[i];
res[i] = m[res[i]];
}
//此时依据所给信息得到序号对应的排名，如果没错，意味着相对位置是对的，也就是要求最长上升子序列
int len = 0;
for(int i = 1; i <= n; i ++)
{
int l = 0, r = len;
//最后一个小于等于这个数的序列
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] <= res[i]) l = mid;
else r = mid - 1;
}
q[r + 1] = res[i];
len = max(len, r + 1);
}
cout << n - len << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
return 0;
}