洛谷U187024 Cell Membrane 题解
本题为私题，作者 q779 （没错，就是本人！）
题目背景：
细胞就像一座化工厂，各个车间（细胞器）有条不紊，忙忙碌碌地生产着各种各样的化学物质，在领导细胞核同志的调控下，共同为化工厂的未来奋斗
工厂人员（化学物质）流动十分频繁，为了保证“工厂“的安全运作，工厂请了一位保安，叫细胞膜
他的日常工作就是检查每一位进出工厂的人
今天他生病了，所以想请你帮帮忙
题目描述：
保安给了你一张工厂人员名单表，（用于检查每个要进工厂上班的人是否为员工，不是员工则不能进入），每个人有唯一的编号 \(a_i\) （正整数）
由于员工的流动性，有一些员工会提前下班，一些下班或休息的员工也会回来继续加班
尊敬的领导细胞核同志要来视察，他会询问编号小于 \(x\) 且在上班的人有多少个
为了方便起见，我们可以把这些条件看作 \(m\) 个操作
输入数据将由以下格式给出
1 x表示编号为x的人想要进入工厂2 x表示编号为x的人离开了工厂3 x表示询问编号小于x且在上班的人的个数输入格式：
建议使用较快的输入输出。
第一行，给出人员名单表长度 \(n\) 和操作个数 \(m\)
第二行，\(n\) 个数，表示名单表（不保证有序）
接下来 \(m\) 行，给出形如
op x的操作，详见题目描述输出格式：
对于每个
3询问，都输出一行表示答案样例 #1
样例输入 #1
4 5 1 2 3 4 1 5 1 4 1 2 1 3 3 999样例输出 #1
3数据范围：
对于 \(30\%\) 的数据，保证 \(1\le n,m \le 1000,~1\le a_i \le 10^9\)
对于 \(100\%\) 的数据，保证 \(1\le n,m \le 2\times10^5,~1\le a_i \le 10^9\)
数据保证不在工厂上班的人不会出“工厂”，在工厂上班的人不会进工厂
这道题是我高一上学期出的，当时水平很菜只会出点基础题，评级最多普及-。
原来的 std 是维护一个 vector ，每次二分查找正确的位置，删除和修改
但实际上这个复杂度是错误的，因为 vector 的删除操作实际上是 \(\mathcal{O}(n)\) 的。
正解应该是把所有出现过的 \(a_i\) 离散化，然后用树状数组来维护。
时间复杂度 \(\mathcal{O}(n \log n)\)
代码：
// 2024年04月26日 01:02:04
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e5 + 15))
int n, m, len, a[N], b[N], o[N], q[N], tr[N]; char ck[N];
int lowbit(int x) { return x & (-x); }
void add(int x, int v) { for(int i = x; i <= len; i += lowbit(i)) tr[i] += v; }
int sum(int x, int r = 0){ for(int i = x; i; i -= lowbit(i)) r += tr[i]; return r; }
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i = 1; i <= n; i++) { cin >> a[i], b[i] = a[i]; }
for(int i = 1; i <= m; i++) { cin >> o[i] >> q[i], b[i + n] = q[i]; }
sort(b + 1, b + 1 + n + m); len = unique(b + 1, b + 1 + n + m) - b - 1;
for(int i = 1; i <= n; i++) {
ck[a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b] = true;
}
for(int i = 1; i <= m; i++)
{
int x = lower_bound(b + 1, b + 1 + len, q[i]) - b;
if(o[i] == 1) { if(ck[x]) add(x, 1); }
else if(o[i] == 2) { if(ck[x]) add(x, -1); }
else if(o[i] == 3) cout << sum(x - 1) << '\n';
}
return 0;
}如果有人好奇 std 是啥，那我就贴上来
// 2021年10月30日 22:38:54
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
template<typename T>inline void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>inline void write(T k)
{
if(k<0){pc('-');k=-k;}
if(k>9)write(k/10);
pc(k%10+'0');
}
#define MAXN (int)(2e5+5)
int n,Q;
unordered_map<int,bool>mp,vis;
vector<int> vec;
signed main()
{
// freopen("3.in","r",stdin);
// freopen("3.out","w",stdout);
read(n);read(Q);
for(int i=1,x; i<=n; i++)
read(x),mp[x]=1;
while(Q--)
{
int op,x;
read(op);read(x);
if(op==1&&mp[x])
{
vis[x]=1;
vec.insert(lower_bound(vec.begin(),vec.end(),x),x);
}
if(op==2)
{
vis[x]=0;
vec.erase(lower_bound(vec.begin(),vec.end(),x));
}
if(op==3)
{
int p=lower_bound(vec.begin(),vec.end(),x)-vec.begin();
write(p);pc('\n');
}
}
return 0;
}题外话：
虽说当时确实很菜，但我确实很努力。
可以说高一上学期是我高中最痛苦但又最快乐的时候。
痛苦的是平均每天睡眠都不超过4小时，快乐的是有很多有趣的同学。
虽然很多人都不再联系了，但是至少在他们眼中我的印象应该还不错吧。
从那以后，我的高中生活没有过能让我说的上快乐的，甚至没有一天让我感到不痛苦的。
很快又要回到学校了，希望“重生”后的我可以体验更多有趣的事情吧。
