小工具（非原创）
卡常类
快读/快写
快读（by tmp_get_zip_diff）
inline long long read(){
char ch=getchar();
long long f=1,x=0;
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
快写（by tmp_get_zip_diff）
inline void _write(long long x){
if(x>9)_write(x/10);
putchar((x%10)+'0');
}
inline void write(long long x,short f=0){
if(x<0)putchar('-'),x=-x;
_write(x);
if(f!=0)putchar(char(f));
}
快读快写namespace（by a_good_boy）
namespace Fast_I {
char *_Buf,*_Start_ptr,*_End_ptr;
std::streambuf*inbuf;
unsigned int Size;
bool _Ok;
struct Fast_Istream {
operator bool(){return _Ok;}
Fast_Istream(std::streambuf*,unsigned int);
Fast_Istream(unsigned int);
Fast_Istream(const char*,unsigned int);
Fast_Istream&operator>>(char&);
Fast_Istream&operator>>(char*);
Fast_Istream&operator>>(bool&);
Fast_Istream&operator>>(short&);
Fast_Istream&operator>>(int&);
Fast_Istream&operator>>(long&);
Fast_Istream&operator>>(long long&);
Fast_Istream&operator>>(unsigned short&);
Fast_Istream&operator>>(unsigned int&);
Fast_Istream&operator>>(unsigned long&);
Fast_Istream&operator>>(unsigned long long&);
Fast_Istream&operator>>(float&);
Fast_Istream&operator>>(double&);
Fast_Istream&operator>>(long double&);
Fast_Istream&operator>>(std::string&);
template<typename Typex>
void operator()(Typex& _Val){*this>>_Val;}
template<typename Typex,typename...More>
void operator()(Typex&,More&...);
std::streambuf*rdbuf(){return inbuf;}
void rdbuf(std::streambuf*_inbuf){inbuf=_inbuf;}
void rdbuf(const char*);void pop();char peek();
};
}
namespace Fast_O{
std::string buf;std::streambuf* outbuf;
struct Fast_Ostream{
Fast_Ostream(std::streambuf*,unsigned int);
Fast_Ostream(std::streambuf*out){outbuf=out;}
Fast_Ostream(const char*, unsigned int);
Fast_Ostream(unsigned int);
void flush();~Fast_Ostream();
void endl(){buf.push_back('\n');}
template<typename Typex>
void endl(const Typex&_Val);
template<typename Typex,typename...More>
void endl(const Typex&,const More&...);
template<typename Typex>
void operator()(const Typex& _Val);
template<typename Typex,typename... More>
void operator()(const Typex&,const More&...);
Fast_Ostream&operator<<(char);
Fast_Ostream&operator<<(const char*);
Fast_Ostream&operator<<(const std::string&);
Fast_Ostream&operator<<(bool);
Fast_Ostream&operator<<(short);
Fast_Ostream&operator<<(int);
Fast_Ostream&operator<<(long);
Fast_Ostream&operator<<(long long);
Fast_Ostream&operator<<(unsigned short);
Fast_Ostream&operator<<(unsigned int);
Fast_Ostream&operator<<(unsigned long);
Fast_Ostream&operator<<(unsigned long long);
std::streambuf*rdbuf(){return outbuf;}
void rdbuf(std::streambuf*_outbuf) {outbuf=_outbuf;}
void rdbuf(const char*);
};
}
namespace Fast_IO{
Fast_I::Fast_Istream fin(std::cin.rdbuf(),1048576);
Fast_O::Fast_Ostream fout(std::cout.rdbuf());
}
#define cin Fast_IO::fin
#define cout Fast_IO::fout
namespace Fast_I{
Fast_Istream::Fast_Istream(std::streambuf*in,unsigned int Sz){_Ok=1;Fast_I::Size=Sz;inbuf=in;_Start_ptr=_End_ptr=_Buf=new char[Sz];}
Fast_Istream::Fast_Istream(const char*in,unsigned int Sz){_Ok=1;Fast_I::Size=Sz;rdbuf(in);_Start_ptr=_End_ptr=_Buf=new char[Sz];}
Fast_Istream::Fast_Istream(unsigned int Sz){_Ok=1;Fast_I::Size=Sz;_Start_ptr=_End_ptr=_Buf=new char[Sz];}
void Fast_Istream::rdbuf(const char*File){static std::ifstream __In__(File);rdbuf(__In__.rdbuf());}
void Get_Char(char&_Val) {
if(_Start_ptr==_End_ptr){_Start_ptr=_Buf;_End_ptr=_Buf+inbuf->sgetn(_Buf,Size);}
if(_Start_ptr==_End_ptr)_Val=1,_Ok=0;
else _Val=*_Start_ptr++;
}
Fast_Istream&Fast_Istream::operator>>(char&_Val){
if(_Ok){Get_Char(_Val);
while(_Val==32||_Val==10||_Val==13||_Val==8||_Val==9||_Val==7||_Val==12||_Val==11)Get_Char(_Val);
}return*this;
}
Fast_Istream& Fast_Istream::operator>>(char*_Val) {
if(_Ok){Get_Char(*_Val);
while (*_Val==32||*_Val==10||*_Val==13||*_Val==8||*_Val==9||*_Val==7||*_Val==12||*_Val==11)Get_Char(*_Val);
while (*_Val!=32&&*_Val!=10&&*_Val&&*_Val!=-1&&*_Val!=9&&*_Val!=11&&*_Val!=12)Get_Char(*++_Val);
*_Val=0;--_Start_ptr;
}
return*this;
}
Fast_Istream&Fast_Istream::operator>>(std::string&_Val) {
if(_Ok){char c;Get_Char(c);
while(c==32||c==10||c==13||c==8||c==9||c==7||c==12||c==11)Get_Char(c);
for(_Val.clear();c!=32&&c!=10&&c&&c!=-1&&c!=9&&c!=11&&c!=12;Get_Char(c)){_Val.push_back(c);}--_Start_ptr;
}return*this;
}
template <typename Typex>
void Get_Int(Typex& _Val) {
if(_Ok){char ch;bool _F=0;
for(Get_Char(ch);(ch<48||ch>57)&&ch!=-1;Get_Char(ch))_F=ch==45;
for(_Val=0;ch>47&&ch<58&&ch!=-1;Get_Char(ch))_Val=_Val*10+(ch^48);
if(_F)_Val=~_Val+1;--_Start_ptr;
}
}
template <typename Typex>
void Get_Unsigned(Typex& _Val) {
if(_Ok){char ch;Get_Char(ch);
while((ch < 48 || ch > 57) && ch != -1) Get_Char(ch);
for(_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) _Val = _Val * 10 + (ch ^ 48);
--_Start_ptr;
}
}
template<typename Typex>
void Get_Double(Typex&_Val){
if(_Ok){char ch;bool _F=0;
for(Get_Char(ch);(ch<48||ch>57)&&ch!=-1;Get_Char(ch))_F=ch==45;
for(_Val=0;ch>47&&ch<58&&ch!=-1;Get_Char(ch))_Val=_Val*10+(ch^48);
if(ch== 46){
unsigned long long _Pow=1;
for (Get_Char(ch);ch>47&&ch<58&&ch!=-1;Get_Char(ch))_Val+=Typex((ch^48)*1.0/(_Pow*=10));
}if(_F)_Val=-_Val;--_Start_ptr;
}
}
Fast_Istream& Fast_Istream::operator>>(bool&_Val) {
if(_Ok){char ch;Get_Char(ch);
while(ch==32||ch==10||ch==13||ch==8||ch==9||ch==7||ch==12||ch==11)Get_Char(ch);
while(ch!32&&ch!=10&&ch&&ch!=-1&&ch!=9&&ch!=11&&ch!=12){_Val|=ch!=48;Get_Char(ch);}
--_Start_ptr;
}return *this;}
Fast_Istream&Fast_Istream::operator>>(short&_Val){Get_Int(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(int&_Val){Get_Int(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(long&_Val){Get_Int(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(long long&_Val){Get_Int(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(unsigned short&_Val){Get_Unsigned(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(unsigned int&_Val){Get_Unsigned(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(unsigned long& _Val){Get_Unsigned(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(unsigned long ong&_Val){Get_Unsigned(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(float&_Val){Get_Double(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(double&_Val){Get_Double(_Val);return*this;}
Fast_Istream&Fast_Istream::operator>>(long double&_Val){Get_Double(_Val);return*this;}
template<typename Typex,typename... More>
void Fast_Istream::operator()(Typex& _Val, More&..._More){*this>>_Val;operator()(_More...);}
void Fast_Istream::pop(){char ch;Get_Char(ch);}
char Fast_Istream::peek(){
if(_Start_ptr==_End_ptr){_Start_ptr=_Buf;_End_ptr=_Buf+inbuf->sgetn(_Buf,Size);}
if(_Start_ptr== _End_ptr){_Ok=0;return -1;}else{return*_Start_ptr;}
}
}
namespace Fast_O{
Fast_Ostream::Fast_Ostream(std::streambuf*out,unsigned int Size){buf.reserve(Size);outbuf=out;}
Fast_Ostream::Fast_Ostream(const char*File,unsigned int Size){buf.reserve(Size);rdbuf(File);}
void Fast_Ostream::rdbuf(const char*File){static std::ofstream __Out__(File);rdbuf(__Out__.rdbuf());}
Fast_Ostream::Fast_Ostream(unsigned int Size){buf.reserve(Size);}
void Fast_Ostream::flush(){outbuf->sputn(buf.data(),buf.size());buf.clear();}
Fast_Ostream::~Fast_Ostream(){flush();}
Fast_Ostream& Fast_Ostream::operator<<(char _Val){buf.push_back(_Val);return*this;}
Fast_Ostream& Fast_Ostream::operator<<(const char*_Val){while(*_Val){buf.push_back(*_Val++);}return*this;}
Fast_Ostream& Fast_Ostream::operator<<(const std::string&_Val){for(auto&& i:_Val){buf.push_back(i);}return*this;}
template <typename Typex>
void Put_Unsigned(Typex _Val) {
char* _Stack=(char*)malloc(sizeof(Typex)*3);unsigned S_top=0;
while(_Val){_Stack[++S_top]=(_Val%10)^48;_Val/=10;}
if(!S_top){buf.push_back('0');}
while(S_top){buf.push_back(_Stack[S_top--]);}free(_Stack);
}
void Put_Int(long long _Val){if(_Val<0){buf.push_back('-');Put_Unsigned(~_Val+1);}else{Put_Unsigned(_Val);}}
Fast_Ostream& Fast_Ostream::operator<<(bool _Val){buf.push_back(_Val?'1':'0');return*this;}
Fast_Ostream& Fast_Ostream::operator<<(short _Val){Put_Int(_Val);return*this;}
Fast_Ostream& Fast_Ostream::operator<<(int _Val){Put_Int(_Val);return*this;}
Fast_Ostream& Fast_Ostream::operator<<(long _Val){Put_Int(_Val);return*this;}
Fast_Ostream& Fast_Ostream::operator<<(long long _Val){Put_Int(_Val);return*this;}
Fast_Ostream& Fast_Ostream::operator<<(unsigned short _Val){Put_Unsigned(_Val);return*this;}
Fast_Ostream& Fast_Ostream::operator<<(unsigned int _Val){Put_Unsigned(_Val);return*this;}
Fast_Ostream& Fast_Ostream::operator<<(unsigned long _Val){Put_Unsigned(_Val);return*this;}
Fast_Ostream& Fast_Ostream::operator<<(unsigned long long _Val){Put_Unsigned(_Val);return*this;}
template<typename Typex>
void Fast_Ostream::endl(const Typex&_Val){*this<<_Val<<'\n';}
template<typename Typex,typename...More>
void Fast_Ostream::endl(const Typex&_Val,const More&..._More) {*this<<_Val;endl(_More...);}
template<typename Typex>
void Fast_Ostream::operator()(const Typex&_Val){*this<<_Val;}
template<typename Typex,typename...More>
void Fast_Ostream::operator()(const Typex&_Val,const More&..._More){*this<<_Val;operator()(_More...);}
}
快读快写（by jjl_cxk）
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;
}
void print(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10)
print(x/10);
putchar(x%10+'0');
return;
}
关闭同步流（by zibenlun）
#define yuanshen ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
$10^{12} \text{kg}$（by zrl123456）
#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
模板类
最长链及次长链求树的直径（by jjl_cxk）
struct EDGE{
int id,qz;
};
int n=read(),m=read(),cd[50002][11],ans,ans2;
vector<EDGE>vt[500012];
void dfs(int now,int fa)
{
for(EDGE i:vt[now])
{
if(i.id!=fa)
{
dfs(i.id,now);
ans2+=i.qz;
int bc=cd[i.id][0]+i.qz;
if(bc>cd[now][0])swap(cd[now][0],bc);
if(bc>cd[now][1])swap(cd[now][1],bc);
}
}
ans=max(ans,cd[now][0]+cd[now][1]);
}
最大公约数，最小公倍数（C++17以上）
质数筛
线性筛+求质数个数（by jjl_cxk）
int prime[114000000],total;
bool isPrime[114000000];
void seive( int Max )
{
memset( isPrime , true , sizeof( isPrime ));
isPrime[0 ] = false ; isPrime[1] = false ;
for ( int i = 2 ; i <= Max ; i++ )
{if ( isPrime[i] ) prime[ ++ total ] = i ;
for ( int j = 1 ; j <= total && i * prime[j] <= Max ; j++)
{ isPrime[ i * prime[j] ] = false ;
if (!( i % prime[j])) break;
}
}
}
线性筛
inline void get_prime(int Mx){
vis[1]=true;
for(int i=2;i<=Mx;i++)
{
if(vis[i]==false)
primes.push_back(i);
for(int j=0;j<primes.size();j++)
{
int p=primes[j];
if(p*i>Mx)
break;
vis[p*i]=true;
if(i%p==0)
break;
}
}
return ;
}
数学函数（by stostostoorzorzorz）
long long mod(long long x,long long p) { return x-(x/p)*p; }
long long r(long long a,long long b) { return mod( (long long)(rand()*rand()) , b-a+1)+a; }
long long random(long long a,long long b) { long long ra=r(a,b); for(int i=1;i<=N;i++) { ra=ra/r(a,b)*r(a,b); ra=ra%(b-a+1)+a; } return ra; }
快速幂（by tmp_get_zip_diff）
inline int qpow(int x,int y,int p){
if(y==1)
return x;
int tmp=qpow(x,y>>1,p)%p;
if(y%2==0)
return (tmp*tmp)%p;
return ((tmp*tmp)%p*x)%p;
}
数据结构模板
线段树（by tmp_get_zip_diff）
inline void pushup(int cur){
tree[cur]=tree[cur<<1]+tree[(cur<<1)+1];
return ;
}
inline void build(int cur,int lt,int rt){
if(lt==rt)
{
tree[cur]=a[lt];
return ;
}
int mid=(lt+rt)>>1;
build(cur<<1,lt,mid);
build((cur<<1)+1,mid+1,rt);
pushup(cur);
return ;
}
inline void addtag(int cur,int lt,int rt,int val){
tree[cur]+=(rt-lt+1)*val;
tag[cur]+=val;
return ;
}
inline void pushdown(int cur,int lt,int rt){
if(tag[cur]==0)
return ;
int mid=(lt+rt)>>1;
addtag(cur<<1,lt,mid,tag[cur]);
addtag((cur<<1)+1,mid+1,rt,tag[cur]);
tag[cur]=0;
return ;
}
inline int query(int cur,int lt,int rt,int qx,int qy){
if(qy<lt||rt<qx)
return 0;
if(qx<=lt&&rt<=qy)
return tree[cur];
pushdown(cur,lt,rt);
int mid=(lt+rt)>>1;
return query(cur<<1,lt,mid,qx,qy)+query((cur<<1)+1,mid+1,rt,qx,qy);
}
inline void update(int cur,int lt,int rt,int qx,int qy,int val){
if(qy<lt||rt<qx)
return ;
if(qx<=lt&&rt<=qy)
{
addtag(cur,lt,rt,val);
return ;
}
pushdown(cur,lt,rt);
int mid=(lt+rt)>>1;
update(cur<<1,lt,mid,qx,qy,val);
update((cur<<1)+1,mid+1,rt,qx,qy,val);
pushup(cur);
return ;
}
树状数组（by tmp_get_zip_diff）
inline int lowbit(int x){
return x&-x;
}
inline int query(int x){
int sum=0;
while(x!=0)
{
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
inline void update(int x,int val){
while(x<=n)
{
tree[x]+=val;
x+=lowbit(x);
}
return ;
}
求某整数二进制$1$的个数
排序算法
快速排序（by jjl_cxk）
void k_sort(int l,int r)
{
int i,j,mid,p;
i=l,j=r;
mid=a[(l+r)/2];
do
{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++,j--;
}
}while(i<=j);
if(l<j) k_sort(l,j);
if(i<r) k_sort(i,r);
}
冒泡排序（by jjl_cxk）
void m_sort(int l,int r)
{
for(int i=r;i>l;i--)
for(int j=l;j<i;j++)
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
归并排序（by jjl_cxk）
void g_sort(int l,int r)
{
if (l>=r)
return;
int mid=l+r>>1;
g_sort(l,mid);
g_sort(mid+1,r);
int i=l,j=mid+1,k=0;
while (i<=mid&&j<=r)
if (a[i]<=a[j])
tmp[k++]=a[i++];
else
tmp[k++]=a[j++];
while (i<=mid)
tmp[k++]=a[i++];
while (j<=r)
tmp[k++]=a[j++];
for (int i=l,j=0;i<=r;i++)
a[i]=tmp[j++];
}
高精度
高精度（by jjl_cxk）
char a1[10100],b1[10100];
int a[10100],b[10100],c[4000005],lena,lenb,lenc,i,x;
char temp[10100],f;
高精加
void gaojia()
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
cin>>a1>>b1;
lena=strlen(a1);
lenb=strlen(b1);
for(i=0;i<=lena-1;i++) a[lena-i]=a1[i]-48;
for(i=0;i<=lenb-1;i++) b[lenb-i]=b1[i]-48;
lenc=max(lena,lenb);
x=0;
for(i=1;i<=lenc;i++)
{
c[i]=a[i]+b[i]+x;
x=c[i]/10;
c[i]%=10;
}
if(x!=0)
lenc++,c[lenc]=x;
for(i=lenc;i>=1;i--)
cout<<c[i];
}
高精减
void gaojian()
{
cin>>a1>>b1;
if(strlen(a1)<strlen(b1)||(strlen(a1)==strlen(b1)&&strcmp(a1,b1)<0))
{
strcpy(temp,a1);
strcpy(a1,b1);
strcpy(b1,temp);
f='-';
}
lena=strlen(a1);
lenb=strlen(b1);
for(i=0;i<=lena-1;i++) a[lena-i]=a1[i]-48;
for(i=0;i<=lenb-1;i++) b[lenb-i]=b1[i]-48;
lenc=lena;
for(i=1;i<=lenc;i++)
{
if(a[i]<b[i])
{
a[i]+=10;
a[i+1]--;
}
c[i]cheng=a[i]-b[i];
}
while(c[lenc]==0&&lenc>1) lenc--;
if(f=='-') cout<<"-";
}
高精乘
void gaocheng(char a1,char b1)
{
//cin>>a1>>b1;
lena=strlen(a1);
lenb=strlen(b1);
for(i=0;i<=lena-1;i++) a[lena-i]=a1[i]-48;
for(i=0;i<=lenb-1;i++) b[lenb-i]=b1[i]-48;
for(i=1;i<=lena;i++)
{
x=0;
for(int j=1;j<=lenb;j++)
{
x=a[i]*b[j]+x/10+c[i+j-1];
c[i+j-1]=x%10;
}
c[i+lenb]=x/10;
}
lenc=lena+lenb;
while(c[lenc]==0&&lenc>1) lenc--;
for(i=lenc;i>=1;i--)
cout<<c[i];
}
高精度结构体（不完整）
// 高精度结构体
template<int MAXSIZE, typename TY = short>
struct hipr {
int uslen = 0; //已使用的长度，未使用为0
TY num[MAXSIZE]{ 0 }; //高精度数的实际存储数组
bool _pos = 1, __flag; //数的正负 1为正，0为负
void erazero() { //去前导0
while (!num[uslen] && uslen > 1) uslen--;
}
void print(const char* Fmt) { //打印，`%`打印这个数字
for (int i = 0; i < strlen(Fmt); i++) //遍历格式数组
if (Fmt[i] == '%') //打印这个数
{
if (!_pos) putchar('-'); //负数
for (int j = uslen; j > 0; j--) putchar(num[j] + '0');
}
else putchar(Fmt[i]); //没有遇到 `%` 的情况
}
void hipin(string s) { //string输入
uslen = s.size(); //已使用的长度
if (s[0] == '-') _pos = 0, __flag = 1; //负数
for (int i = (__flag ? --uslen : uslen - 1), j = 1; i >= __flag; i--, j++)
num[j] = s[i] ^ 48; //可用 `-'0'` 代替
}
};
高精加（只能输入正数）
template<int MAXSIZE, typename TY>
void hiadd(hipr<MAXSIZE,TY>* a, hipr<MAXSIZE,TY>* b, hipr<MAXSIZE,TY>* ans) {
ans->uslen = max(a->uslen, b->uslen) + 1;
TY x = 0;
for (int i = 1; i <= ans->uslen; i++)
{
ans->num[i] = (a->num[i] + b->num[i] + x) % 10;
x = (a->num[i] + b->num[i] + x) / 10;
}
ans->erazero();
}
高精乘（只能输入正数)
template<int MAXSIZE, typename TY>
void himulti(hipr<MAXSIZE,TY>* a, hipr<MAXSIZE,TY>* b, hipr<MAXSIZE,TY>* ans) {
ans->uslen = a->uslen + b->uslen;
for (int i = 1; i <= a->uslen; i++)
{
for (int j = 1; j <= b->uslen; j++) ans->num[i + j - 1] += a->num[i] * b->num[j];
for (int j = 1; j <= ans->uslen; j++)
{
ans->num[j + 1] += ans->num[j] / 10;
ans->num[j] %= 10;
}
}
ans->erazero();
}