set/map/rope/bitset用法

orz hhw posted @ 2015年5月31日 15:18 in 算法学习 with tags 数据结构 Set 算法学习 模板 STL map rope bitset , 1074 阅读
 
Set用法
函数
bst.begin()         返回首元素的迭代器指针
bst.end()          返回尾元素的迭代器指针
bst.insert(key)        插入一个值key
bst.erase(key)         删除地址为key的数
bst.erase(l,r)         删除地址[l,r)的数
bst.size()             目前元素个数
bst.find(key)       返回键值等于key的迭代器指针
bst.count(key)      返回键值等于key的元素的个数
bst.lower_bound(key) 返回键值大于等于key的迭代器指针
bst.upper_bound(key) 返回键值大于key的迭代器指针
 
程序
#include<cstdio>
#include<set>
using namespace std;
set<int> bst;
set<int>::iterator now,l,r,it;
int main(){
	for(int i=1;i<=10;i++)bst.insert(i);
	now=bst.find(3);
	bst.erase(now);//1 2 4 5 6 7 8 9 10
	l=bst.lower_bound(5);//5
	r=bst.upper_bound(8);//9
	bst.erase(l,r);//1 2 4 9 10
	printf("%d\n",bst.size());// 5
	for(it=bst.begin();it!=bst.end();it++)printf("%d ",*it);
}

然后来实战演习,就来做ZJOI2007报表统计吧,实在太SB,懒得手写,现在学了set正好写一发

写是挺容易的,但由于不会MAP,RE了几发,搞了MAP后终于在LJOJ上A了,兴冲冲的去BZOJ上交,没想到TLE了、、

也许是写set姿势不太对,于是加了读入优化,终于卡过了,但似乎是最后一名哈哈

#include<cstdio>
#include<set>
#include<map>
#define N 500010
#define inf 1000000000
using namespace std;
int n,m,i,now,key,t,ans,st[N],ed[N];
char s[99];
multiset<int> bst,bst2;
map<int,int> w;
int abs(int x){if(x<0)return -x;return x;}
int min(int x,int y){if(x<y)return x;return y;}
void insert(int x){w[x]++;if(w[x]==1)bst.insert(x);}
void push(int x){
    int l=*--bst2.lower_bound(x),r=*bst2.lower_bound(x);
    ans=min(ans,min(x-l,r-x));
    bst2.insert(x);
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
	n=read();m=read();
	ans=inf;
	bst2.insert(inf);bst2.insert(-inf);
	for(i=1;i<=n;i++){
		key=read();
		push(key);
		ed[i]=st[i]=key;
		if(i>1)insert(abs(st[i]-st[i-1]));
	}
	now=n;
	while(m--){
		scanf("%s",s);
		if(s[0]=='I'){
			i=read();key=read();
			if(i!=n){
				t=abs(ed[i]-st[i+1]);
				w[t]--;
				if(!w[t])bst.erase(t);
			}
            insert(abs(ed[i]-key));
            insert(abs(key-st[i+1]));
            ed[i]=key;
            push(key);
		}else if(s[4]=='G')printf("%d\n",*bst.begin());
		else printf("%d\n",ans);
	}
}
 

 

 

map用法

map构造函数:
   map<int/char/string(原变量),int/char/string(现变量)>mapint/char/string;
map添加数据:
   map<int,string>mp;
   1.mp.insert(pair<int,string>(233,"orzmxh"));
   2.mp.insert(map<int,string>::value_type(521,"orzhzh"));
   3.mp[666]="orzhhw";
   mp->first第一项 mp->second第二项
map函数:
   mp.begin()         返回首元素的迭代器指针
   mp.end()          返回尾元素的迭代器指针
   mp.size()             目前元素个数
   mp.bool()        判断容器是否空,若返回true,表明容器已空
   mp.find(key)       返回键值等于key的迭代器指针
   mp.count(key)      返回键值等于key的元素的个数
   mp.lower_bound(key) 返回键值大于等于key的迭代器指针
   mp.upper_bound(key) 返回键值大于key的迭代器指针
   mp.erase(key)      删除迭代指针key处元素
   mp.erase(l,r)      删除[l,r)之间元素
   mp.swap(mp2)       交换mp和mp2映射元素
   mp.clear()         删除所有元素
