set & vector

STL
  1. set
  2. vector
  3. 1 【bzoj 3224】Tyvj 1728 普通平衡树
  4. 2 【bzoj 1208】[HNOI2004]宠物收养所
  5. 3 【bzoj 1588】[HNOI2002]营业额统计
  6. 4 【bzoj 3173】[Tjoi2013]最长上升子序列

STL大法好
set和vector有点像,所以一起写了

set

set:不可重复
multiset:可重复

基本操作: 1. begin() : 返回第一个元素的位置 2. end() : 返回最后一个元素的位置 3. rbegin() : 返回倒数第一个的位置,值与end()相同 4. rend() : 返回倒数最后一个的位置,值与rbegin()相同 5. clear() : 删除set容器中的所有的元素 6. empty() : 判断set容器是否为空 7. max_size() : 返回set容器可能包含的元素最大个数 8. size() : 返回当前set容器中的元素个数 9. count() : 某个键值出现的次数 10. find() : 返回给定值值得定位器,如果没找到则返回end()

插入: 1. insert(key_value) : 将key_value插入到set中 ,返回值是pair < set < int > :: iterator , bool > ,bool标志着插入是否成功,而iterator代表插入的位置,若key_value已经在set中,则iterator表示的key_value在set中的位置。 2. inset(first,second) : 将定位器first到second之间的元素插入到set中,返回值是void.

删除: 1. erase(iterator) : 删除定位器iterator指向的值 2. erase(first,second) : 删除定位器first和second之间的值 3. erase(key_value) : 删除键值key_value的值

前后: 1. upper_bound(key_value) : 大于key_value的定位器 2. lower_bound(key_value) : 大于等于key_value的定位器 3. --upper_bound(key_value) : 小于等于key_value的定位器 4. --lower_bound(key_value) : 小于key_value的定位器

1
2
3
4
5
set<int>::iterator iter;
//遍历
for(iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter);
//查找
if((iter=s.find(2))!=s.end()) printf("%d ",*iter);

vector

在vector中,如果一个函数中需要两个迭代器,一般后一个都不包含.

  1. 创建vector对象 : vector<int> vec;
  2. 尾部插入数字 : vec.push_back(a);
  3. 使用下标访问元素 : cout<<vec[i]<<endl;记住下标是从0开始的。
  4. 使用迭代器访问元素 : for(vector<int>::iterator iter=vec.begin();iter!=vec.end();it++) printf("%d ",*iter);
  5. 插入元素 : vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a
  6. 删除元素 : vec.erase(vec.begin()+i);删除第i+1个元素
  7. 删除区间 : vec.erase(vec.begin()+i,vec.begin()+j);删除区间[i,j-1]
  8. 大小 : vec.size();
  9. 清空 : vec.clear();
  10. 使用reverse将元素翻转 : reverse(vec.begin(),vec.end());
  11. 使用sort排序 : sort(vec.begin(),vec.end());

1 【bzoj 3224】Tyvj 1728 普通平衡树

维护一些数,其中需要提供以下操作:
1.插入x数
2.删除x数(若有多个相同的数,因只删除一个)
3.查询x数的排名(若有多个相同的数,因输出最小的排名)
4.查询排名为x的数
5.求x的前驱(前驱定义为小于x,且最大的数)
6.求x的后继(后继定义为大于x,且最小的数)

然而set并不能完成4
但可以用vector实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int x,y,n;
int main()
{
scanf("%d",&n);
//a.reserve(200000);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(x==1) a.insert(upper_bound(a.begin(),a.end(),y),y);
else if(x==2) a.erase(lower_bound(a.begin(),a.end(),y));
else if(x==3) printf("%d\n",lower_bound(a.begin(),a.end(),y)-a.begin()+1);
else if(x==4) printf("%d\n",a[y-1]);
else if(x==5) printf("%d\n",*--lower_bound(a.begin(),a.end(),y));
else printf("%d\n",*upper_bound(a.begin(),a.end(),y));
}
}

2 【bzoj 1208】[HNOI2004]宠物收养所

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<algorithm>
#include<cstdio>
#include<set>
using namespace std;
set<int> s;
set<int>::iterator iter;
int n,mark,m,ans,mod=1000000;
int main()
{
scanf("%d",&n);
s.insert(-0x7fffffff);s.insert(0x7fffffff);
for(int i=1,x,y;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(x==mark||!m)
mark=x,m++,s.insert(y);
else
{
iter=s.lower_bound(y);
int b=*iter,a=*--iter;
if((long long)y-a<=(long long)b-y)
ans=(ans+y-a)%mod,s.erase(a);
else ans=(ans+b-y)%mod,s.erase(b);
m--;
}
}
printf("%d",ans);
}

3 【bzoj 1588】[HNOI2002]营业额统计

\[\sum_1^n min\lbrace \left|a[now]-a[pre]\right|\rbrace\]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<algorithm>
#include<cstdio>
#include<set>
using namespace std;
set<int> s;
int n,ans;
int main()
{
scanf("%d",&n);
s.insert(-0x7fffffff);
s.insert(0x7fffffff);
for(int i=1;i<=n;i++)
{
int x=0;scanf("%d",&x);
if(i==1) ans+=x;
else if(!s.count(x))
{
int a=*--s.lower_bound(x),b=*s.lower_bound(x);
if((long long)x-a<=(long long)b-x) ans+=x-a;
else ans+=b-x;
}
s.insert(x);
}
printf("%d",ans);
}

4 【bzoj 3173】[Tjoi2013]最长上升子序列

给定一个序列,初始为空。现在我们将1到N的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int n,len,f[100001],ans[100001];
int main()
{
scanf("%d",&n);
for(int i=1,j;i<=n;i++)
scanf("%d",&j),a.insert(a.begin()+j,i);
memset(f,0x7f,sizeof(f));
f[0]=-0x7fffffff;
for(int i=0;i<n;i++)
{
int t=upper_bound(f,f+len+1,a[i])-f;
if(f[t-1]<=a[i])
{
f[t]=min(f[t],a[i]);
ans[a[i]]=t;
len=max(len,t);
}
}
for(int i=1;i<=n;i++)
{
ans[i]=max(ans[i],ans[i-1]);
printf("%d\n",ans[i]);
}
}