[ACM] 个人常见问题

因为影响板子空间，所以现在特将其从板子区分离出来，自成一文。

TIPS&WA

这里记录收集到的一些小技巧和注意事项（大部分和STL相关）。

[TIP] 获取一个整数二进制位数

正常做法是写循环位运算，

int cnt=0;
while(x){x>>=1;cnt++;}

但是如果直接用log2函数，写法上会更简洁更快（注意，测了一下，x小于1ll«16时，循环位移运算会快一点）

inline int len(ll x){//获取二进制位数（记得#include<cmath>）
    return x>0?log2l(x)+1:0;
}
//log这里不需要写int，因为返回值自动设为int了

如果你要卡常，试试下面的写法：
inline int len(ll x){
    if(x<=(1ll<<16)){
        int cnt=0;
        while(x){x>>=1;cnt++;}
    }
    return x>0?log2l(x)+1:0;
}

[TIP/WA] 位运算相关

• 按位左移，正数负数最左边补符号位（除开符号位的最左边）；按位右移，正数负数最右边都补0；无符号数当正数处理；

• 含有对高达$10^{18}$的数进行位运算的题，在对表达式进行左移时记得开ll，比如

  1ll<<n
  

• 使用~进行按位取反操作，包括符号位。

  可以用~构造INF：

  ll INF=(((ull)~0)>>1);
  

• 使用__builtin_popcount()获取一个数二进制下1的个数

[TIP/WA] 获取带空格的整行输入

洛谷的字符串题总是喜欢带一堆连续空格，还要求你不能忽略这些空格，这时候就需要用到$$getline(cin,t)$$了。 (什么？不喜欢iostream？那去这里选一个你喜欢的款式：C/C++如何整行输入，我就不一一列举了)

[WA] sort函数与string数组

两个string之间的比较也是要花时间的，若数组大小为 $n$，string长度为 $m$，则sort(a,a+n)的时间复杂的是 $O(nmlogn)$

[TIP/WA] for(auto &i:a)问题

在for(auto &i:a)循环体中对i修改直接反映于原迭代体a，但是不能在这种循环体中往a继续添加元素，不然会报错。

初始化vector数组时可以利用这个特性减少代码量：

vector<int> a(n);
for(auto& i:a)cin>>i;

[TIP] nth_element()与sort()

二者都可以求数组中第 $k$ 大，sort得先对数据进行 $O(n\log n)$ 的排序，再a[k]调用，而nth_element()则只需花 $O(n)$ 的时间进行部分排序，即可使得数组中第 $k$ 大的数就位，且其左边的数都比它小，右边的数都比它大

[TIP] 和python类似的多行字符串输入

使用R"(多行内容)"，即可完成，多行字符串的存储。和python的 ‘‘‘多行内容’‘‘差不多。

[WA] 取模问题

有时候可能会遇到一个式子内的取模符号太多，导致很容易丢失重要信息，比如该模的式子没有取模：

cout<<(((pre[n]-(ans>0)*ans)%M+(ans>0)*(ans*powp(2,k)%M)%M)%M+M)%M<<ET;
//某场div2上，有个ans忘记取模了，导致一直WA2，怎么也调不出问题，赛后补上这个%M就AC了：
cout<<(((pre[n]-(ans>0)*ans)%M+(ans>0)*((ans%M)*powp(2,k)%M)%M)%M+M)%M<<ET;

这时候可以考虑开一个函数来处理取模，化繁为简：

inline ll MO(ll x){return (x%M+M)%M;}
cout<<MO(MO(pre[n]-(ans>0)*ans)+(ans>0)*MO(MO(ans)*MO(powp(2,k))))<<ET;
//虽然看着好像差不了多少的样子，但是起码不用再受到%M+M)%M的折磨了

[WA] Python 的高精度问题

有些高精度的题，如果想用python来水的话，要特别注意除法的环节，python在除法时，会把结果转成float，而float型是不支持高精度运算的。所以这时候我们就需要整除。

[WA] map的遍历问题

用for(auto &[key,v]:mp){}即可

但是不知道为什么，上次写了个for(auto &[key1,v1]:mp)for(auto &[key2,v2]:mp)结果TLE了，还以为自己写的不是正解。

破案了，map的下标访问是 $O(logn)$ 的，所以TLE了

[WA] for(ll i=0;i<n;i++)问题

非必要别用ll写for循环，ll的运算比int运算慢了一倍，小心被卡常卡掉。

[WA] lower_bound()问题

这个不是“返回指向第一个小于v的元素的迭代器”的意思，而是“返回指向第一个大于等于v的元素的迭代器”的意思，要想返回第一个小于等于的元素，我建议自己手写一个二分吧。

[WA] 素数筛问题

p数组别开小了，素数只是少，不代表它小，你100000的数据，开2024大小的数组跑素数筛是想WA几次？（Luogu P1621 集合）

[TIP] 处理倍数的一个技巧

使用 (a+k-1)/k*k 可以得到大于等于a的第一个k的倍数。

[WA] 马拉车的R[]查回文子串

菜就多练，别背个板子，抄了还不会用。如果很不太会写怎么验字符串子串是不是回文串，那就直接封装个函数，然后就只需要调这个函数就行了。你问常数？我的建议是，如果你题都没法AC，那怕被卡常而省运行时间又有何用？

vector<int> PR;
inline bool PAL(int l,int r){
    return PR[r+l-1]-1==(r-l+1);
}

(Codeforce Global Round 25 E)

[WA] vector去重

