OI模板-其他
快读快写
测试 T256742 快读测试
稳定版：
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;测试版（更快），但没有经过时间的检验。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
#define gc() readchar()
#define pc(a) printchar(a)
#define SIZ (int)(1e6+15)
char buf2[SIZ],buf1[SIZ],*p1,*p2,*O=buf2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
void printans(){fwrite(buf2,O-buf2,1,stdout); O=buf2;}
void printchar(char ch){ *O++=ch; if(O-buf2 > SIZ-5) printans();}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N ((int)())
int n,x;
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
read(n);
while(n--)
read(x),write(x),pc('\n');
printans();
return 0;
}还有个快的离谱的版本，不是我写的
namespace __fastio
{
const int bufl=1<<20;
const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
struct IN{
FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
template<typename Temp>inline void getInt(Temp &a)
{a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
template<typename Temp>inline void getDouble(Temp &a)
{a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();
if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
IN& operator>>(char &a){a=getChar();return *this;}
IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
IN& operator>>(string &a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
IN& operator>>(int &a){getInt(a);return *this;}
# ifndef int
IN& operator>>(long long &a){getInt(a);return *this;}
# endif
IN& operator>>(__int128 &a){getInt(a);return *this;}
IN& operator>>(float &a){getDouble(a);return *this;}
IN& operator>>(double &a){getDouble(a);return *this;}
# ifndef double
IN& operator>>(long double &a){getDouble(a);return *this;}
# endif
};
struct OUT{
FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}
inline void ChangEps(int x=6){Eps=x;}
inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
inline void putChar(int a){*os++=a;if(os==ot)flush();}
template<typename Temp>inline void putInt(Temp a)
{if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
template<typename Temp>inline void putDouble(Temp a)
{if(a<0){putChar(45);a=-a;}__int128 b=a;putInt(b);a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putInt(b);}
OUT& operator<<(char a){putChar(a);return *this;}
OUT& operator<<(char *a){while(*a>32)putChar(*a++);return *this;}
OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
OUT& operator<<(int a){putInt(a);return *this;}
# ifndef int
OUT& operator<<(long long a){putInt(a);return *this;}
# endif
OUT& operator<<(__int128 a){putInt(a);return *this;}
OUT& operator<<(float a){putDouble(a);return *this;}
OUT& operator<<(double a){putDouble(a);return *this;}
# ifndef double
OUT& operator<<(long double a){putDouble(a);return *this;}
# endif
~OUT(){flush();}
};
}using __fastio::IN;using __fastio::OUT; IN fin; OUT fout;模拟退火
求 $n(n \le 10^3)$ 个点的带权类费马点。
三角形的不带权费马点就是 $PA + PB + PC$ 取到最小值的点 $P$ 。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3+15))
int n,x[N],y[N],w[N],st=clock();
double ansx, ansy, dis; int _;
mt19937_64 _rd(time(0) + (unsigned int)(&_));
double rd() { return (double)_rd() / UINT64_MAX; }
double Time() { return ((double)clock()-st) / CLOCKS_PER_SEC; }
double calc(double nx, double ny)
{
double res = 0;
for(int i=1; i<=n; i++)
{
double dx = x[i] - nx, dy = y[i] - ny;
res += sqrt(dx * dx + dy * dy) * w[i]; // 带权类费马点
}
if(res < dis) { dis = res, ansx = nx, ansy = ny; }
return res;
}
void sa() // simulateAnneal
{
double t = 1e5, x = ansx, y = ansy; // 初始值
for(; t > 1e-3; t *= 0.997)
{
double tx = x + t * (rd() * 2 - 1);
double ty = y + t * (rd() * 2 - 1);
double delta = calc(tx,ty) - calc(x,y);
if(exp( -delta / t ) > rd()) tie(x,y) = tie(tx,ty);
}
for(int i=1; i<=1000; i++)
{
double tx = ansx + t * (rd() * 2 - 1);
double ty = ansy + t * (rd() * 2 - 1);
calc(tx,ty);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cout << fixed << setprecision(3);
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> x[i] >> y[i] >> w[i];
ansx += x[i]; ansy += y[i];
}
ansx /= n; ansy /= n; dis = calc(ansx, ansy); // 初值
while(Time() < 0.85) sa();
cout << ansx << ' ' << ansy << '\n';
return 0;
}光速幂
仅适用于int 且 底数相同，即 $a^b$ ， $a$ 不变，复杂度约为 $O(\sqrt{n})$
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)
int a,b,p;
int pw1[N],pw2[N];
int solve()
{
pw1[0]=pw2[0]=1;
for(int i=1; i<1<<17; i++)
pw1[i]=pw1[i-1]*a%p;
pw2[1]=pw1[(1<<17)-1]*a%p;
for(int i=2; i<1<<17; i++)
pw2[i]=pw2[i-1]*pw2[1]%p;
return pw1[b&131071]*pw2[b>>17]%p;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
scanf("%lld%lld%lld",&a,&b,&p);
printf("%lld^%lld mod %lld=%lld\n",a,b,p,solve());
return 0;
}O(1)快速乘
// 以下是O(1)快速乘+快速幂，可以防 10^18 的情况
#define int long long
int mul(int a,int b,int p)
{
int res=(__int128)a*b%p;
return res;
}
int qpow(int a,int b,int p)
{
int ans=1,base=a;
while(b)
{
if(b&1)ans=mul(ans,base,p);
base=mul(base,base,p);
b>>=1;
}
return ans;
}二维数点
二维数点 分治
二维CDQ
时间复杂度 $O(n\log n)$
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(5e5+15)
struct node
{
int x,y,typ,add,id,ans;
}t[N*5],tmp[N*5];
int n,Q,pos,ans[N];
void add(int a,int b,int c,int d=0,int e=0)
{
t[++pos]={a,b,c,d,e};
}
bool cmp(node a,node b)
{
if(a.x==b.x)
return a.typ<b.typ;
return a.x<b.x;
}
void cdq(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
int i=mid+1,j=l,res=0,cnt=0;
for(;i<=r; i++)
{
while(t[j].y<=t[i].y&&j<=mid)
{
if(t[j].typ==1)++res;
tmp[++cnt]=t[j++];
}
if(t[i].typ==2)t[i].ans+=res;
tmp[++cnt]=t[i];
}
while(j<=mid)
tmp[++cnt]=t[j++];
for(int i=1; i<=cnt; i++)
t[l+i-1]=tmp[i];
}
signed main()
{
read(n);read(Q);
for(int i=1,x,y; i<=n; i++)
{
read(x);read(y);
add(x,y,1);
}
for(int i=1,a,b,c,d; i<=Q; i++)
{
read(a);read(b);read(c);read(d);
add(a-1,b-1, 2, 1,i);
add( c, d, 2, 1,i);
add(a-1, d, 2,-1,i);
add( c,b-1, 2,-1,i);
}
sort(t+1,t+1+pos,cmp);
cdq(1,pos);
for(int i=1; i<=pos; i++)
{
if(t[i].typ==2)
ans[t[i].id]+=t[i].add*t[i].ans;
}
for(int i=1; i<=Q; i++)
write(ans[i]),pc('\n');
return 0;
}二维数点 树状数组
时间复杂度 $O(n\log n)$
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(5e5+15)
struct node
{
int x,y,typ,add,id,ans;
}t[N*5];
int n,Q,pos,tree[N],tmp[N*5],ans[N];
void addQ(int a,int b,int c,int d=0,int e=0)
{
t[++pos]={a,b,c,d,e};
}
#define lowbit(x) (x&(-x))
void add(int x,int v)
{
while(x&&x<=n)
{
tree[x]+=v;
x+=lowbit(x);
}
}
int sum(int x)
{
int res=0;
while(x>=1)
{
res+=tree[x];
x-=lowbit(x);
}
return res;
}
bool cmp(node a,node b)
{
if(a.x==b.x)
return a.typ<b.typ;
return a.x<b.x;
}
void init()
{
for(int i=1; i<=pos; i++)
tmp[i]=t[i].y;
sort(tmp+1,tmp+1+pos);
int len=unique(tmp+1,tmp+1+pos)-tmp-1;
for(int i=1; i<=pos; i++)
t[i].y=lower_bound(tmp+1,tmp+1+len,t[i].y)-tmp;
}
signed main()
{
read(n);read(Q);
for(int i=1,x,y; i<=n; i++)
{
read(x);read(y);
addQ(x,y,1);
}
for(int i=1,a,b,c,d; i<=Q; i++)
{
read(a);read(b);read(c);read(d);
addQ(a-1,b-1,2,1,i);
addQ(c,d,2,1,i);
addQ(a-1,d,2,-1,i);
addQ(c,b-1,2,-1,i);
}
init();
sort(t+1,t+1+pos,cmp);
for(int i=1; i<=pos; i++)
{
if(t[i].typ==1)
add(t[i].y,1);
if(t[i].typ==2)
t[i].ans+=sum(t[i].y);
}
for(int i=1; i<=pos; i++)
{
if(t[i].typ==2)
ans[t[i].id]+=t[i].add*t[i].ans;
}
for(int i=1; i<=Q; i++)
write(ans[i]),pc('\n');
return 0;
}乘法取模封装
需要头文件 cstdarg
请注意：如果 #define int long long ，则传入的常参数必须是 long long 型，否则会出现 UB ！！
int mul(int cnt, ...)
{
va_list ptr; va_start(ptr,cnt);
int res=1;
for(int i=0; i<cnt; i++)
res=1ll*res*va_arg(ptr,int)%mod;
va_end(ptr);
return res;
}调用方式如下：
计算 $(a \times b \times c \times d )\bmod M$
ans = mul(4, a, b, c, d);
