现在才开始写 POI 是不是太弱了？
-Rendezvous
怎么说呢，我发现我的代码好长啊～长啊～长啊～长长长长长长长长长长长长长长长长长长长长长长啊～
大概就是在一个内向树上搞一个类似 lca 的东西，想想内向树估计就可以搞出来了吧……
#include <cstdio>
const int sizeOfPoint=;
const int sizeOfEdge=; inline int lg(int);
inline int min(int, int);
inline int max(int, int);
inline void swap(int & , int & );
inline int getint();
inline void putint(int); struct edge {int point; edge * next;};
edge memory[sizeOfEdge], * port=memory;
inline edge * newedge(int, edge * ); struct node {int x, y; inline node(int=, int=);};
inline bool operator < (node, node); int n, m, k;
int p[sizeOfPoint];
edge * e[sizeOfPoint];
int a[][sizeOfPoint];
int g[sizeOfPoint], s[sizeOfPoint];
int f[sizeOfPoint], d[sizeOfPoint];
int l[sizeOfPoint];
bool v[sizeOfPoint], b[sizeOfPoint];
inline void bfs(int);
inline int lca(int, int); int main()
{
n=getint(), k=getint();
for (int i=;i<=n;i++)
{
p[i]=getint();
e[p[i]]=newedge(i, e[p[i]]);
} for (int i=;i<=n;i++) if (!v[i])
{
int u=i;
for ( ;!b[u];u=p[u]) b[u]=true; ++m;
for (int j=;!l[u];j++, u=p[u])
{
g[u]=m;
s[m]++;
l[u]=j;
bfs(u);
}
} for (int i=;i<=k;i++)
{
int a=getint(), b=getint(); if (g[f[a]]!=g[f[b]])
{
putint(-), putchar(' ');
putint(-), putchar('\n');
}
else if (f[a]==f[b])
{
int c=lca(a, b);
putint(d[a]-d[c]), putchar(' ');
putint(d[b]-d[c]), putchar('\n');
}
else
{
int o=s[g[f[a]]];
node ans1=node(d[a], d[b]), ans2=node(d[a], d[b]); if (l[f[a]]<l[f[b]])
{
ans1.x+=l[f[b]]-l[f[a]];
ans2.y+=o-(l[f[b]]-l[f[a]]);
}
else
{
ans1.x+=o-(l[f[a]]-l[f[b]]);
ans2.y+=l[f[a]]-l[f[b]];
} if (ans1<ans2)
{
putint(ans1.x), putchar(' ');
putint(ans1.y), putchar('\n');
}
else
{
putint(ans2.x), putchar(' ');
putint(ans2.y), putchar('\n');
}
}
} return ;
} inline int lg(int x)
{
return -__builtin_clz(x);
}
inline int min(int x, int y)
{
return x<y?x:y;
}
inline int max(int x, int y)
{
return x>y?x:y;
}
inline void swap(int & x, int & y)
{
int t=x; x=y; y=t;
}
inline int getint()
{
register int num=;
register char ch;
do ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline void putint(int num)
{
char stack[];
register int top=;
if (num==) stack[top=]='';
if (num<) putchar('-'), num=-num;
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
} inline edge * newedge(int point, edge * next)
{
edge * ret=port++;
ret->point=point; ret->next=next;
return ret;
} inline node::node(int _x, int _y)
{
x=_x;
y=_y;
}
inline bool operator < (node a, node b)
{
if (max(a.x, a.y)<max(b.x, b.y)) return true;
if (max(a.x, a.y)>max(b.x, b.y)) return false;
if (min(a.x, a.y)<min(b.x, b.y)) return true;
if (min(a.x, a.y)>min(b.x, b.y)) return false;
return a.y<b.y;
} inline void bfs(int root)
{
static int q[sizeOfPoint];
int s=, t=;
d[root]=;
f[root]=root; for (q[t++]=root;s<t;s++)
{
int u=q[s];
v[u]=true;
if (d[u]>)
{
int lim=lg(d[u]);
for (int i=;i<=lim;i++)
a[i][u]=a[i-][a[i-][u]];
} for (edge * i=e[u];i;i=i->next) if (i->point!=p[u] && !l[i->point])
{
d[i->point]=d[u]+;
f[i->point]=root;
a[][i->point]=u;
q[t++]=i->point;
}
}
}
inline int lca(int u, int v)
{
int dist;
if (d[u]<d[v]) swap(u, v);
while ((dist=d[u]-d[v])) u=a[__builtin_ctz(dist)][u];
if (u==v) return u;
for (int i=;i>=;i--)
if (a[i][u]!=a[i][v])
u=a[i][u],
v=a[i][v];
return a[][u];
}
LEN:190+
-Distance
一道我认为做法极其诡异的题目，很容易想到若令 g[i] 表示 i 有几个质因子，则 d[x, y]=g[x]+g[y]-2*g[gcd(x, y)]
然后我就想不下去了……一看题解，居然是枚举 x 的因数！然后暴力搞搞就出来了，细节部分要仔细推敲。
还有 n 的质因子数应该是 O(log2n) 所以 n 的因子数最差情况似乎是 O(n) 级别的？也只能说是数据弱了～
#include <cstdio>
#include <cstring>
const int sizeOfNumber=;
const int sizeOfSieve=;
const int inf=0x7F7F7F7F; inline int getint();
inline void putint(int); bool b[sizeOfSieve];
int m, p[sizeOfNumber];
int e[sizeOfSieve], c[sizeOfSieve];
inline void sieve(); struct node {int v, t; inline node(int=, int=);}; int n, l;
int ansv, anst;
int a[sizeOfNumber];
node s[sizeOfNumber];
int v1[sizeOfSieve], v2[sizeOfSieve];
int t1[sizeOfSieve], t2[sizeOfSieve];
void search(int, int);
void query(int, int); int main()
{
sieve(); n=getint();
for (int i=;i<=n;i++)
a[i]=getint(); memset(v1, 0x7F, sizeof(v1));
memset(v2, 0x7F, sizeof(v2));
for (int i=;i<=n;i++)
{
int t=a[i]; s[]=node(, );
for (l=;t>;t/=e[t])
{
if (e[t]!=s[l].v)
s[++l]=node(e[t], );
else
s[l].t++;
}
s[]=node(a[i], i);
search(, );
}
for (int i=;i<=n;i++)
{
int t=a[i]; s[]=node(, );
for (l=;t>;t/=e[t])
{
if (e[t]!=s[l].v || !l)
s[++l]=node(e[t], );
else
s[l].t++;
}
s[]=node(a[i], i); ansv=anst=inf;
query(, );
putint(anst);
} return ;
} inline int getint()
{
register int num=;
register char ch;
do ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline void putint(int num)
{
char stack[];
register int top=;
if (num==) stack[top=]='';
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
putchar('\n');
} inline void sieve()
{
for (int i=;i<sizeOfSieve;i++)
{
if (!b[i])
{
p[m++]=i;
e[i]=i; c[i]=;
} for (int j=;j<m;j++)
{
if (i*p[j]>=sizeOfSieve) break;
b[i*p[j]]=true;
e[i*p[j]]=p[j]; c[i*p[j]]=c[i]+;
if (e[i]==p[j]) break;
}
}
} inline node::node(int _v, int _t)
{
v=_v, t=_t;
} void search(int v, int t)
{
if (t>l)
{
int g=c[s[].v]-(c[v]<<);
if (g<v1[v])
{
v2[v]=v1[v], t2[v]=t1[v];
v1[v]=g, t1[v]=s[].t;
}
else if (g<v2[v])
v2[v]=g, t2[v]=s[].t;
}
else
{
for (int i=, j=;i<=s[t].t;i++, j=j*s[t].v)
search(v*j, t+);
}
}
void query(int v, int t)
{
if (t>l)
{
if (s[].t!=t1[v])
{
if (v1[v]<ansv || (v1[v]==ansv && t1[v]<anst))
ansv=v1[v], anst=t1[v];
}
else if (v2[v]<ansv || (v2[v]==ansv && t2[v]<anst))
ansv=v2[v], anst=t2[v];
}
else
{
for (int i=, j=;i<=s[t].t;i++, j=j*s[t].v)
query(v*j, t+);
}
}
调了半天 T_T
-Letters
这道题目应该还是比较简单的吧，一眼就看出是求逆序对数，利用第一个字符串给第二个字符串标号（是字母对应字母的标号，开 26 个队列即可）
本质其实和直接算逆序对数是一样的，只不过这道题可以看作是对 “顺序” 重新下了一个定义罢了～
#include <cstdio>
#include <cstring>
#include <queue>
typedef long long LL;
const int sizeOfString=; inline int getint();
inline int getstr(char * );
inline void putint(LL); int C[sizeOfString];
inline int lowbit(int);
inline void update(int);
inline int query(int); int N;
char J[sizeOfString], M[sizeOfString];
std::queue<int> q[];
int A[sizeOfString]; int main()
{
LL ans=; N=getint();
getstr(J);
getstr(M); for (int i=;i<N;i++)
q[J[i]-'A'].push(i);
for (int i=;i<N;i++)
{
A[i]=+q[M[i]-'A'].front();
q[M[i]-'A'].pop();
} for (int i=;i<N;i++)
{
ans+=query(A[i]);
update(A[i]);
} putint(ans); return ;
} inline int getint()
{
register int num=;
register char ch;
do ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline int getstr(char * str)
{
register int len=;
register char ch;
do ch=getchar(); while (ch<'A' || ch>'Z');
do str[len++]=ch, ch=getchar(); while (ch>='A' && ch<='Z');
return len;
}
inline void putint(LL num)
{
char stack[];
register int top=;
if (num==) stack[top=]='';
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
putchar('\n');
} inline int lowbit(int i)
{
return i & -i;
}
inline void update(int i)
{
for ( ;i;i-=lowbit(i))
C[i]++;
}
inline int query(int i)
{
int ret=;
for ( ;i<=N;i+=lowbit(i))
ret+=C[i];
return ret;
}
一 A 啊！久违的一 A 啊！