vector去重的步骤是，先sort，再unique，最后erase，别把sort忘了

sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());

[TIP] 数据输入格式

cin可以读入含前导0的整数，比如说00013的数据，cin读到整数型变量里就变成了13；使用getchar()忽略单个字符

比如说要获取“03:12”的h和m，可以直接这样写：

int h,m;
cin>>h;getchar();cin>>m;

[TIP] 计算几何计算距离的快速写法

正常是这样写：

ld d=sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

有点麻烦，如果不在意函数的常数的话，可以使用cmath的函数求

ld d=hypot(x1-x2,y1-y2);

[TIP] 极简二分板子（FROM jiangly）

若数列已经按某规则划分成了左右两组，则该STL可快速返回其分界点（右边那组最靠左的元素）。

注意事项：若ck函数在给定范围内均成立，则返回的是r+1的值，如果有必要，这点记得特判一下。

//所需库：algorithm，ranges（C++20才有的，还是得记一下标准二分板子，这个只是偷懒用的）
//返回第一个使ck(x)为假的x
//（l,r+1）因为是左开右闭，所以右端应+1
int ans = *ranges::partition_point(ranges::iota_view(l, r+1),
    [&](int v) {
        return ck(v);
    });

//使用例：
#define PP(r,l,CK) *ranges::partition_point(ranges::iota_view(l, r+1),CK)

ll ans=PP(1,n,[&](int x){
    ...
    return 1;
    ...
    return 0;//ck函数直接写这里就行
});
//注意，如果你使用#define的调用方法，那么CK块里面不能出现逗号
//不然会报错。如果你真的需要在ck函数里写逗号，请auto ck=[&](int x){...};
//再PP(1,n,ck);

//最基础的两个线性二分STL：
//返回指向第一个大于v的元素的迭代器
auto mid=upper_bound(a.begin(),a.end(),v);
if(mid==a.end())//此时数组中不存在满足条件的数
else int ans=mid-a.begin();

//返回指向第一个大于等于v的元素的迭代器
auto mid=lower_bound(a.begin(),a.end(),v);

[WA] unordered类型容器

此类容器不能用end和begin来访问，乱写小心CE

[TIP] 降序排序容器

正常sort(a.begin(),a.end())是升序排序容器，如果想要倒序排序，可以用sort(a.rbegin(),a.rend())来排序，而无序写cmp。

[TIP] 判断vector内元素是否全相等

[From jiangly]

if(a==vector<int>(n,a[0]))

[WA] 并查集别用fa数组查根，要用find函数

[TIP] cp的sum函数

//begin(a)=>a.begin()
std::accumulate(begin(a), end(a), 0)

[TIP] STL前缀和

//begin(a)=>a.begin()
std::partial_sum(a.begin(), a.end(), b.begin());

[TIP] STL轮换

少用，O(n)的，你直接变换下标也行

//begin(a)=>a.begin()
std::rotate(a.begin(), a.end(), x);//x指第几号元素会被移位到第一个

[TIP] 快速离散化

保证数据两两不同时的快速离散化

std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
std::sort(p.begin(), p.end(), [&](int i, int j){
	return a[i] < a[j];
});
//此时，p的各个元素值代表原数组对应元素排序后的序号（从小到大）
//1 8 5 3 2 -> 0 4 3 2 1

[WA] 莫队不要带log

$O(n\sqrt n \log n)$的复杂度在 $n = 2e5$ 时已经达到了 $1e9$ 级别了。

[TIP] 非常抽象的维护

    auto cmp = [&](const auto& a, const auto& b) {
        return std::make_pair(dis[a.first][a.second], a) < std::make_pair(dis[b.first][b.second], b);
    };
    std::set<std::pair<int, int>, decltype(cmp)> q(cmp);

可以在每次 insert 时，按照外部提供的数据结构重新排序。（应该是$O(\log n)$的）

[TIP] 使用set维护不相交区间集

通过一种特殊的重载，可以实现用 set 维护不相交区间集。而且能够用 .find({x, y}) 成员函数，返回第一个与 $[x, y]$ 相交的区间。

bool operator<(const Data &b) const {
	return r < b.l;
}

auto cmp = [&](const auto& a, const auto& b) -> bool {
    return a.second < b.first;//a.R < b.L
};

std::set<std::pair<int, int>, decltype(cmp)> s(cmp);

[WA] 网络流板子建边

jiangly那个网络流板子，建边不是双向的，网络流本身也不是无向边，多写题练练吧

[WA] 位运算符号优先级问题

&, ^, | 和 «，» 不同级，建议疯狂加括号

[WA] 更安全的取模

对于 $abs(a)$ 远大于模数的情况的取模，可以这样取：

(std::abs(a) / M * M + M + a) % M

[TIP] 手写CPP23特性 this auto

对于高版本 cpp，lambda函数递归可以这样写：

auto f = [&](this auto self, int x) -> void {
    if (x > 0) return;
    self(x - 1);
};

但是若版本没那么高，就用不了，但我们可以手动实现这种特性：

// https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
namespace std {
    template<class Fun>
    class y_combinator_result {
        Fun fun_;
    public:
        template<class T>
        explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

        template<class ...Args>
        decltype(auto) operator()(Args &&...args) {
            return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
    };

    template<class Fun>
    decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
    }
}

auto F = std::y_combinator([&](auto self, int x) -> void {
    if (x > 0) return;
    self(x - 1);
});

虽然但是，我觉得还不如直接self(self, x)算了，也就多几个字符