笔记汇总
详细讲述
$1.$ string
$2.$ vector
$3.$ 符号重载
$4.$ 编程技巧
upper_bound / lower_bound
upper_bound > x的第一个数
lower_bound >= x的第一个数
lower_bound(a+1, a+1+n, x) - a
vector
常用于储存图、不定长数据。
vector<int> v(n, t) // 声明一个名为v的有n个t元素的容器（不给t就是0）
vector<int>::iterator id; // 迭代器
不能越界访问，不推荐声明容器大小（除非必要）
a.begin() // 头指针
a.end() // 尾部空指针
a.front(),a.rbegin() //首元素
a.back(),a.rend() //末尾元素
v.push_back() //增
v.insert() //由于insert重载方法比较多
1.v.insert(p,t)//将t插到p的前面
2.v.insert(p,n,t)//将n个t插入p之前
3.v.insert(p,i,j)//将区间[i,j)的元素插入到p之前
4.v.insert(a.end(),b.begin(),b.end()); // 在后面插
v.pop_back() //删
v.erase(t,k)
1.v.erase(t,k)//删除他们之间的元素
2.v.erase(p)//删除p指向的元素
v.chear() == v.erase(begin(),end());
queue 和 stack
不允许随机访问元素，不能遍历，一定记得要判空。
deque
v.push_front()
v.pop_front()
v.push_back()
v.pop_back()
priority_queue
priority_queue<int> X //大根堆,默认初始化
priority_queue<int, vector<int>, greater<int>> x //小根堆,运用了预定义函数greater<int>
大根堆重载小于，
小根堆重载大于（虽然一般不用）
平衡树实现
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
begin() 首迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
链表
快速插入和删除，不能随机访问。
一般数组实现就行。
$ne$ 一个头结点指向的邻接指针指向下一个头结点指针
$pre$ 一个头结点指向的邻接指针指向上一个头结点指针
$h$ 头结点往后指的指针
迭代器
set<PII>::iterator id = a.lower_bound({c, c});
printf("%d", *(id).y);
还可以遍历
for (id = a.begin(); id != a.end(); id ++ )
bitset
压位, 存储相同的数据量，存储空间仅占$bool$变量的 $1/8$
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() // 返回有多少个1
any() // 判断是否至少有一个1
none() //判断是否全为0
set() //把所有位置成1
set(k, v) // 将第k位变成v
reset() // 把所有位变成0
flip() // 等价于~
flip(k) // 把第k位取反
string
substr(), c_str() //返回 const 类型的指针
size()/length() //返回字符串长度
empty()
clear() //清空整个字符串
erase() //erase(1,2) 删除以1为索引，长度为2的字符串
[]
支持比较运算，按字典序进行比较 a < "hello" 或 a.compare("hello");//a.compare() 返回具体的比较值
字符串变量和字符数组之间的转化：char ch[] = "hello"; string str = "world";
ch[] -> str : str = ch;
str -> ch[] : strcpy(ch,str.c_str());
string 初始化:
string a("hello");
string a = "hello";
取子串：//很常用
a.substr(1,3);//返回下标从1开始且长度为3的子串，包括左端点
拼接字符串：
a += "world";//新增字符串
a.append(" world");//新增字符串
a.push_back('.');//在字符串末新增单个字符
在字符串指定位置添加字符串
a.insert(3,"world");
访问字符串：string str;
cout << str[2];//以下标方式访问
cout << str.at(2);//通过at()方法访问
getline(cin,str );;//读取一行字符赋值给str
getline(cin, str,'!');//读取一行字符赋值给str,以！结束
字符串排序：
sort(str.begin(),str.end());//需要包含头文件algorithm
可以使用STL接口，可以理解为一个特殊的容器，容器里装的是的字符
a.push_back('.');//在字符串末新增单个字符
a.pop_back();
字符串变量的交换和取代：
a.swap(str);//str 为字符串变量
a.replace(1,2,str2) //用字符串str2取代字符串a下标为1长度为2的子串
符号重载
函数类型 operator 运算符 (形参表)
{
函数体；
}
PII operator + (PII a, PII b)
{
return {a.first + b.first, a.second + b.second};
}
struct matrix // 矩阵结构体
{
int w[N][N]; // 存矩阵
void init(bool type) // 矩阵初始化。type 为 true 则初始化为 E，type 为 false 则初始化为 O。
{
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i != j) w[i][j] = 0; // 两种矩阵的共同点：不在 i = j 对角线上的数皆为 0
else w[i][j] = type; // 不同点：在 i = j 对角线上，E 为 1，O 为 0
}
matrix operator * (const matrix &t) const // 重载矩阵乘法
{
matrix ans;
ans.init(false);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
for (int k = 1; k <= n; k ++ )
ans.w[i][j] = (ans.w[i][j] + t.w[i][k] * w[k][j]) % mod;
return ans;
}
matrix operator + (const matrix &t) const // 重载矩阵加法
{
matrix ans;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
ans.w[i][j] = (w[i][j] + t.w[i][j]) % mod;
return ans;
}
void print() // 将该矩阵输出
{
for (int i = 1; i <= n; i ++ ) // 不写奇怪的 for 循环了 2333
{
for (int j = 1; j <= n; j ++ )
printf("%d ", w[i][j]);
puts("");
}
}
void read() // 读入该矩阵
{
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
scanf("%d", &w[i][j]);
w[i][j] %= mod;
}
}
};
// 这个不更改原来的值
matrix operator ^ (matrix a, int k) // 重载矩阵快速幂。由于要用到乘法，所以在结构体外重载。
{
matrix ans;
ans.init(true);
while (k)
{
if (k & 1) ans = ans * a;
a = a * a, k >>= 1;
}
return ans;
}
扩展库
可持久化平衡树
#include<ext/rope>
using namespace __gnu_cxx;//rope的命名空间
rope<type> R;
R.push_back(a) //往后插入
R.insert(pos,a) //在pos位置插入a，pos是一个迭代器。
R.erase(pos,n) //在pos位置删除n个元素。
R.replace(pos,x)//从pos开始替换成x
R.substr(pos,x) //从pos开始提取x个。
R.size() // 获取R的大小
rope<type>* R[1000]; // 一般用指针，方便可持久化
R[i] = new rope<type>(*R[v]); // 复制
hash
#include<bits/extc++.h>
using namespace __gnu_pbds;
//bits/extc++.h与bits/stdc++.h类似，bits/extc++.h是所有拓展库，bits/stdc++.h是所有标准库
cc_hash_table<int,bool> h;
gp_hash_table<int,bool> h;
h[type] = a;
priority_queue
priority_queue<int,greater<int>,TAG> Q;//小根堆，大根堆写less<int>
/*其中的TAG为类型，有以下几种：
pairing_heap_tag
thin_heap_tag
binomial_heap_tag
rc_binomial_heap_tag
binary_heap_tag
其中pairing_help_tag最快*/
Q.push(x);
Q.pop();
Q.top();
Q.join(b);
Q.empty();
Q.size();
Q.modify(it,6);
Q.erase(it);
trie
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> tr;
//第一个参数必须为字符串类型，tag也有别的tag，但pat最快，与tree相同，node_update支持自定义
tr.insert(s); //插入s
tr.erase(s); //删除s
tr.join(b); //将b并入tr
pair//pair的使用如下：
pair<tr::iterator,tr::iterator> range=base.prefix_range(x);
for(tr::iterator it=range.first;it!=range.second;it++)
cout<<*it<<' '<<endl;
//pair中第一个是起始迭代器，第二个是终止迭代器，遍历过去就可以找到所有字符串了。
tree
平衡树
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> tr;
pii //存储的类型
null_type //无映射(低版本g++为null_mapped_type)
less<pii> //从小到大排序
rb_tree_tag //红黑树
tree_order_statistics_node_update //更新方式
tr.insert(mp(x,y)); //插入;
tr.erase(mp(x,y)); //删除;
tr.order_of_key(pii(x,y)); //求排名
tr.find_by_order(x); //找k小值，返回迭代器
tr.join(b); //将b并入tr，前提是两棵树类型一样且没有重复元素
tr.split(v,b); //分裂，key小于等于v的元素属于tr，其余的属于b
tr.lower_bound(x); //返回第一个大于等于x的元素的迭代器
tr.upper_bound(x); //返回第一个大于x的元素的迭代器
//以上所有操作的时间复杂度均为O(logn)
自定义，添加功能。
template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc>
struct my_node_update
{
typedef my_type, metadata_type;
void operator()(Node_Itr it, Node_CItr end_it)
{
...
}
};
我们先解释一下这个类是如何工作的。节点更新的tree都会保存一个my_type类型的变量。当我们修改这棵树的时候，会从叶子节点开始修改，并且每次都会调用operator()，我们来看一下这个函数的两个参数：
Node_Itr it为调用该函数的元素的迭代器，Node_CItr end_it可以const到叶子节点的迭代器，Node_Itr有以下的操作：
1.get_l_child()，返回其左孩子的迭代器，没有则返回node_end；
2.get_r_child()，同get_l_child();
3.get_metadata()，返回其在树中维护的数据；
4.**it可以获取it的信息。
为了详细讲解，我们举一个更新子树大小的例子：
void operator()(Node_Itr it, Node_CItr end_it)
{
Node_Itr l=it.get_l_child();
Node_Itr r=it.get_r_child();
int left=0,right=0;
if(l!=end_it) left=l.get_metadata();
if(r!=end_it) right=r.get_metadata();
const_cast<int&>(it.get_metadata())=left+right+1;
}
现在我们学会了更新，那么我们该如何自己写操作呢？node_update所有public方法都会在树中公开。如果我们在node_update中将它们声明为virtual，则可以访问基类中的所有virtual。所以，我们在类里添加以下内容：
virtual Node_CItr node_begin() const=0;
virtual Node_CItr node_end() const=0;
这样我们就能直接访问树了，还有，node_begin指向树根，node_end指向最后一个叶子节点的后一个地址，下面这个就是查排名的操作：
int myrank(int x)
{
int ans=0;
Node_CItr it=node_begin();
while(it!=node_end())
{
Node_CItr l=it.get_l_child();
Node_CItr r=it.get_r_child();
if(Cmp_Fn()(x,**it))
it=l;
else
{
ans++;
if(l!=node_end()) ans+=l.get_metadata();
it=r;
}
}
return ans;
}
应用，
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc>
struct my_node_update
{
typedef int metadata_type;
int order_of_key(pair<int,int> x)
{
int ans=0;
Node_CItr it=node_begin();
while(it!=node_end())
{
Node_CItr l=it.get_l_child();
Node_CItr r=it.get_r_child();
if(Cmp_Fn()(x,**it))
it=l;
else
{
ans++;
if(l!=node_end()) ans+=l.get_metadata();
it=r;
}
}
return ans;
}
void operator()(Node_Itr it, Node_CItr end_it)
{
Node_Itr l=it.get_l_child();
Node_Itr r=it.get_r_child();
int left=0,right=0;
if(l!=end_it) left =l.get_metadata();
if(r!=end_it) right=r.get_metadata();
const_cast<int&>(it.get_metadata())=left+right+1;
}
virtual Node_CItr node_begin() const = 0;
virtual Node_CItr node_end() const = 0;
};
tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,my_node_update> me;
int main()
{
map<int,int> cnt[2];
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
vector<int> pre(n),suf(n);
for(int i=0;i<n;i++)
{
pre[i]=cnt[0][a[i]]++;
suf[n-i-1]=cnt[1][a[n-i-1]]++;
}
long long ans=0;
for(int i=1;i<n;i++)
{
me.insert({pre[i-1],i-1});
ans+=i-me.order_of_key({suf[i],i});
}
cout<<ans<<endl;
}
其它函数
__int128 // 类型，要用快读快输
inline 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;
}
inline void write(int n){
if(n<0){
putchar('-');
n=-n;
}
if(n>9)write(n/10);
putchar(char(n%10+'0'));
}
//快输，原理和快读一样，程序是递归实现的。
__builtin_ffs(x) // 返回二进制下x中最后一个为1的位是从后向前的第几位。
__builtin_popcount(x) // 二进制下x中1的个数。
__builtin_ctz(x) // 二进制下x末尾0的个数。x=0时结果未定义。
__builtin_clz(x) // 二进制下x前导0的个数。x=0时结果未定义。
// 上面的宏中x都是unsigned int型的，如果传入signed或者是char型，会被强制转换成unsigned int。
