START198B——Restricted Removals（字符串） · znzryb
## 思路讲解
[https://www.codechef.com/viewsolution/1179874822](https://www.codechef.com/viewsolution/1179874822)
我们的贪心做法用AI树状数组给过去了（其实我也想到了，但是我觉得复杂度也太离谱了吧，就没试）。
my solution is a kind of greedy.
It is not difficult to observe that delete the last element matched is the best, because it affect the least elements.
so just do it.
certainly, using vector or list can not go through all tests.
but if you using fenwick tree which can find the kth element, all problems will be solved.
## AC代码
[https://www.codechef.com/viewsolution/1179893708](https://www.codechef.com/viewsolution/1179893708)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+9; // 1e18+9也是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
inline void __();
// by znzryb
// 普通的单点修改区间查询树状数组，含有查找第K个空位，第K个元素的功能
// https://www.codechef.com/viewsolution/1179893708 第K个元素测试
// 第K个空位的测试应该是一道abc的题目，但是当时没保存
struct BIT {
vector < ll > tr;
int n;
inline int lowbit(int x) {
return x & (-x);
}
BIT(int ln) { // 构造+初始化函数
n = ln;
tr.resize(n + 5, 0);
}
inline void add(int p, int x) {
if (p == 0) return;
while (p <= n) {
tr[p] += x;
p += lowbit(p);
}
}
inline ll query(int l, int r) {
ll lres = 0, rres = 0;
l -= 1;
while (l > 0) {
lres += tr[l];
l -= lowbit(l);
}
while (r > 0) {
rres += tr[r];
r -= lowbit(r);
}
return rres - lres;
}
inline int findkth(int k) { // 找到第k个元素，当然应当是要求只能出现0和1
int x = 0,sum=0;
for(int i=__lg(n);~i;--i){
x+=1<<i;
if(x>=n || sum+tr[x]>=k){
x-=1<<i;
}else{
sum+=tr[x];
}
}
return x + 1; // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新元素出现的地方
}
inline int kthspace(int k) { // 找到第k个空位，当然应当是要求只能出现0和1
int cx = 0;
for (int i = 1 << 20; i > 0; i >>= 1) { // 这个你可以理解为不断缩小步长的搜索
if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
// lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
k -= lowbit(cx + i) - tr[cx + i];
cx += i;
}
}
return cx + 1; // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
}
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
inline void __(){
cin>>N>>M;
vll A(N+5),B(M+5);
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,M){
cin>>B[i];
}
BIT tr(max(N,M)+5);
FOR(i,1,N){
tr.add(i,1);
}
ll n=N;
// vb vis(N+5);
while (n) {
ll lim=min(M,n);
bool ok=false;
ROF(i,lim,1){
ll pos=tr.findkth(i);
if(A[pos]==B[i]){
tr.add(pos,-1);
ok=true;
break;
}
}
if(!ok) break;
n--;
}
cout<<n<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1179893708
1
3 2
1 0 1
1 1
1
3 2
0 0 1
0 0
*/
```
:::
## 心路历程（WA，TLE，MLE……）