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的定位器

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实现

#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]宠物收养所

#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\]

#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的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

#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]);
	}	
}