常数优化技巧
UnionRE
·
·
算法·理论
卡常
这个其实很多人写过了，汇总一下。
STL
STL大部分比较慢。所以我们可以优化。
map
因此可以优化。
常见的就是`unordered_map`优化。这是一种哈希，所以可能被卡。
当然还有`pb_ds` ($\text{Policy-Based Data Structures}$) 优化。
```cpp
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gun_pbds;
```
`pb_ds`提供两种哈希，`cc_hash_table`和`gp_hash_table`。
> 其中cc开头为拉链法，gp开头为探测法，个人实测探测法稍微快一些。啥？操作？其实就和map差不多，支持[ ]和find。
>
> map的总时间复杂度是$O(n\log n)$的，而hash_table的总时间复杂度仅为$O(n)$！
>
> $\qquad\qquad\qquad\qquad\qquad\qquad$ ——[《比STL还STL？——平板电视》]([比STL还STL？——平板电视 - 洛谷专栏](https://www.luogu.com.cn/article/zi85ltjk))
`cc_hash_table`在随机数据下的表现较差，时间约为3倍`gp_hash_table`，空间约为8倍。
这两种哈希直接替换`map`即可，支持`[]`和`find()`，不支持`count()`。
定义方法同`map`。
顺便一说，[《关于NOI系列活动中编程语言使用限制的补充说明》](https://www.noi.cn/xw/2021-09-01/735729.shtml)，使得使用pb_ds有法可依。体现了规则不是一成不变的，良法需要体现社会发展规律……
### set / multiset
已经很好了。
### priority_queue
还是`pb_ds`。 #include<ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp> __gnu_pbds::priority_queue<Type, Compare, Tag, Allocator>//不要using namespace，不然会歧义(std::priority_queue)
* `Compare`:大根堆`less<Type>`，小根堆`greater<Type>`。
* `Tag`: pairing_heap_tag thin_heap_tag binomial_heap_tag rc_binomial_heap_tag binary_heap_tag
`paring_heap_tag`最快。
| | push | pop | modify | erase | Join |
| --- | --- | --- | --- | --- | --- |
| `pairing_heap_tag` | $O(1)$ | 最坏 $\Theta(n)\small ^1$ 均摊 $\Theta(\log(n))$ | 最坏 $\Theta(n)$ 均摊 $\Theta(\log(n))$ | 最坏 $\Theta(n)$ 均摊 $\Theta(\log(n))$ | $O(1)$ |
| `binary_heap_tag` | 最坏 $\Theta(n)$ 均摊 $\Theta(\log(n))$ | 最坏 $\Theta(n)$ 均摊 $\Theta(\log(n))$ | $\Theta(n)$ | $\Theta(n)$ | $\Theta(n)$ |
| `binomial_heap_tag` | 最坏 $\Theta(\log(n))$ 均摊 $O(1)$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ |
| `rc_binomial_heap_tag` | $O(1)$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ | $\Theta(\log(n))$ |
| `thin_heap_tag` | $O(1)$ | 最坏 $\Theta(n)$ 均摊 $\Theta(\log(n))$ | 最坏 $\Theta(\log(n))$ 均摊 $O(1)$ | 最坏 $\Theta(n)$ 均摊 $\Theta(\log(n))$ | $\Theta(n)$ |
**【注】：**
$1:$ $\Theta(g(x))$ 时间复杂度表示方法，表示确界。
* `Allocator` 空间配置器，一般不填。
## 常规操作
以下内容中，$A$>$B$ 表示$A$比$B$快。（除`>`和$>$外）
1. `i++`$\to$`++i`其实不必要。
2. 矩阵乘法，`for ikj`比`for ijk`快得多。
3. `#define`>`constexpr`>`const`（表示常量时）。
4. 快读快输。
``` cpp
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
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 << 1) + (x << 3)+ch-48;ch=getchar();}
return x*f;
}//快读
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}//快输
```
OI wiki
```cpp
void write(int x) {
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) putchar(sta[--top] + 48); // 48 是 '0'
}
```
不同type输出时，用这个(先不要`#define int long long`)
namespace fast_io{
const int fread_cnt=(1<<20);
const int fwrite_cnt=(1<<20);
class fast_read{
private:
char buf_in[fread_cnt],*p1,*p2;
inline char gc(){return (p1==p2&&(p2=(p1=buf_in)+fread(buf_in,1,fread_cnt,stdin),p1==p2)?EOF:*p1++);}
inline bool read_bool(){char ch=gc();while(ch<'0'||ch>'1'){ch=gc();}return (ch=='1');}
inline char read_ch(){char ch=gc();while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t'){ch=gc();}return ch;}
inline string read_string(){
string s;char ch=gc();while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t'){ch=gc();}
while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!='\t'){s+=ch;ch=gc();}return s;
}
template <typename T>
inline T read_int(){
T x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){f=(ch=='-')?-f:f;ch=gc();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x*f;
}
template <typename T>
inline T read_unsigned(){
T x=0;char ch=gc();while(ch<'0'||ch>'9'){ch=gc();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x;
}
template <typename T>
inline T read_float(){
T x=0,f=1,c=1;char ch=gc();
while(ch<'0'||ch>'9'){f=(ch=='-')?-f:f;ch=gc();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=gc();}
if(ch=='.'){ch=gc();while(ch>='0'&&ch<='9'){c/=10;x+=c*(ch^48);ch=gc();}}
return x*f;
}
public:
fast_read& operator >> (bool &valx){valx=read_bool();return *this;}
fast_read& operator >> (char &valx){valx=read_ch();return *this;}
fast_read& operator >> (string &valx){valx=read_string();return *this;}
fast_read& operator >> (float &valx){valx=read_float<float>();return *this;}
fast_read& operator >> (double &valx){valx=read_float<double>();return *this;}
fast_read& operator >> (long double &valx){valx=read_float<long double>();return *this;}
fast_read& operator >> (short &valx){valx=read_int<short>();return *this;}
fast_read& operator >> (int &valx){valx=read_int<int>();return *this;}
fast_read& operator >> (long &valx){valx=read_int<long>();return *this;}
fast_read& operator >> (long long &valx){valx=read_int<long long>();return *this;}
fast_read& operator >> (unsigned short &valx){valx=read_unsigned<unsigned short>();return *this;}
fast_read& operator >> (unsigned int &valx){valx=read_unsigned<unsigned int>();return *this;}
fast_read& operator >> (unsigned long &valx){valx=read_unsigned<unsigned long>();return *this;}
fast_read& operator >> (unsigned long long &valx){valx=read_unsigned<unsigned long long>();return *this;}
}fin;
class fast_write{
private:
char buf_out[fwrite_cnt],*p=buf_out;
inline void write_bool(bool x){char ch=(x==1)?'1':'0';pc(ch);}
inline void write_ch(char x){char ch=x;pc(ch);}
inline void write_string(string s){for(string::iterator it=s.begin();it!=s.end();it=next(it)){pc(*it);}}
template <typename T>
inline void write_int(T x){
if(x<(T)0){pc('-');x=-x;}
if(x>=10){write_int(x/10);}pc((x%10)^48);
}
template <typename T>
inline void write_unsigned(T x){
if(x>=10){write_unsigned(x/10);}pc((x%10)^48);
}
template <typename T>
inline void write_float(T x){
if(x<(T)0)pc('-'),x=-x;
write_int((int)x);pc('.');x-=(int)x;
while(x!=0){x*=10;pc((int)x^48);x-=(int)x;}
}
public:
inline void pc(char ch){if(p-buf_out==fwrite_cnt){fwrite(buf_out,1,fwrite_cnt,stdout),p=buf_out;}*p=ch;++p;}
inline void flush(){fwrite(buf_out,1,p-buf_out,stdout);p=buf_out;}
inline fast_write& operator << (bool valx){write_bool(valx);return *this;}
inline fast_write& operator << (char valx){write_ch(valx);return *this;}
inline fast_write& operator << (string valx){write_string(valx);return *this;}
inline fast_write& operator << (float valx){write_float<float>(valx);return *this;}
inline fast_write& operator << (double valx){write_float<double>(valx);return *this;}
inline fast_write& operator << (long double valx){write_float<long double>(valx);return *this;}
inline fast_write& operator << (short valx){write_int<short>(valx);return *this;}
inline fast_write& operator << (int valx){write_int<int>(valx);return *this;}
inline fast_write& operator << (long valx){write_int<long>(valx);return *this;}
inline fast_write& operator << (long long valx){write_int<long long>(valx);return *this;}
inline fast_write& operator << (unsigned short valx){write_unsigned<unsigned short>(valx);return *this;}
inline fast_write& operator << (unsigned int valx){write_unsigned<unsigned int>(valx);return *this;}
inline fast_write& operator << (unsigned long valx){write_unsigned<unsigned long>(valx);return *this;}
inline fast_write& operator << (unsigned long long valx){write_unsigned<unsigned long long>(valx);return *this;}
inline fast_write& operator << (fast_write& (*func)(fast_write&)){return func(*this);}
}fout;inline fast_write& endl(fast_write& fastout){fastout.pc('\n');fastout.flush();return fastout;}
}using namespace fast_io;
5. `bitset`
逆天时间复杂度，洛谷测评机 $O(\frac{n}{32})$ 。STL神器！
6. 位运算
`(l+r)>>1` > `(l+r)/2`。
7. 手写内置函数
```cpp
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
```
8.