题目描述
你们wyh学长小时候住在河边，因为周围的生态环境非常好，所以经常会有天鹅浮在湖面上，每只天鹅都长得不一样，它们偶尔排成一排，偶尔分散开，偶尔也会去其他河畔，wyh学长为了统计它们的个数，编了一个程序赋予它们一个“萌”值，但是这些天鹅很不听话，一会儿会从别的地方游过来一两只，一会儿又会在统计过程中游走一两只，现在请你帮他完成统计任务。
输入描述:
共有T(T<=10)组数据，每组数据第一行为两个数 N, M (N，M <= 500000)，代表有N只天鹅和M次操作，接下来一行是N个数字，下面M行首先会输入一个字符串S，接着会有三类操作，如果S是“insert”，接着输入一个正整数a，代表插入一只“萌”值为a的天鹅，如果S是“delete”，接着输入一个正整数a，代表删除一只“萌”值为a的天鹅，如果S是“query”，接着输入一个正整数k，代表查询“萌”值第k大的天鹅。萌值为[1,1000000000]，并且保证一定存在第k大
输出描述:
对应每次询问，输出询问结果。
示例
输入:
1
5 4
6 4 2 9 1
query 2
insert 7
delete 6
query 2
输出:
6
7
题解
这题使用vector进行存储数据,sort排序过后,插入/删除/查询都可二分进行,写题解的意义在哪儿呐?
vector 的元素的删除
#include<iostream> #include<algorithm> #include<vector> #define int long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N = 1e6+10; int a[N]; int sum[N<<2]; void sol() { vector<int>ve; int n,m,x; string s; cin>>n>>m; rep(i,1,n) cin>>x,ve.push_back(x); sort(ve.begin(),ve.begin()+n); while(m--) { cin>>s; if(s == "insert") { cin>>x; // lower_bound(起始元素地址,终止元素后面的地址,比较值) ve.insert(lower_bound(ve.begin(),ve.end(),x),x); }else if(s == "delete") { cin>>x; // erase 删除的是某一个地址 ve.erase(lower_bound(ve.begin(),ve.end(),x)); }else if(s == "query"){ cin>>x; cout<<ve[ve.size()-x]<<endl; } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin>>T; while(T--) sol(); return 0; }