#include<map>  
#include<cstdio>
using namespace std;
map<char,int> mp1,mp2;
map<char,int>::iterator it;
int main(){
    mp1['a']=1;mp1['b']=2;  
    mp1['c']=3;mp1['d']=4;
    mp2.insert(pair<char,int>('e',10));
    mp2.insert(pair<char,int>('f',40));
    mp2.insert(map<char,int>::value_type('g',60));
    mp2.insert(map<char,int>::value_type('h',80));
	mp1.swap(mp2);
	it=mp2.find('b');
	printf("%d\n",it->second);//2
	mp2.erase(mp2.find('b'),mp2.find('d'));//<a,1> <d,4>
	printf("%d\n",mp2.size());//2
	printf("%d\n",mp1.count('g'));//1
	for(it=mp1.begin();it!=mp1.end();it++)//<e,10><f,40>
	printf("%c %d\n",it->first,it->second);//<g,60><h,80>
} 

Rope用法

头文件:#include<ext/rope>
声明:using namespace __gnu_cxx;
定义:crope x;
函数:
  x.push_back(ch) 在末尾添加字符ch
  x.insert(pos,s) 在pos位置插入字符ch
  x.erase(pos,x)  从pos位置开始删除x个
  x.replace(pos,ch) 将位置为pos的字符换成ch
  x.substr(pos,x) 从pos位置开始提取x个字符
  x.copy(pos,x,s) 将从pos位置开始x个字符提取到s中
  x.at(x)/[x]访问第x个元素
#include<ext/rope>
#include<cstdio>
using namespace std;
using namespace __gnu_cxx;
crope x;
char s[10000000];
int main(){
	x.insert(0,"233");
	x.erase(1,1);//23
	x.replace(1,"!");//2!
	x.push_back('1');//2!1
	x.insert(2,"&^");//2!&^1
	x.copy(0,5,s);
	printf("%s",s);//2!&^1
}

然后听毛主力说ROPE可以可持久化,只要fa[i]=new rope<int>(*fa[i-1]);就行啦

BZOJ3673&3674可持久化并查集,只有700多B,太爽啦

#include<cstdio>
#include<ext/rope>
using namespace __gnu_cxx;
rope<int> *fa[200002];
int n,m,i,x,y,p,ans,a[200002];
int find(int x){
	if(fa[i]->at(x)!=x){
		int f=find(fa[i]->at(x));
		if(f==fa[i]->at(x))return f;
		fa[i]->replace(x,f);
		return fa[i]->at(x);
	}
	return x;
}
void uni(int x,int y){int p=find(x),q=find(y);fa[i]->replace(q,p);}
int main(){
	scanf("%d%d",&n,&m);for(i=0;i<=n;i++)a[i]=i;
	fa[0]=new rope<int>(a,a+n+1);
	for(i=1;i<=m;i++){
		fa[i]=new rope<int>(*fa[i-1]);scanf("%d",&p);
		if(p==1)scanf("%d%d",&x,&y),uni(x^ans,y^ans);
		else if(p==2)scanf("%d",&x),fa[i]=fa[x^ans];
		else if(p==3)scanf("%d%d",&x,&y),printf("%d\n",(ans=find(x^ans)==find(y^ans)));
	}
} 

bitset用法

今天打BC被这个坑了,出题人脑子有gin一定要用bitset,不用就超时,也因此失去了38元奖励。。

1.头文件:#include<bitset>
2.定义:bitset<2000000> b(key);//key为初值,但从右向左读
3.函数:b.any()    b中是否存在置为1的二进制位
b.none()        b中不存在置为1的二进制位吗
b.count()       b中置为1的二进制位的个数
b.size()        b中二进制位的个数
b[pos]         访问b中在pos处的二进制位
b.test(pos)      b中在pos处的二进制位是否为1
b.set()         把b中所有二进制位都置为1
b.set(pos)       把b中在pos处的二进制位置为1
b.reset()       把b中所有二进制位都置为0
b.reset(pos)     把b中在pos处的二进制位置为0
b.flip()        把b中所有二进制位逐位取反
b.flip(pos)      把b中在pos处的二进制位取反
b.to_ulong()     用b中同样的二进制位返回一个unsigned long值
os << b        把b中的位集输出到os流
 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter