Skip to content

Instantly share code, notes, and snippets.

@fjzzq2002

fjzzq2002/acm_templates.cpp

Created October 17, 2016 15:06
Show Gist options
  • Save fjzzq2002/3706ca3bf75814f67a888c7c5e563327 to your computer and use it in GitHub Desktop.
Save fjzzq2002/3706ca3bf75814f67a888c7c5e563327 to your computer and use it in GitHub Desktop.
Download ZIP
ACM Templates
Raw
acm_templates.cpp
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#define SZ 666666
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int aa,bb;int F(){
while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
}
#define gi F()
#define gc getc()
namespace mergeable_heap
{
int ch[SZ][2],dis[SZ],v[SZ];
int merge(int a,int b)
{
if(!a||!b) return a+b;
if(v[a]<v[b]) swap(a,b);
ch[a][1]=merge(ch[a][1],b);
if(dis[ch[a][0]]<dis[ch[a][1]]) swap(ch[a][0],ch[a][1]);
if(!ch[a][1]) dis[a]=0;
else dis[a]=dis[ch[a][1]]+1;
return a;
}
int pop(int a)
{
int t=merge(ch[a][0],ch[a][1]);
ch[a][0]=ch[a][1]=dis[a]=0;
return t;
}
}
namespace splayy
{
int n,m,ch[SZ][2],siz[SZ],vs[SZ],fa[SZ],root,an=0;
bool rev[SZ];
void pd(int x)
{
if(!rev[x]) return;
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1; rev[ch[x][1]]^=1;
rev[x]=0;
}
void upd(int x)
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
void rot(int x)
{
pd(fa[x]); pd(x);
int y=fa[x],c=ch[y][0]==x; fa[x]=fa[y];
if(fa[y]) ch[fa[y]][ch[fa[y]][1]==y]=x;
int h=ch[x][c]; ch[y][!c]=h;
if(h) fa[h]=y; ch[x][c]=y; fa[y]=x;
upd(y); upd(x);
}
int ss[SZ],sn=0;
void splay(int x,int f)
{
int cur=x;
while(cur!=f) ss[++sn]=cur, cur=fa[cur];
while(sn) pd(ss[sn--]);
while(fa[x]!=f)
{
int y=fa[x];
if(fa[y]!=f)
{
if(ch[fa[y]][1]==y^ch[y][1]==x) rot(x);
else rot(y);
}
rot(x);
}
if(!f) root=x;
}
void splayp(int x,int f)
{
int p=root; pd(p);
while(siz[ch[p][0]]!=x-1)
{
if(siz[ch[p][0]]<x-1) x-=siz[ch[p][0]]+1, p=ch[p][1];
else p=ch[p][0];
pd(p);
}
splay(p,f);
}
void addnode(int& x,int f,int v)
{
x=++an; ch[x][0]=ch[x][1]=rev[x]=0; fa[x]=f; siz[x]=1; vs[x]=v;
}
void build(int& x,int f,int l,int r)
{
if(l>r) {x=0; return;}
int mid=l+r>>1;
addnode(x,f,mid);
build(ch[x][0],x,l,mid-1);
build(ch[x][1],x,mid+1,r);
upd(x);
}
#define RRL ch[ch[root][1]][0]
void init()
{
addnode(root,0,0);
addnode(ch[root][1],root,0);
build(RRL,ch[root][1],1,n);
upd(ch[root][1]); upd(root);
}
void revs(int l,int r)
{
splayp(l,0);
splayp(r+2,root);
rev[RRL]^=1;
}
int as[SZ],asn=0;
void prt(int x)
{
if(!x) return;
pd(x);
prt(ch[x][0]);
if(vs[x]) as[++asn]=vs[x];
prt(ch[x][1]);
}
}
namespace splayy2
{
int ch[SZ][2],root,fa[SZ],siz[SZ],val[SZ],an=2;
void upd(int x) {siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
void rot(int x)
{
if(!fa[x]) return;
int y=fa[x],c=ch[y][0]==x;
int z=fa[y]; fa[x]=z; if(z) ch[z][ch[z][1]==y]=x; fa[y]=x;
int t=ch[x][c]; ch[y][!c]=t; if(t) fa[t]=y; ch[x][c]=y;
upd(y); if(!fa[x]) root=x;
}
void splay(int x,int f)
{
while(fa[x]!=f)
{
int y=fa[x],z=fa[y];
if(z!=f)
{
if(ch[z][0]==y^ch[y][0]==x) rot(x);
else rot(y);
}
rot(x);
}
upd(x);
if(!f) root=x;
}
void ins(int x)
{
int *c=&root,f=0;
while(*c)
{
f=*c;
if(x<=val[*c]) c=&ch[*c][0];
else c=&ch[*c][1];
}
*c=++an; val[an]=x; siz[an]=1; fa[an]=f;
splay(an,0);
}
void del(int x)
{
int c=root;
while(c)
{
if(x==val[c]) break;
if(x<=val[c]) c=ch[c][0];
else c=ch[c][1];
}
//del pos c.
if(val[c]!=x)
{
printf("WHAT THE HELL!!!!!!\n");
return;
}
splay(c,0);
int ll=ch[c][0],rr=ch[c][1];
fa[ll]=fa[rr]=0;
//可以回收f节点（懒得写）
if(!ll) swap(ll,rr);
if(!rr) {root=ll; return;}
while(ch[ll][1]) ll=ch[ll][1];
fa[rr]=ll; ch[ll][1]=rr;
splay(rr,0);
}
int rank(int x)
{
int c=root,ts=0,f;
while(c)
{
f=c;
if(x<=val[c]) c=ch[c][0];
else ts+=siz[ch[c][0]]+1, c=ch[c][1];
}
splay(f,0);
return ts+1;
}
int grn(int r)
{
int c=root;
while(siz[ch[c][0]]!=r-1)
{
if(siz[ch[c][0]]+1>r) c=ch[c][0];
else r-=siz[ch[c][0]]+1, c=ch[c][1];
}
splay(c,0);
return val[c];
}
void init()
{
root=1; siz[1]=2; val[1]=-1234567890;
ch[1][1]=2; siz[2]=1; val[2]=1234567890; fa[2]=1;
}
int pre(int x)
{
int maxn=-1234567890,c=root,f;
while(c)
{
f=c;
if(val[c]<x) maxn=max(maxn,val[c]), c=ch[c][1];
else c=ch[c][0];
}
splay(f,0);
return maxn;
}
int nxt(int x)
{
int minn=1234567890,c=root,f;
while(c)
{
f=c;
if(val[c]>x) minn=min(minn,val[c]), c=ch[c][0];
else c=ch[c][1];
}
splay(f,0);
return minn;
}
}
namespace lct
{
int n,m,ch[SZ][2],vv[SZ],fa[SZ],root,an=0,mx[SZ];
bool rev[SZ];
void pd(int x)
{
if(!rev[x]) return;
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]=0;
}
bool top(int x) {return !(ch[fa[x]][0]==x||ch[fa[x]][1]==x);}
void upd(int x)
{
mx[x]=x;
if(vv[mx[ch[x][0]]]>vv[mx[x]]) mx[x]=mx[ch[x][0]];
if(vv[mx[ch[x][1]]]>vv[mx[x]]) mx[x]=mx[ch[x][1]];
}
void rot(int x)
{
int y=fa[x],c=ch[y][0]==x; fa[x]=fa[y];
if(!top(y)) ch[fa[y]][ch[fa[y]][1]==y]=x;
int h=ch[x][c]; ch[y][!c]=h;
if(h) fa[h]=y; ch[x][c]=y; fa[y]=x;
upd(y); upd(x);
}
int ss[SZ],sn=0;
void splay(int x)
{
for(int c=x;;c=fa[c])
{
ss[++sn]=c;
if(top(c)) break;
}
while(sn) pd(ss[sn--]);
while(!top(x))
{
int y=fa[x];
if(!top(y))
{
if(ch[fa[y]][1]==y^ch[y][1]==x) rot(x);
else rot(y);
}
rot(x);
}
}
void access(int x)
{
for(int c=0;x;c=x,x=fa[x]) splay(x), ch[x][1]=c, upd(x);
}
void makeroot(int x) {access(x); splay(x); rev[x]^=1;}
void link(int a,int b) {makeroot(a); fa[a]=b;}
void cut(int a,int b)
{makeroot(a); access(b); splay(b); ch[b][0]=fa[a]=0;}
int findroot(int x)
{
access(x); splay(x);
while(ch[x][0]) x=ch[x][0];
splay(x); return x;
}
int getrd(int a,int b)
{makeroot(a); access(b); splay(b); return b;}
}
namespace AMs
{
#define S 26
struct AM
{
int rot,ch[SZ][S],C,cnt[SZ];
};
struct SeqAM: public AM
{
int par[SZ],lst[S];
SeqAM()
{
C=rot=1;
for(int i=0;i<S;i++) lst[i]=rot;
}
void ins(char c)
{
++C; par[C]=lst[c];
for(int i=0;i<S;i++)
{
for(int g=lst[i];g&&!ch[g][c];g=par[g]) ch[g][c]=C;
}
lst[c]=C;
}
void getcnt()
{
for(int i=1;i<=C;i++) cnt[i]=1;
for(int i=C;i>=1;i--)
{
for(int j=0;j<S;j++) cnt[i]+=cnt[ch[i][j]];//, cnt[i]%=MOD;
}
}
}SeqA,SeqB;
struct SufAM: public AM
{
int ml[SZ],fail[SZ],lst,cl,qzh[SZ],od[SZ];
SufAM() {C=lst=rot=1; cl=0;}
void ins(char c)
{
int x=++C,len=++cl,p=lst;
lst=x; ml[x]=len;
for(;p&&!ch[p][c];p=fail[p]) ch[p][c]=x;
if(!p) fail[x]=rot;
else if(ml[ch[p][c]]==ml[p]+1) fail[x]=ch[p][c];
else
{
int chh=ch[p][c],cm=++C;
ml[cm]=ml[p]+1; fail[cm]=fail[chh];
for(int i=0;i<S;i++) ch[cm][i]=ch[chh][i];
fail[chh]=fail[x]=cm;
for(;ch[p][c]==chh;p=fail[p]) ch[p][c]=cm;
}
}
void getcnt()
{
for(int i=0;i<SZ;i++) qzh[i]=0;
for(int i=1;i<=C;i++) qzh[ml[i]]++;
for(int i=1;i<SZ;i++) qzh[i]+=qzh[i-1];
for(int i=1;i<=C;i++) od[qzh[ml[i]]--]=i;
for(int i=1;i<=C;i++) cnt[i]=1;
for(int i=C;i>=1;i--)
{
for(int j=0;j<S;j++) cnt[od[i]]+=cnt[ch[od[i]][j]];//, cnt[od[i]]%=MOD;
}
}
}SufA,SufB;
#undef S
}
namespace SA
{
#define P 20
int n,k,sa[SZ],t[SZ],rank[SZ],qzh[SZ],tmpsa[SZ],tmpr[SZ],h[SZ];
char s[SZ];
bool same(int a,int b,int p) {return t[a]==t[b]&&t[a+p]==t[b+p];}
void getsa(int m=500)
{
s[++n]=0;
for(int i=0;i<n;i++) rank[i]=s[i], ++qzh[rank[i]];
for(int i=1;i<m;i++) qzh[i]+=qzh[i-1];
for(int i=n-1;i>=0;i--) sa[--qzh[rank[i]]]=i;
for(int j=1;j<=n;j<<=1)
{
int cur=-1;
for(int i=n-j;i<n;i++) tmpsa[++cur]=i;
for(int i=0;i<n;i++) if(sa[i]>=j) tmpsa[++cur]=sa[i]-j;
for(int i=0;i<n;i++) tmpr[i]=rank[tmpsa[i]];
for(int i=0;i<m;i++) qzh[i]=0;
for(int i=0;i<n;i++) ++qzh[tmpr[i]];
for(int i=1;i<m;i++) qzh[i]+=qzh[i-1];
for(int i=n-1;i>=0;i--) t[i]=rank[i], sa[--qzh[tmpr[i]]]=tmpsa[i];
m=0;
for(int i=0;i<n;i++)
rank[sa[i]]=(i>0&&same(sa[i],sa[i-1],j))?m:++m;
++m;
}
for(int i=0;i<n;i++) rank[sa[i]]=i;
int p=0;
for(int i=0;i<n;i++)
{
if(p) --p;
int ls=sa[rank[i]-1];
while(s[ls+p]==s[i+p]) p++;
h[rank[i]]=p;
}
--n;
for(int i=1;i<=n;i++) sa[i-1]=sa[i];
for(int i=0;i<n;i++) rank[sa[i]]=i;
for(int i=2;i<=n;i++) h[i-1]=h[i];
h[n]=sa[n]=0;
}
int log2[SZ],minn[SZ][P];
void getst()
{
for(int i=0;i<n;i++) minn[i][0]=h[i];
for(int i=1;i<=n;i++)
{
int t=0;
while((1<<t)<=i) ++t;
log2[i]=t-1;
}
for(int j=1;j<P;j++)
{
for(int i=0;i<n;i++)
{
if(i+(1<<j)<=n) minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
else minn[i][j]=-2333;
}
}
}
int gmin(int a,int b)
{
int l2=log2[b-a+1];
return min(minn[a][l2],minn[b-(1<<l2)+1][l2]);
}
int lcp(int a,int b)
{
if(a==b) return n-a;
if(rank[a]>rank[b]) swap(a,b);
return gmin(rank[a]+1,rank[b]);
}
}
namespace HashKMPs
{
typedef long long ll;
ll MOD=1000000007,cm[SZ],cmn[SZ];
ll qp(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%MOD;
a=a*a%MOD; b>>=1;
}
return ans;
}
struct HashKMP
{
char s[SZ+1]; int n;
ll hash[SZ+1];
void pre()
{
n=strlen(s);
for(int i=n-1;i>=0;i--) hash[i]=(hash[i+1]+cm[n-1-i]*(s[i]-'a'+1)%MOD)%MOD;
}
ll ghash(int l,int r)
{
return ((hash[l]-hash[r+1])*cmn[n-1-r]%MOD+MOD)%MOD;
}
int next[SZ+3];
void gnext()
{
next[0]=-1;
int j=-1;
for(int i=1;s[i];i++)
{
while(j!=-1&&s[i]!=s[j+1]) j=next[j];
if(s[i]==s[j+1]) ++j;
next[i]=j;
}
}
void kmp(char* a)
{
int j=-1;
for(int i=0;a[i];i++)
{
while(j!=-1&&s[j+1]!=a[i]) j=next[j];
if(s[j+1]==a[i]) ++j;
//do sth
printf("%d w %d\n",i,j);
}
}
}ha;
void getcm()
{
cm[0]=cmn[0]=1; ll gg=qp(31,MOD-2);
for(int i=1;i<SZ;i++) cm[i]=cm[i-1]*31%MOD;
for(int i=1;i<SZ;i++) cmn[i]=cmn[i-1]*gg%MOD;
}
}
namespace ACAM
{
int rot=1,ch[SZ][29],fail[SZ],cnt[SZ],e=1;
void insert(char* s)
{
int cur=rot;
for(int i=0;s[i];i++)
{
int c=s[i]-'a';
if(!ch[cur][c]) ch[cur][c]=++e;
cur=ch[cur][c];
}
cnt[cur]++;
}
int qs[SZ],h=0,t=0;
void bfail()
{
h=t=0; fail[rot]=rot;
for(int i=0;i<26;i++)
{
if(!ch[rot][i])
{
ch[rot][i]=rot; continue;
}
fail[ch[rot][i]]=rot;
qs[t++]=ch[rot][i];
}
while(h!=t)
{
int cur=qs[h++];
for(int c=0;c<26;c++)
{
if(!ch[cur][c]) ch[cur][c]=ch[fail[cur]][c];
else
{
fail[ch[cur][c]]=ch[fail[cur]][c];
qs[t++]=ch[cur][c];
}
}
}
}
int match(char* s)
{
int cur=rot,ans=0;
for(int i=0;s[i];i++)
{
int c=s[i]-'a'; cur=ch[cur][c];
for(int f=cur;f!=rot;f=fail[f]) ans+=cnt[f], cnt[f]=0;
}
return ans;
}
}
namespace Manachers
{
int p[SZ];
char str[SZ];
void manacher()
{
int ml=0,id;
for(int i=0;str[i];i++)
{
if(ml>i) p[i]=min(p[2*id-i],p[id]+id-i);
else p[i]=1;
while(i>=p[i]&&str[i+p[i]]==str[i-p[i]]) ++p[i];
if(p[i]+i>ml) ml=p[i]+i, id=i;
}
}
char s[SZ];
void init()
{
str[0]='$'; int n=1;
for(int i=0;s[i];i++) str[n++]=s[i], str[n++]='$';
str[n]=0;
}
}
namespace PTrees
{
struct PTree
{
#define SZ 666666
int ch[SZ][26],len[SZ],fail[SZ],cnt[SZ],s[SZ],cl,an,lst;
int addn(int l) {len[an]=l; return an++;}
PTree()
{
cl=an=lst=0;
memset(ch,0,sizeof(ch));
addn(0); addn(-1);
fail[0]=1; s[0]=-233;
}
int gfail(int x,int l)
{
while(s[l-len[x]-1]!=s[l]) x=fail[x];
return x;
}
void add(int c)
{
s[++cl]=c;
int cp=gfail(lst,cl);
if(!ch[cp][c])
{
int nn=addn(len[cp]+2);
fail[nn]=ch[gfail(fail[cp],cl)][c];
ch[cp][c]=nn;
}
cnt[lst=ch[cp][c]]++;
}
void getcnt()
{
for(int i=an-1;i>=2;i--) cnt[fail[i]]+=cnt[i];
}
}pt;
}
namespace FFTer
{
ll MOD=998244353;
ll w[2][SZ];
ll qp(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%MOD;
a=a*a%MOD; b>>=1;
}
return ans;
}
int K;
void fftinit(int n)
{
for(K=1;K<n;K<<=1);
w[0][0]=w[0][K]=1;
ll g=qp(3,(MOD-1)/K); //g=3
for(int i=1;i<K;i++) w[0][i]=w[0][i-1]*g%MOD;
for(int i=0;i<=K;i++) w[1][i]=w[0][K-i];
}
void fft(ll* x,int v)
{
for(int i=0,j=0;i<K;i++)
{
if(i>j) {x[i]^=x[j]; x[j]^=x[i]; x[i]^=x[j];}
for(int l=K>>1;(j^=l)<l;l>>=1);
}
for(int i=2;i<=K;i<<=1)
{
for(int j=0;j<K;j+=i)
{
for(int l=0;l<i>>1;l++)
{
ll t=(ll)x[j+l+(i>>1)]*w[v][K/i*l]%MOD;
x[j+l+(i>>1)]=(x[j+l]-t+MOD)%MOD;
x[j+l]=(x[j+l]+t)%MOD;
}
}
}
if(!v) return;
ll rv=qp(K,MOD-2);
for(int i=0;i<K;i++) x[i]=x[i]*rv%MOD;
}
void FFT_(ll* a,ll* b,ll* c)
{
fft(a,0); fft(b,0);
for(int i=0;i<K;i++) c[i]=a[i]*b[i]%MOD;
fft(c,1);
}
ll gcd(ll a,ll b)
{
if(a<0) a=-a;
if(b<0) b=-b;
while(b) {ll t=a%b; a=b; b=t;}
return a;
}
void ex_gcd(ll a,ll b,ll& x,ll& y)
{
if(!b) {x=1; y=0; return;}
ex_gcd(b,a%b,x,y);
ll y_=x-a/b*y; x=y; y=y_;
}
ll exgcd(ll a,ll b,ll c)
{
ll gg=gcd(a,b);
if(c%gg) return -2333;
a/=gg; b/=gg; c/=gg;
ll x,y;
ex_gcd(a,b,x,y);
x=x*c; x%=b; y=(c-x*a)/b;
return x;
}
ll M1=1866465281,M2=1998585857;
ll a1[SZ],b1[SZ],c1[SZ];
ll a2[SZ],b2[SZ],c2[SZ];
void FFT(ll* a,ll* b,ll* c,int n)
{
MOD=M1;
fftinit(n+n);
for(int i=0;i<K;i++) a1[i]=b1[i]=c1[i]=a2[i]=b2[i]=c2[i]=0;
for(int i=0;i<n;i++) a1[i]=a[i]%M1, a2[i]=a[i]%M1;
for(int i=0;i<n;i++) b1[i]=b[i]%M1, b2[i]=b[i]%M2;
FFT_(a1,b1,c1);
MOD=M2;
fftinit(n+n);
FFT_(a2,b2,c2);
for(int i=0;i<n+n;i++)
{
ll p=exgcd(M1,M2,c2[i]-c1[i]);
ll x=p*M1+c1[i],m=M1*M2;
c[i]=(x%m+m)%m;
}
}
}
//I don't think I'll need it...
namespace KDTree
{
struct pnt
{
int _x,_y;
pnt() {}
pnt(int x,int y) {_x=x; _y=y;}
};
int Abs(int x) {return (x>=0)?x:-x;}
int dis(pnt a,pnt b) {return Abs(a._x-b._x)+Abs(a._y-b._y);}
bool dim_;
bool cmp(pnt a,pnt b)
{
if(!dim_) return a._x<b._x||(a._x==b._x&&a._y<b._y);
else return a._y<b._y||(a._y==b._y&&a._x<b._x);
}
int rot,M=0,ch[SZ][2],inf=1000000000;
pnt pp[SZ],lu[SZ],rd[SZ];
inline int min_(int a,int b)
{
return (a<=b)?a:b;
}
inline int min_(int a,int b,int c)
{
int ans=a;
if(b<ans) ans=b;
if(c<ans) ans=c;
return ans;
}
inline int max_(int a,int b,int c)
{
int ans=a;
if(b>ans) ans=b;
if(c>ans) ans=c;
return ans;
}
void upd(int x)
{
lu[x]._x=min_(lu[ch[x][0]]._x,lu[ch[x][1]]._x,lu[x]._x);
lu[x]._y=min_(lu[ch[x][0]]._y,lu[ch[x][1]]._y,lu[x]._y);
rd[x]._x=max_(rd[ch[x][0]]._x,rd[ch[x][1]]._x,rd[x]._x);
rd[x]._y=max_(rd[ch[x][0]]._y,rd[ch[x][1]]._y,rd[x]._y);
}
int dis(int x,pnt p)
{
int ans=0;
if(p._x<lu[x]._x) ans+=lu[x]._x-p._x;
else if(p._x>rd[x]._x) ans+=p._x-rd[x]._x;
if(p._y<lu[x]._y) ans+=lu[x]._y-p._y;
else ans+=p._y-rd[x]._y;
return ans;
}
void init()
{
rot=M=0;
lu[0]._x=inf; lu[0]._y=inf;
rd[0]._x=-inf; rd[0]._y=-inf;
}
pnt ps[SZ];
int build(int l,int r,bool d=0)
{
if(l>=r) return 0;
int c=++M,m=l+r>>1; dim_=d;
nth_element(ps+l,ps+m,ps+r,cmp);
pp[c]=lu[c]=rd[c]=ps[m];
ch[c][0]=build(l,m,!d);
ch[c][1]=build(m+1,r,!d);
upd(c); return c;
}
int ans;
void query(int x,pnt p)
{
if(!x) return;
ans=min_(ans,dis(p,pp[x]));
int dc[2]={dis(ch[x][0],p),dis(ch[x][1],p)};
int d=dc[0]>dc[1];
query(ch[x][d],p);
if(dc[!d]<ans) query(ch[x][!d],p);
}
void ins(int& x,pnt p)
{
if(!x) {x=++M; pp[x]=lu[x]=rd[x]=p; return;}
int d=!cmp(p,pp[x]); dim_=!dim_;
ins(ch[x][d],p); upd(x);
}
}
namespace Dinic
{
int n,M=1;
typedef long long ll;
int fst[SZ],nxt[SZ],vb[SZ]; ll cap[SZ];
void ad_de_(int a,int b,ll c)
{
++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b; cap[M]=c;
}
void ad_de(int a,int b,ll c)
{
ad_de_(a,b,c); ad_de_(b,a,0);
}
int S,T,q[SZ],d[SZ];
bool bfs()
{
memset(d,-1,sizeof(d));
d[S]=0; q[1]=S; int h=1,t=2;
while(h!=t)
{
int cur=q[h++];
for(int e=fst[cur];e;e=nxt[e])
{
int b=vb[e];
if(d[b]==-1&&cap[e]);else continue;
d[b]=d[cur]+1; q[t++]=b;
}
}
return d[T]!=-1;
}
ll dfs(int x,ll f)
{
if(f<=0) return 0;
if(x==T) return f;
ll ca=0;
for(int e=fst[x];e;e=nxt[e])
{
int b=vb[e];
if(d[b]!=d[x]+1) continue;
ll w=dfs(b,min(cap[e],f-ca));
cap[e]-=w; cap[e^1]+=w; ca+=w;
if(ca==f) break;
}
if(!ca) d[x]=-1;
return ca;
}
#define inf 100000000000000000LL
ll dinic()
{
ll ans=0;
while(bfs()) ans+=dfs(S,inf);
return ans;
}
#undef inf
}
namespace MCF
{
typedef long long ll;
int M=1,S,T,fst[SZ],nxt[SZ],va[SZ],vb[SZ];
ll cap[SZ],cost[SZ];
void ad_de_(int a,int b,ll ca,ll co)
{
++M; nxt[M]=fst[a]; fst[a]=M; va[M]=a; vb[M]=b; cap[M]=ca; cost[M]=co;
}
void ad_de(int a,int b,ll ca,ll co)
{ad_de_(a,b,ca,co); ad_de_(b,a,0,-co);}
ll dis[SZ]; int n,q[SZ],fe[SZ];
bool inq[SZ];
bool spfa()
{
ll inf=2000000000000000LL;
for(int i=1;i<=n;i++) dis[i]=inf;
inq[S]=1; q[1]=S; dis[S]=0; int h=1,t=2;
while(h!=t)
{
int cur=q[h++]; h&=131071;
for(int e=fst[cur];e;e=nxt[e])
{
if(!cap[e]||dis[vb[e]]<=dis[cur]+cost[e]) continue;
int b=vb[e],co=cost[e];
dis[b]=dis[cur]+co; fe[b]=e;
if(!inq[b]) {inq[b]=1; q[t++]=b; t&=131071;}
}
inq[cur]=0;
}
return dis[T]!=inf;
}
ll mcf()
{
ll ans=0;
while(spfa())
{
ll cur=2000000000000000LL;
for(int i=fe[T];i;i=fe[va[i]]) cur=min(cur,cap[i]);
for(int i=fe[T];i;i=fe[va[i]])
{
ans+=cur*cost[i];
cap[i]-=cur; cap[i^1]+=cur;
}
}
return ans;
}
}
namespace Inv
{
int inv[SZ],p;
void pre(int n)
{
inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=ll(p-p/i)*inv[p%i]%p;
}
}
namespace PollardRho
{
typedef long long ll;
ll c_f(ll a,ll b,ll c)
{
if(b==0) return 0;
ll hf=c_f(a,b>>1,c);
hf=(hf+hf)%c;
if(b&1) hf=(hf+a)%c;
return hf;
}
ll cf(ll a,ll b,ll c)
{
a%=c; b%=c;
if(!a||!b) return 0;
if(a<0&&b<0) a=-a,b=-b;
if(b<0) return c-c_f(a,-b,c);
if(a<0) return c-c_f(-a,b,c);
return c_f(a,b,c);
}
ll qp(ll x,ll y,ll m)
{
if(y==0) return 1;
ll hf=qp(x,y>>1,m);
hf=cf(hf,hf,m);
if(y&1) hf=cf(hf,x%m,m);
return hf;
}
bool isprime(ll p)
{
int b=0; ll a=p-1;
while(!(a&1)) ++b, a>>=1;
for(int i=1;i<=10;i++)
{
ll x=rand()%(p-1)+1;
if(qp(x,a,p)==1) goto ct;
for(int j=0;j<b;j++)
{
if(qp(x,a*(1<<j),p)==p-1) goto ct;
}
return 0;
ct:;
}
return 1;
}
ll f(ll x,ll p) {return (cf(x%p,x%p,p)+1)%p;}
ll gcd(ll a,ll b)
{
if(a<0) a=-a;
if(b<0) b=-b;
while(b) {ll g=a%b; a=b; b=g;}
return a;
}
ll pollard_rho(ll m)
{
if(m==1) return 1;
if(m%2==0) return 2;
if(m%3==0) return 3;
if(isprime(m)) return m;
s:
ll x=rand()%m,y=f(x,m),p=1;
while(p==1)
{
x=f(x,m);
y=f(f(y,m),m);
p=gcd(x-y,m);
}
if(p==m) goto s;
return p;
}
#define vll vector<ll>
vll merge(vll a,vll b)
{
vll ans;
int as=0,bs=0;
while(as<a.size()) ans.push_back(a[as++]);
while(bs<b.size()) ans.push_back(b[bs++]);
return ans;
}
vll ysh(ll x)
{
if(x==1) {return vll();}
if(isprime(x)) {vll ans; ans.push_back(x); return ans;}
ll ys; vll ans;
while((ys=pollard_rho(x))!=1)
{
vll cur=ysh(ys);
while(x%ys==0) x/=ys, ans=merge(ans,cur);
}
return ans;
}
}
namespace CRT
{
typedef long long ll;
int n;
ll gcd(ll a,ll b)
{
if(a<0) a=-a;
if(b<0) b=-b;
while(b) {ll t=a%b; a=b; b=t;}
return a;
}
void ex_gcd(ll a,ll b,ll& x,ll& y)
{
if(!b) {x=1; y=0; return;}
ex_gcd(b,a%b,x,y);
ll y_=x-a/b*y; x=y; y=y_;
}
#define GG -233333333333333333LL
ll exgcd(ll a,ll b,ll c)
{
ll gg=gcd(a,b);
if(c%gg) return GG;
a/=gg; b/=gg; c/=gg;
ll x,y;
ex_gcd(a,b,x,y);
x=x*c; x%=b; y=(c-x*a)/b;
return x;
}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
typedef pair<ll,ll> pll;
//mod fi=se
pll merge(pll a,pll b)
{
ll s=exgcd(a.fi,b.fi,b.se-a.se);
if(s==GG); //do sth
ll x=s*a.fi+a.se;
ll lc=lcm(a.fi,b.fi);
return pll(lc,(x%lc+lc)%lc);
}
#undef GG
}
namespace PSeg
{
#define S2 5555555
int ch[S2][2],rot[SZ],sum[S2],an=0;
void ins(int r1,int& r2,int l,int r,int p,int q)
{
if(!r2) r2=++an;
sum[r2]=sum[r1]+q;
if(l==r) return;
int mid=l+r>>1;
if(p<=mid) ins(ch[r1][0],ch[r2][0],l,mid,p,q), ch[r2][1]=ch[r1][1];
else ins(ch[r1][1],ch[r2][1],mid+1,r,p,q), ch[r2][0]=ch[r1][0];
}
int query(int r1,int r2,int l,int r,int p)
{
if(l>p) return 0;
if(sum[r1]==sum[r2]) return 0;
if(r<=p) return sum[r2]-sum[r1];
int mid=l+r>>1,ans=0;
ans+=query(ch[r1][0],ch[r2][0],l,mid,min(p,mid));
if(p>mid) ans+=query(ch[r1][1],ch[r2][1],mid+1,r,p);
return ans;
}
#undef S2
}
namespace Seg2D
{
#define S2 23333333
int an=0,rot[S2],sum[S2],tag[S2],ch[S2][2],n;
int alc(int& x) {return (x)?(x):(x=++an);}
void I_add(int x,int l,int r,int ql,int qr)
{
sum[x]+=qr-ql+1;
if(l==ql&&r==qr) {++tag[x]; return;}
int mid=l+r>>1;
if(ql<=min(mid,qr)) I_add(alc(ch[x][0]),l,mid,ql,min(mid,qr));
if(max(mid+1,ql)<=qr) I_add(alc(ch[x][1]),mid+1,r,max(mid+1,ql),qr);
}
void O_add(int x,int l,int r,int ql,int qr,int p)
{
I_add(alc(rot[x]),1,n,ql,qr);
if(l==r) return;
int mid=l+r>>1;
if(p<=mid) O_add(x+x,l,mid,ql,qr,p);
else O_add(x+x+1,mid+1,r,ql,qr,p);
}
int I_sum(int x,int l,int r,int ql,int qr)
{
if(!x||ql>qr) return 0;
if(l==ql&&r==qr) return sum[x];
int mid=l+r>>1;
return tag[x]*(qr-ql+1)+I_sum(ch[x][0],l,mid,ql,min(qr,mid))+I_sum(ch[x][1],mid+1,r,max(ql,mid+1),qr);
}
int O_query(int x,int l,int r,int ql,int qr,int p)
{
if(l==r) return l;
int mid=l+r>>1,cnt=I_sum(rot[x+x+1],1,n,ql,qr);
if(cnt>=p) return O_query(x+x+1,mid+1,r,ql,qr,p);
else return O_query(x+x,l,mid,ql,qr,p-cnt);
}
}
namespace Tree
{
Edg int n;
#define S 20
int p[SZ][S],fa[SZ],dep[SZ];
int sz[SZ],son[SZ];
void dfs(int x,int f=0)
{
sz[x]=1;
for(int i=1;i<S;i++) p[x][i]=p[p[x][i-1]][i-1];
for es(x,e)
{
int b=vb[e];
if(b==f)continue;
fa[b]=p[b][0]=x;
dep[b]=dep[x]+1;
dfs(b,x);
sz[x]+=sz[b];
if(sz[b]>sz[son[x]]) son[x]=b;
}
}
int top[SZ],ds[SZ],cd[SZ],C=0;
void dfs2(int x,int t,int f=0)
{
top[x]=t; ds[++C]=x; cd[x]=C;
if(son[x]) dfs2(son[x],t,x);
for es(x,e)
{
int b=vb[e];
if(b==f||b==son[x]) continue;
dfs2(b,b,x);
}
}
int jump1(int x,int d)
{
for(int i=S-1;i>=0;i--)
{
if(p[x][i]&&dep[p[x][i]]>=d) x=p[x][i];
}
return x;
}
int lca1(int a,int b)
{
if(dep[a]<dep[b]);else swap(a,b);
b=jump1(b,dep[a]);
if(a==b) return a;
for(int i=S-1;i>=0;i--)
{
if(p[a][i]!=p[b][i])
a=p[a][i], b=p[b][i];
}
return p[a][0];
}
int jump2(int x,int d)
{
while(fa[top[x]]&&dep[fa[top[x]]]>=d) x=fa[top[x]];
int ans=ds[cd[x]-(dep[x]-d)];
return ans;
}
int lca2(int a,int b)
{
int f1=top[a],f2=top[b];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
swap(f1,f2), swap(a,b);
a=fa[f1]; f1=top[a];
}
int ans;
if(dep[a]>dep[b]) ans=b; else ans=a;
return ans;
}
#undef S
}
namespace D_qzh
{
ll d_qzh(ll n)
{
ll ed=1,ans=0;
for(ll a=1;a<=n;a=ed+1)
{
ed=(n/(n/a));
ans+=(a+ed)*(ed-a+1)/2*(n/a);
}
return ans;
}
}
namespace Eul_qzh
{
ll MOD=1000000007;
#define MM 6000000
int ps[MM+5],pn=0,mu[MM+5],eul[MM+5];
bool np[MM+5];
ll qzheul[MM+5];
void shai()
{
np[1]=mu[1]=eul[1]=1;
for(int i=2;i<=MM;i++)
{
if(!np[i]) {mu[i]=-1; ps[++pn]=i; eul[i]=i-1;}
for(int j=1;j<=pn&&i*ps[j]<=MM;j++)
{
np[i*ps[j]]=1;
if(i%ps[j])
{
mu[i*ps[j]]=-mu[i];
eul[i*ps[j]]=eul[i]*(ps[j]-1);
}
else
{
mu[i*ps[j]]=0;
eul[i*ps[j]]=eul[i]*ps[j];
break;
}
}
}
for(int i=1;i<=MM;i++) qzheul[i]=(qzheul[i-1]+eul[i])%MOD;
}
ll qp(ll a,ll b)
{
if(b==0) return 1;
ll hf=qp(a,b>>1);
hf=hf*hf%MOD;
if(b&1) hf=hf*(a%MOD)%MOD;
return hf;
}
ll rv2=qp(2,MOD-2);
map<ll,ll> mm;
ll eulsum(ll x)
{
if(x<=MM) return qzheul[x];
if(mm.count(x)) return mm[x];
ll ans,lst;
if(x%MOD!=0)
ans=(x%MOD)*((x%MOD)+1)%MOD*rv2%MOD;
else
ans=0;
for(ll p=2;p<=x;p=lst+1)
{
lst=x/(x/p);
ans-=((lst-p+1)%MOD)*eulsum(x/p)%MOD;
ans%=MOD;
}
ans=(ans%MOD+MOD)%MOD;
return mm[x]=ans;
}
}
namespace Muqzh
{
ll MOD=1000000007;
#define MM 6000000
int ps[MM+5],pn=0,mu[MM+5];
bool np[MM+5];
ll qzhmu[MM+5];
void shai()
{
np[1]=mu[1]=1;
for(int i=2;i<=MM;i++)
{
if(!np[i]) {mu[i]=-1; ps[++pn]=i;}
for(int j=1;j<=pn&&i*ps[j]<=MM;j++)
{
np[i*ps[j]]=1;
if(i%ps[j]) mu[i*ps[j]]=-mu[i];
else{mu[i*ps[j]]=0; break;}
}
}
for(int i=1;i<=MM;i++) qzhmu[i]=qzhmu[i-1]+mu[i];
}
map<ll,ll> mm;
ll musum(ll x)
{
if(x<=MM) return qzhmu[x];
if(mm.count(x)) return mm[x];
ll ans=1,lst;
for(ll p=2;p<=x;p=lst+1)
{
lst=x/(x/p);
ans-=(lst-p+1)*musum(x/p);
}
return mm[x]=ans;
}
}
int main()
{
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment