A:小睿睿的数列
我们注意到一个区间内的数字全部相同这种贡献是可以单独算的
那么我们可以把它们都缩在一起
然后我们发现我们每个点的gcd要使找得到，一定是下一次是这一次的约数，然后我们不断向两边扩展，由于是约数而且我们规定了它们不同，所以每次至少是上次的两倍，这样最多是log次的
我们找一个起点作为gcd然后向两边枚举即可，不断更新取max然后计数就可以了
因此总复杂度是一个log的，代码里只有些去重的技巧，还是比较好写的
代码：
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=2e6+5;
int n,a[N],len,lst=1,ma,ans;pii b[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)if(i!=1&&a[i]!=a[i-1])b[++len]=pii(lst,i-1),lst=i;
b[++len]=pii(lst,n);
for(int i=1;i<=len;i++){
int res=b[i].second-b[i].first+1;
for(int j=i-1;j;j--){
if(a[b[j].first]%a[b[i].first]!=0)break;
res+=b[j].second-b[j].first+1;
}
for(int j=i+1;j<=len;j++){
if(a[b[j].first]%a[b[i].first]!=0)break;
res+=b[j].second-b[j].first+1;
}
if(res>ma)ma=res,ans=1;else if(res==ma)ans++;
}
printf("%d\n",ans);
return 0;
}B:小睿睿的伤害
不太会题解的做法，考试的时候没多想直接码就可以了
我们考虑质因数不会太多，因此我们用一个vector记录一下
然后每个vector枚举每个约数我们用一个虚树维护一下这个部分点的树结构，然后虚树上dfs一遍更新答案就可以了，好像有点卡常加上卡常选项就好了，O(能过)
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+5;
struct Edge{int to,nxt;}e[N<<1];
int n,fst[N],tote,dep[N],id[N],fa[N][21],dfn,st[N],tp,siz[N],a[N],now,ans[N];
bool usd[N],vis[N];LL cnt[N];
vector<int>edg[N],vec[N],cle;set<int>s;
void adde(int u,int v){e[++tote]=(Edge){v,fst[u]};fst[u]=tote;}
void dfs(int u,int f) {
id[u]=++dfn;dep[u]=dep[f]+1;fa[u][0]=f;
for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=fst[u],v;i;i=e[i].nxt)if((v=e[i].to)!=f)dfs(v,u);
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i>=0;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
if(u==v)return u;
for(int i=20;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
bool cmp(int x,int y){return id[x]<id[y];}
void insert(int u){
s.insert(u);
if(tp==1){if(u!=st[tp])st[++tp]=u;return;}
int pos=lca(st[tp],u);
while(tp>1&&id[pos]<=id[st[tp-1]]){
if(!vis[st[tp-1]])vis[st[tp-1]]=true,cle.pb(st[tp-1]);
edg[st[tp-1]].pb(st[tp]);tp--;
}
if(st[tp]!=pos){
if(!vis[pos])vis[pos]=true,cle.pb(pos);
edg[pos].pb(st[tp]);st[tp]=pos;
}
st[++tp]=u;
}
void dfs2(int u){
if(usd[u])siz[u]=1;else siz[u]=0;
LL res=0;
for(auto v:edg[u]){
dfs2(v);
//if(now==12)printf("siz:%d %d %d %d\n",u,v,siz[u],siz[v]);
res+=(LL)siz[u]*siz[v];siz[u]+=siz[v];
}
//if(now==12)printf("res:%lld\n",res);
if(res)ans[u]=now,cnt[u]=res;
}
void build(int len){
//memset(siz,0,sizeof(siz));
//printf("now:%d %d\n",now,len);
//for(int i=1;i<=len;i++)printf("%d%c",a[i]," \n"[i==len]);
for(int i=1;i<=len;i++)usd[a[i]]=true;
sort(a+1,a+len+1,cmp);
cle.clear();cle.pb(1);vis[1]=true;
for(int i=1;i<=len;i++)insert(a[i]);
while(tp>1){
if(!vis[st[tp-1]])vis[st[tp-1]]=true,cle.pb(st[tp-1]);
edg[st[tp-1]].pb(st[tp]);tp--;
}
//puts("edge:");
//for(int i=1;i<=n;i++)for(auto v:edg[i])printf("%d %d\n",i,v);
dfs2(1);
for(auto x:cle)edg[x].clear(),vis[x]=false;
for(int i=1;i<=len;i++)usd[a[i]]=false;
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
for(int j=1;j*j<=x;j++)if(x%j==0){
vec[j].pb(i);
if(j*j!=x)vec[x/j].pb(i);
}
}
dfs(1,0);
for(int i=1,len;i<N;i++){
if(vec[i].empty())continue;len=0;now=i;
for(auto x:vec[i])a[++len]=x;build(len);
}
for(int i=1;i<=n;i++)printf("%d %lld\n",ans[i],cnt[i]);
return 0;
}C:小睿睿的兄弟
我们发现求k级的关系这些深度都是一样的，然后又是出现在一个子树里面的问题，我们通常会想到dfs序
但是我们发现要求特定深度的dfs序就不是那么好搞
我们对于每个深度按dfs维护一个顺序，然后在一个vector里面存一下，我们按照深度优先，dfs第二优先级的顺序存一下，接着我们就可以直接求一个深度里面连续的第k小了，我们可以在vector上二分然后用跟平常套路一样的主席树维护！
这题有点卡空间，我们尽量要优化空间常数！
代码：
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=1e6+5;
struct Edge{int to,nxt;}e[N<<1];
int n,m,val[N],fst[N],tote,fa[N][21],dep[N],L[N],R[N],id[N],dfn;
vector<int>v[N];
void adde(int u,int v){e[++tote]=(Edge){v,fst[u]};fst[u]=tote;}
int up(int u,int k){for(int i=20;i>=0;i--)if(k&(1<<i))u=fa[u][i];return u;}
void dfs(int u,int f){
fa[u][0]=f;dep[u]=dep[f]+1;L[u]=++dfn;v[dep[u]].pb(u);
for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=fst[u],v;i;i=e[i].nxt)if((v=e[i].to)!=f)dfs(v,u);
R[u]=dfn;
}
bool cmp(int x,int y){return L[x]<L[y];}
namespace seg{
int Root[N],siz[N*30],ls[N*30],rs[N*30],tot;
void build(int rt,int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
build(ls[rt]=++tot,l,mid);build(rs[rt]=++tot,mid+1,r);
}
void insert(int rt,int pre,int l,int r,int x){
siz[rt]=siz[pre]+1;if(l==r)return;
ls[rt]=ls[pre];rs[rt]=rs[pre];int mid=(l+r)>>1;
if(x<=mid)insert(ls[rt]=++tot,ls[pre],l,mid,x);else insert(rs[rt]=++tot,rs[pre],mid+1,r,x);
}
int ask(int rt,int pre,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1,t=siz[ls[rt]]-siz[ls[pre]];
return k<=t?ask(ls[rt],ls[pre],l,mid,k):ask(rs[rt],rs[pre],mid+1,r,k-t);
}
}
int binary(int d,int len,int x){
int now=-1;
for(int k=20,tmp;~k;k--){
tmp=now+(1<<k);
if(tmp<len&&L[v[d][tmp]]<=x)now=tmp;
}
return now;
}
int ask(int u,int k){
int f=up(u,k);if(!f)return -1;
int d=dep[f]+k,len=v[d].size();
if(!len)return -1;
int lu=binary(d,len,L[f]-1),ru=binary(d,len,R[f]),lrt,rrt;
if(ru-lu<k)return -1;
if(lu==-1)lrt=seg::Root[id[v[d][0]]-1];else lrt=seg::Root[id[v[d][lu]]];
rrt=seg::Root[id[v[d][ru]]];
return seg::ask(rrt,lrt,1,n,k);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
dfs(1,0);
for(int i=1;i<=n;i++)sort(v[i].begin(),v[i].end(),cmp);
seg::build(seg::Root[0]=++seg::tot,1,n);
for(int i=1,now=0;i<=n;i++)for(auto x:v[i])id[x]=++now,seg::insert(seg::Root[now]=++seg::tot,seg::Root[now-1],1,n,val[x]);
//for(int i=1;i<=n;i++)printf("%d%c",id[i]," \n"[i==n]);
//for(auto x:v[4])printf("%d ",x);puts("OK");
int lstans=0;
while(m--){
int x,k,res;scanf("%d%d",&x,&k);
x=(x^lstans)%n+1;res=ask(x,k);
if(res==-1)puts("?");else printf("%d\n",lstans=res);
}
return 0;
}D,E,F待补（等补题以后就会补）
京公网安备 11010502036488号