set/map/rope/bitset用法
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流
2023年4月23日 20:14
crediblebh