stdafx
HighPerformanceRobot
2019-01-03 20:27:42
## 新版更新通知:
更新INT，除法仍然无法使用，有几率WA，机房电脑配置不好，过几天回家之后再调试。
更新字典树trie，支持基础插入、查询操作。
现版本将可以直接`#include<stdafx>`
[stdafx及stdafx.h食用方法](https://www.luogu.org/blog/133720/stdafx-yu-stdafxh-si-yong-fang-fa)
以下是stdafx文件内容：
```cpp
#ifndef _GLIBCXX_STDAFX
#define _GLIBCXX_STDAFX 1
#pragma GCC system_header
#include<stdafx.h>
#endif
```
以下是stdafx.h文件内容：
```cpp
#ifndef stdafx
#define stdafx 1
#define LL long long
#define ULL unsigned long long
#define UF unsigned float
#define UD unsigned double
#include<bits/stdc++.h>
using namespace std;
namespace std
{
class INT
{
protected:
vector <ULL> que;
bool flag;
static const ULL mod=1e8;
inline unsigned size()const
{
return que.size();
}
inline void count()
{
while(que.size()>1&&!que[que.size()-1])
que.pop_back();
}
inline void check()
{
unsigned len=size();
for(unsigned i=0; i<len-1; i++)
{
que[i]+=mod;
que[i+1]--;
que[i+1]+=que[i]/mod;
que[i]%=mod;
}
count();
}
inline void lmove(unsigned size)
{
que.resize(que.size()+1);
for(unsigned i=que.size()-1; i; i--)
que[i]=que[i-1];
que[0]=0ull;
}
public:
inline INT()
{
que.clear();
que.push_back(0ull);
flag=1;
}
inline INT(const char num[])
{
*this=num;
}
inline INT(const int &num)
{
*this=num;
}
inline INT(const long long &num)
{
*this=num;
}
inline INT operator=(const string num)
{
que.clear();
que.resize(num.size()/8+1);
bool f=(num[0]=='-');
flag=!f;
string now=num.substr((int)f);
reverse(now.begin(),now.end());
for(unsigned i=0; i<now.size(); i+=8)
{
string str=now.substr(i,8);
reverse(str.begin(),str.end());
que[i/8]=stoi(str);
}
count();
return *this;
}
inline INT operator=(const char num[])
{
string str=num;
return *this=str;
}
inline INT operator=(const int &now)
{
int num=now;
num<0?flag=0,num=-num:flag=1;
que.clear();
if(!num)
{
que.push_back(0);
return *this;
}
while(num)
que.push_back(num%mod),num/=mod;
return *this;
}
inline INT operator=(const long long &now)
{
long long num=now;
num<0?flag=0,num=-num:flag=1;
que.clear();
if(!num)
{
que.push_back(0ull);
return *this;
}
while(num)
que.push_back(num%mod),num/=mod;
return *this;
}
inline INT operator+(const INT &num)const
{
if(flag^num.flag)
{
INT tmp=flag?num:*this;
tmp.flag=1;
return flag?*this-tmp:num-tmp;
}
INT res=*this;
res.que.resize(size()+1);
for(unsigned i=0,temp=0; temp||i<num.size(); i++)
{
res.que[i]+=num.que[i];
res.que[i+1]+=res.que[i]/mod;
res.que[i]%=mod;
}
res.count();
res.flag=flag;
return res;
}
inline INT operator-(const INT &num)const
{
if(flag)
if(num.flag)
{
if(*this<num)
return -(num-*this);
}
else
return *this+(-num);
else
return flag?-((-*this)+num):-num-(-*this);
INT res=*this;
res.que.resize(res.size()+1);
for(unsigned i=0; i<num.size(); i++)
res.que[i]-=num.que[i];
res.check();
return res;
}
inline INT operator*(const INT &num)const
{
INT res;
res.que.resize(size()+num.size()+2);
for(unsigned i=0; i<size(); i++)
for(unsigned j=0; j<num.que.size(); j++)
{
res.que[i+j]+=que[i]*num.que[j];
res.que[i+j+1]+=res.que[i+j]/mod;
res.que[i+j]%=mod;
}
res.count();
res.flag=(flag==num.flag);
return res;
}
inline INT operator/(const INT&num)const
{
INT res,now;
res.que.resize(size()+1);
for(int i=size()-1; i>=0; i--)
{
now.lmove(1);
now.que[0]=que[i];
now.count();
LL left=0,right=mod,mid;
while(left<right)
{
mid=(left+right)/2;
if(num*mid<=now)
left=mid+1;
else
right=mid;
}
res.que[i]=right-1;
now-=num*(right-1);
}
res.count();
return res;
}
inline INT operator%(const INT &num)const
{
INT nowa=*this,nowb=num;
nowa.flag=nowb.flag=1;
INT res=nowa-nowa/nowb*nowb;
res.flag=flag;
return res;
}
inline INT operator-()const
{
INT res=*this;
res.flag^=flag;
return res;
}
inline INT operator+=(const INT &num)
{
return *this=*this+num;
}
inline INT operator-=(const INT &num)
{
return *this=*this-num;
}
inline INT operator*=(const INT& num)
{
return *this=*this*num;
}
inline INT operator/=(const INT& num)
{
return *this=*this/num;
}
inline INT operator++()
{
*this=*this+1;
return *this;
}
inline INT operator++(int)
{
INT old=*this;
++(*this);
return old;
}
inline INT& operator--()
{
*this=*this-1;
return *this;
}
inline INT operator--(int)
{
INT old=*this;
--(*this);
return old;
}
inline bool operator<(const INT &num)const
{
if(flag^num.flag)
return num.flag;
if(size()!=num.size())
return flag?size()<num.size():size()>num.size();
for(int i=que.size()-1; i>=0; i--)
if(que[i]!=num.que[i])
return flag?que[i]<num.que[i]:que[i]>num.que[i];
return !flag;
}
inline bool operator<=(const INT &num)const
{
return !(*this>num);
}
inline bool operator>(const INT &num)const
{
return num<*this;
}
inline bool operator>=(const INT &num)const
{
return !(*this<num);
}
inline bool operator==(const INT &num)const
{
return !(num!=*this);
}
inline bool operator!=(const INT &num)const
{
return *this>num||*this<num;
}
inline bool operator!()const
{
return *this!=0?1:0;
}
inline string to_str()const
{
ULL now=que[size()-1];
string res,str;
while(now)
{
str.push_back(now%10+'0');
now/=10;
}
reverse(str.begin(),str.end());
res=str;
for(int i=size()-2; i>=0; i--)
{
str="";
now=que[i];
for(unsigned j=0; j<8; now/=10,j++)
str.push_back(now%10+'0');
reverse(str.begin(),str.end());
res+=str;
}
if(res=="")
res="0";
if(!flag&&res!="0")
res="-"+res;
return res;
}
};
inline istream& operator>>(istream &in,INT &now)
{
string ined;
in>>ined;
now=ined;
return in;
}
inline ostream& operator<<(ostream &out,const INT &now)
{
out<<now.to_str();
return out;
}
INT pow(INT base_num,INT index)
{
INT res=1;
while(!(!index))
{
if(index%2==1)
res*=base_num;
base_num*=base_num;
index/=2;
}
return res;
}
INT pow(INT base_num,INT index,INT mod)
{
INT res=1;
while(!(!index))
{
if(index%2==1)
res=res*base_num%mod;
base_num=base_num*base_num%mod;
index/=2;
}
return res;
}
INT sqrt(INT x)
{
if(x<0)
throw(x);
if(x<4)
return 1;
INT l=0,r=x,mid;
while(r-l>1)
{
mid=(l+r)/2;
if(mid*mid>x)
r=mid;
else
l=mid;
}
return l;
}
class trienode
{
public:
trienode**nxt,**fa;
bool fend;
int dep;
trienode()
{
nxt=fa=nullptr;
fend=0;
dep=0;
}
~trienode()
{
if(nxt)
delete nxt;
if(fa)
delete fa;
}
void begin()
{
nxt=new trienode*[26];
fa=new trienode*[20];
fill(nxt,nxt+26,nullptr);
fill(fa,fa+20,nullptr);
}
};
class trie
{
protected:
trienode*root;
public:
trie()
{
root=new trienode();
}
~trie()
{
delete root;
}
void insert(string str)
{
trienode*p=root;
for(unsigned i=0; i<str.size(); i++)
{
if(p->nxt[str[i]-'a']==nullptr)
p->nxt[str[i]-'a']=new trienode();
p=p->nxt[str[i]-'a'];
}
p->fend=1;
}
bool find(string str)
{
trienode*p=root;
for(unsigned i=0; i<str.size()&&p; i++)
p=p->nxt[str[i]-'a'];
return p&&p->fend;
}
bool findpre(string pre)
{
trienode*p=root;
for(unsigned i=0; i<pre.size()&&p; i++)
p=p->nxt[pre[i]-'a'];
return p;
}
};
template<typename T>T pow(T base_num,T index)
{
T res=1;
while(index)
{
if(index&1)
res*=base_num;
base_num*=base_num;
index>>=1;
}
return res;
}
template<typename T>T pow(T base_num,T index,T mod)
{
T res=1;
while(index)
{
if(index&1)
res=res*base_num%mod;
base_num=base_num*base_num%mod;
index>>=1;
}
return res;
}
template<typename T>int log(T base_num,T index)
{
int ans=0;
while(index/=base_num)
ans++;
return ans;
}
template<typename T>T sqr(T x)
{
return x*x;
}
template<typename T>double dist(T x_1,T y_1,T x_2,T y_2)
{
return sqrt(sqr(x_1-x_2)+sqr(y_1-y_2));
}
template<typename T>int sgn(T x,T y)
{
return x>0?1:!x?0:-1;
}
bool is_prime(int n)
{
if(n==2||n==3)
return true;
if((n%6!=1&&n%6!=5)||n==1)
return false;
for(int i=5; i*i<=n; i+=6)
if(n%i==0||n%(i+2)==0)
return false;
return true;
}
template<typename T>void prime_table(int length,T f[])
{
fill(f,f+length,1);
f[0]=f[1]=0;
for(int nowa=2; nowa<=length; nowa++)
if(f[nowa]==1)
for(int nowb=2; nowb*nowa<=length; nowb++)
f[nowa*nowb]=0;
}
void read() {}
template<typename T1,typename ...T2>void read(T1 &num,T2&... rest)
{
num=0;
bool flag=0;
char ch;
while(!isdigit(ch=getchar()))
flag=ch=='-';
do
num=num*10+ch-'0';
while(isdigit(ch=getchar()));
if(flag)
num=-num;
read(rest...);
}
template<typename T>void write(T num)
{
if(num<0)
putchar('-'),num=-num;
if(num>9)
write(num/10);
putchar(num%10+'0');
}
template<const char ch=' '>void write() {}
template<const char ch=' ',typename T,typename ...arr>void write(T num,arr... rest)
{
write(num);
if(ch!=-1)
putchar(ch);
write<ch>(rest...);
}
}
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
//char B[1<<15],*S,*T;
#endif
```