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的迭代器指针
程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #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姿势不太对，于是加了读入优化，终于卡过了，但似乎是最后一名哈哈
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include<cstdio>#include<set>#include<map>#define N 500010#define inf 1000000000using 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() 删除所有元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #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个元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #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，太爽啦
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<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