基础知识
bitset空间为bool的1/8
abs等函数不能套__int128（可以手写）
vector自带大常数空间
函数加 inline 可以提升速度
lower_bound // 大于等于x最小值（找下界）
upper_bound // 大于x最小值（找上界）
如果不存在这样的元素，则返回尾迭代器。
都返回指针，需减去头指针，对于set，直接调用内置函数
unique // 返回筛出数后的第一个数的指针，减去头指针为筛出数的数量
计时 clock() / CLOCKS_PER_SEC
goto M1; // 较耗时
M1:
注意边界问题是STL出错常见原因
STL代替平衡树
令人惊讶的是vector可以提供很多平衡树的操作，
#include <bits/stdc++.h>
#define lb(a,y) lower_bound(a.begin(), a.end(), y)
#define ub(a,y) upper_bound(a.begin(), a.end(), y)
using namespace std;
int n;
vector<int> a;
int main()
{
cin >> n;
while(n--)
{
int op,x;
cin>>op>>x;
if(op==1) a.insert(lb(a,x),x);
else if(op==2) a.erase(lb(a,x));
else if(op==3) printf("%d\n",lb(a,x)-a.begin()+1);
else if(op==4) printf("%d\n",a[x-1]);
else if(op==5) printf("%d\n",a[lb(a,x)-a.begin()-1]);
else printf("%d\n",a[ub(a,x)-a.begin()]);
}
}
文艺平衡树这种要操纵大量结点的就跑不过了，而且vector不支持快速合并分裂平衡树，所以转拓展库
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define sr substr
#define B begin
#define e end
using namespace std;
using namespace __gnu_cxx;
int n,m,l,r;
rope<int> a,b;
void Rev()
{
rope<int> t=a; int ll=n-r-1,rr=n-l-1;
a=a.sr(a.B(),a.B()+l)+b.sr(b.B()+ll,b.B()+rr+1)+a.sr(a.B()+r+1,a.e());
b=b.sr(b.B(),b.B()+ll)+t.sr(t.B()+l,t.B()+r+1)+b.sr(b.B()+rr+1,b.e());
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) a.push_back(i),b.push_back(n-i+1);
while(m--){
scanf("%d%d",&l,&r);l--,r--;Rev();
}
for(int x:a) printf("%d ",x);
}
效率会比平衡树慢几倍，所以不推荐（
可持久化实现是靠的O(1)复制，所以要用指针。
S[0] = new rope<int>();
S[0]->append(0);
for(int i = 0; i < n; ++ i)
a[i] = read();
S[0]->insert(1, a, n);
for(int i = 1; i <= m; ++ i){
int v, k, a, b;
v = read(), k = read();
S[i] = new rope<int>(*S[v]);
if(k == 1){
a = read(), b = read();
S[i]->replace(a, b);
}
else {
a = read();
printf("%d\n", S[i]->at(a));
}
}
nums[0] = new rope<int>();
for(int i=1;i<=n;++i){
static int v,opt,x;
scanf("%d%d%d",&v,&opt,&x);
nums[i] = new rope<int>(*nums[v]);
if(opt == 1)
nums[i]->insert(lower_bound(nums[i]->begin(),nums[i]->end(),x)-nums[i]->begin(),x);
if(opt == 2){
auto it = lower_bound(nums[i]->begin(),nums[i]->end(),x);
if(*it == x) nums[i]->erase(it-nums[i]->begin(),1);
}
if(opt == 3)
printf("%d\n",(int)(lower_bound(nums[i]->begin(),nums[i]->end(),x)-nums[i]->begin()) + 1);
if(opt == 4)
printf("%d\n",*(nums[i]->begin() + x - 1));
if(opt == 5){
auto it = lower_bound(nums[i]->begin(),nums[i]->end(),x);
if(it == nums[i]->begin() - 1) puts("-2147483647");
else --it,printf("%d\n",*it);
}
if(opt == 6){
auto it = upper_bound(nums[i]->begin(),nums[i]->end(),x);
if(it == nums[i]->end()) puts("2147483647");
else printf("%d\n",*it);
}
}
以上条件还有一些没发掘完的
P5247
#define lb(a,y) lower_bound(a.begin(), a.end(), y)
using namespace std;
const int N = 5050;
int n, m;
vector<int> a[N];
int vis[N];
int qx[N], qy[N];
bool chk(int x, int y) {
int l1, r1, l2, r2;
l1 = r1 = l2 = r2 = 0;
qx[r1++] = x, qy[r2++] = y; // qx.push(x), qy.push(y)
vis[x] = 1; vis[y] = 2;
if (x == y) return true;
while (true) {
if (l1 == r1) return false;
int u = qx[l1++]; // u = qx.back(), qx.pop_back()
for (int i = 0; i < a[u].size(); ++i) {
int v = a[u][i];
if (vis[v] == 2) return 1;
if (vis[v] == 0) {
qx[r1++] = v; // qx.push(v)
vis[v] = 1;
}
}
if (l2 == r2) return false;
u = qy[l2++];
for (int i = 0; i < a[u].size(); ++i) {
int v = a[u][i];
if (vis[v] == 1) return 1;
if (vis[v] == 0) {
qy[r2++] = v;
vis[v] = 2;
}
}
}
return false;
}
int main() {
cin >> n >> m;
int lst = 0, op, x, y;
while (m--) {
cin >> op >> x >> y; x ^= lst, y ^= lst;
if (op == 0) a[x].insert(lb(a[x],y), y), a[y].insert(lb(a[y],x), x);
else if (op == 1) a[x].erase(lb(a[x],y)), a[y].erase(lb(a[y],x));
else {
memset(vis, 0, sizeof(vis));
if (chk(x, y)) puts("Y"), lst = x;
else puts("N"), lst = y;
}
}
return 0;
}
我们也可以类似（比如在树上跑双端spfa） 来求解一般化LCT问题
字符串当然也可以用
using namespace std;using namespace __gnu_cxx;
crope R; int t, now, x; char s[11], ch[3000010];
int main() { cin >> t;
while (t -- ) { cin >> s;
switch(s[0]) {
case 'M':cin >> now;break;
case 'I':cin >> x;ch[x] = 0; for(int i=0;i<x;i++){ch[i]=getchar();while(ch[i]=='\n'||ch[i]=='\r'){ch[i]=getchar();}}R.insert(now,ch);break;
case 'D':cin >> x;R.erase(now,x);break;
case 'G':cin >> x;R.copy(now,x,ch);ch[x]=0;puts(ch);break;
case 'P':now--;break; case 'N':now++;break; default:break;
} } }
需注意上述容器左闭右开。
注意可持久化并查集和可持久化线段树没有本质区别
int find(int i,int x)
{
if(rp[i]->at(x) == x) return x;
int f = find(i,rp[i]->at(x));
if(f == rp[i]->at(x)) return f;
rp[i]->replace(x,f);
return rp[i]->at(x);
}
inline void merge(int i,int x,int y)
{
x = find(i,x),y = find(i,y);
if(x != y) rp[i]->replace(y,x);
}
rp[i] = new rope<int> (*rp[i - 1]);
int opt; scanf("%d",&opt);
if(opt == 1){
int a,b; scanf("%d%d",&a,&b);
merge(i,a,b);
}
else if(opt == 2){
int k; scanf("%d",&k);
rp[i] = rp[k];
}
else{
int a,b;scanf("%d%d",&a,&b);
printf("%d\n",lastans = (find(i,a) == find(i,b)));
}
P8496
需要维护插入，删除，合并（保留及不保留），以及询问区间出现次数严格大于一半的数字。
前三个操作可以用链表解决，第四个可以用随机化解决（取不到概率为1/2，多随机几次即可），
不过我们还是需要维护序列中数字的出现个数，可以用gp_hash_table<int,int> h;
复杂度 O(24C)，漂亮的取代了 O(Clog^2C) 的分治做法和 O(ClogC) 的线段树合并做法。
而且还可以剪枝，比如说搜过的就标记，再写个启发式，就可以冲最优解了。
STL优化最短路
可见 OI-wiki
虽然set也可以达到这个效果，但堆快的可不只是一点。
一般 pairing_heap_tag 表现最好。
而在只关注连通性的问题中，bitset优化floyd也不比tarjan慢，
hash
由于unordered_map非常好卡，所以最好用gp_hash_table<int,int>替换，
同样hash也是方便实现离散化的最好选择
bitset
效率高于欧拉筛
bitset<N> vis;
void Prime(int n) {
vis.set();
vis[0] = vis[1] = 0;
for (int i = 2; i * i <= n; i++) {
if (vis[i]) {
for (int j = i << 1; j <= n; j += i) vis[j] = 0;
}
}
}
STL大法！