SlingShot 求数轴上从x到y的最短路（ 边长为1），有若干个从xi到yi长度为ti的传送门，每次只能选择其中一个使用。

即求min(|x-y|,min{|a-x|+|b-y|+c})，拆开绝对值，根据相对位置分开讨论，转换成二维数点问题。

MLE的主席树版本：

#include
#define P pair
#define fir first
#define sec second
using namespace std;
typedef long long ll;
int read()
{
int x=;char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (''<=ch&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar(); return x; } const int N=1e9,T=6e6,M=1e5+; const ll inf=1ll<<; P Min[T]; int ls[T],rs[T],A[M],x,y,sc,n,rt0[M],rt1[M],m; struct node{ll a,b,c;}p[M]; bool cmp(const node &A,const node &B) {return A.a>;
if (x<=mid) ins(ls[k],ls[pk],l,mid,x,y); else ins(rs[k],rs[pk],mid+,r,x,y); Min[k]=fmin(Min[ls[k]],Min[rs[k]]); } P qry(int k,int l,int r,int L,int R) { if (!k) return P(inf,inf); if (L<=l&&r<=R) return Min[k]; int mid=(l+r)>>;P mn=P(inf,inf);
if (L<=mid) mn=fmin(mn,qry(ls[k],l,mid,L,R)); if (R>mid) mn=fmin(mn,qry(rs[k],mid+,r,L,R));
return mn;
}
int main()
{
n=read();m=read();Min[]=P(inf,inf);
for (int i=;i<=n;i++) p[i].a=read(),p[i].b=read(),p[i].c=read(),A[i]=p[i].a; sort(p+,p+n+,cmp); sort(A+,A+n+);//寻址数组 for (int i=n;i>=;i--)
ins(rt0[i],rt0[i+],,N,p[i].b,P(p[i].a-p[i].b+p[i].c,p[i].a+p[i].b+p[i].c));
for (int i=;i<=n;i++)
ins(rt1[i],rt1[i-],,N,p[i].b,P(-p[i].a-p[i].b+p[i].c,-p[i].a+p[i].b+p[i].c));
while (m--)
{
x=read();y=read();
ll ans=abs(x-y);
int k=upper_bound(A+,A+n+,x)-A-;
ans=min(ans,qry(rt0[k+],,N,,y).fir-x+y);
ans=min(ans,qry(rt1[k],,N,,y).fir+x+y);
ans=min(ans,qry(rt0[k+],,N,y,N).sec-x-y);
ans=min(ans,qry(rt1[k],,N,y,N).sec+x-y);
printf("%lld\n",ans);
}
return ;
}

正常二维数点的树状数组版本（AC）：

#include
using namespace std;
typedef long long ll;
int read()
{
int x=;char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (''<=ch&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar(); return x; } const int M=1e5+; const ll inf=1ll<<; int A[M],n,m,tot,t,B[M*]; ll ans[M],bit[M*]; vector vec1[M],vec2[M];
struct node{ll a,b,c,d;}p[M],q[M];
bool cmp(const node &A,const node &B) {return A.a=;i--)
{
add1(p[i].d,p[i].a-p[i].b+p[i].c);
for (int j=;j=;i--)
{
add2(p[i].d,p[i].a+p[i].b+p[i].c);
for (int j=;j<vec1[i].size();j++)
t=vec1[i][j],ans[t]=min(ans[t],qry2(q[t].d)-q[t].a-q[t].b);
}
init();
for (int i=;i<=n;i++)
{
add1(p[i].d,-p[i].a-p[i].b+p[i].c);
for (int j=;j<vec2[i].size();j++)
t=vec2[i][j],ans[t]=min(ans[t],qry1(q[t].d)+q[t].a+q[t].b);
}
init();
for (int i=;i<=n;i++)
{
add2(p[i].d,-p[i].a+p[i].b+p[i].c);
for (int j=;j<vec2[i].size();j++)
t=vec2[i][j],ans[t]=min(ans[t],qry2(q[t].d)+q[t].a-q[t].b);
}
for (int i=;i<=m;i++) printf("%lld\n",ans[i]);
return ;
}

Newbarn 加点x，询问x在树上能走的最远距离

最远距离一定会走到直径端点。维护每棵树的直径（维护一条就够了）。

#include
using namespace std;
const int N=;
int q,x,dep[N],fa[N][],id,bel[N],sc,Max,u[N],v[N],tmp;
char s[];
int lca(int x,int y)
{
if (dep[x]=;i--)
if (del&(<=;i--)
if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][];
}
int dis(int x,int y) {return dep[x]+dep[y]-*dep[lca(x,y)];}
int main()
{
scanf("%d",&q);
while (q--)
{
scanf("%s%d",s,&x);
if (s[]=='B')
{
id++;
if (x!=-)
{
dep[id]=dep[x]+,fa[id][]=x; bel[id]=bel[x];
for (int j=;j<=;j++) fa[id][j]=fa[fa[id][j-]][j-]; Max=dis(u[bel[id]],v[bel[id]]); if (tmp=dis(id,u[bel[id]]),tmp>Max) Max=tmp,v[bel[id]]=id;
if (tmp=dis(id,v[bel[id]]),tmp>Max) Max=tmp,u[bel[id]]=id;
}else bel[id]=++sc,u[sc]=v[sc]=id;
}else printf("%d\n",max(dis(x,u[bel[x]]),dis(x,v[bel[x]])));
}
return ;
}

Cow Gymnasts 求有多少个数组A任意位i都满足A[i]=sigma[A[i-j+1]>=j](i-j+1<=0时从N开始往下)？(1<=A[i]<=N)

关键点在发现循环节。大胆从最小位置x入手，设其值为m，则满足y=x(mod gcd(N,m)的位置y的值都为m。

同样也可以归纳证明，所有位置的值都<=m+1。（注意一个循环节中有一个m+1，那么就不会出现m）

枚举m，$Ans=\sum_{m=1}^{n-1}(2^{\gcd(n,m)}-1)+1$。m=n的情况只有可能全是m，故加1。

把gcd提出来，$Ans=\sum_{d|n}2^d*\varphi(N/d)-N+2-2^N$。

#include
using namespace std;
typedef long long ll;
const int mod=1e9+;
#define P pair
ll n,ans,sum;
map Phi;
vector

vec;
ll ksm(ll x,ll y) {
ll res=;
while (y) {if (y&) res=res*x%mod; x=x*x%mod;y>>=;}
return res;
}
void dvd(ll x)
{
for (int i=;i<=sqrt(x);i++)
if (x%i==)
{
sum*=i-;int cnt=;x/=i;
while (x%i==) x/=i,cnt++,sum*=i;
vec.push_back(P(i,cnt));
}
if (x!=) vec.push_back(P(x,));
}
void dfs(ll x,int d,ll phi)
{
if (d==vec.size()) {Phi[x]=phi;return;}
dfs(x,d+,phi);
ll t=vec[d].first,sum=t-;
for (int i=;i<=vec[d].second;i++)
{
x*=t;
dfs(x,d+,phi*sum);
sum*=t;
}
}
int main()
{
scanf("%lld",&n);
if (n==) return puts(""),;
sum=;dvd(n);
dfs(,,);ans=((-n-ksm(,n))%mod+mod)%mod;
for (int i=;i<=sqrt(n);i++)
if (n%i==){
ans+=ksm(,i)*Phi[n/i]%mod; ans%=mod;
if ((ll)i*i!=n) ans+=ksm(,n/i)*Phi[i]%mod,ans%=mod;
}
printf("%lld\n",ans);
return ;
}