专项测试 数据结构1
数据结构场，指用数据结构做题,不做数据结构题
A. Surprise me
题目让求的式子为
\[\frac{1}{n\times(n-1)}\sum\limits_{u,v,u\neq v}\varphi(a_u\times a_v)\times dist(u,v) \]只看后面
当 \(u=v\) 时 \(dist\) 为 \(0\) 所以变成
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\varphi(a_i\times a_j)\times dist(i,j) \]欧拉函数的新套路 \(\varphi(x\times y)=\frac{\varphi(x)\times\varphi(y)\times gcd(x,y)}{\varphi(gcd(x,y))}\)
简单证明
\(\varphi(x)=x\times \prod\limits_{d|x}\frac{d-1}{d}\)
把 \(\varphi(x)\) 和 \(\varphi(y)\) 展开和 \(\varphi(x\times y)\) 比较，把少乘的补上就是上面的东西了
那么式子变成
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\frac{\varphi(a_i)\times\varphi(a_j)\times gcd(a_i,a_j)}{\varphi(gcd(a_i,a_j))}\times dist(i,j) \]发现有 \(gcd\) 那么可以直接提出来枚举 \(gcd\)
\[\sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\varphi(a_i)\varphi(a_j)dist(i,j)[gcd(a_i,a_j)==d] \]利用莫比乌斯变换
那我们设 \(f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\varphi(a_i)\varphi(a_j)dist(i,j)[gcd(a_i,a_j)==d]\)
那么 \(F(x)=\sum\limits_{x|d}f(d),f(x)=\sum\limits_{x|d}\mu(\frac{d}{x})F(d)\)
然后 \(F(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\varphi(a_i)\varphi(a_j)dist(i,j)[x|gcd(a_i,a_j)]\)
再把 \(dist\) 拆了
\(F(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^{n}\varphi(a_i)\varphi(a_j)(dep_i+dep_j-2\times dep_{lca(i,j)})\)
把只和 \(i,j\) 有关的提一提
\(F(x)=\sum\limits_{i=1}^n\varphi(a_i)dep_i\sum\limits_{j=1}^n\varphi(a_j)[x|gcd(a_i,a_j)]+\sum\limits_{i=1}^n\varphi(a_i)\sum\limits_{j=1}^n\varphi(a_j)dep_j[x|gcd(a_i,a_j)]-2\times \sum\limits_{i=1}^n\sum\limits_{j=1}^n\varphi(a_i)\varphi(a_j)dep_{lca(i,j)}[x|gcd(a_i,a_j)]\)
前两项一样直接合并
\(F(x)=2\times\sum\limits_{i=1}^n\varphi(a_i)dep_i\sum\limits_{j=1}^n\varphi(a_j)[x|gcd(a_i,a_j)]-2\times \sum\limits_{i=1}^n\sum\limits_{j=1}^n\varphi(a_i)\varphi(a_j)dep_{lca(i,j)}[x|gcd(a_i,a_j)]\)
前一项可以直接 \(O(n)\) 处理再乘起来，考虑后一项
相当于 \(i,j\) 在 \(lca\) 的位置合并,可以简单 \(dp\) 一下，统计子树内的权值和，再在 \(lca\) 处乘上深度
直接这样做复杂度直接爆炸，发现两个点只有在 \(x|gcd(a_i,a_j)\) 时有贡献
于是可以直接将所有 \(x\) 的倍数的点提取出来，建出虚树，由调和级数得出总共会提出 \(n\log n\) 个点这样复杂度就对了
总复杂度 \(O(n\log^2n)\)
Code
#include
#define int long long
#define rint signed
#define mod 1000000007
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,res,ans;
int F[400010],f[400010],v[400010];
int a[400010],pos[400010];
int node[400010],stk[400010],p,K;
int top[400010],siz[400010],fa[400010],dep[400010],son[400010],dfn[400010],clo;
int head[400010],ver[400010],to[400010],tot;
int prime[400010],phi[400010],mu[400010],cnt;
bool is[400010],vis[400010];
inline bool cmp(int x,int y){return dfn[x]>=1;}
return res;
}
void dfs1(int x,int fath,int depth){
fa[x]=fath,dep[x]=depth,siz[x]=1;
int maxson=-1;
for(int i=head[x];i;i=to[i]){
int y=ver[i];
if(y==fath) continue;
dfs1(y,x,depth+1);
siz[x]+=siz[y];
if(siz[y]>maxson) maxson=siz[y],son[x]=y;
}
}
void dfs2(int x,int topf){
top[x]=topf,dfn[x]=++clo;
if(!son[x]) return ;
dfs2(son[x],topf);
for(int i=head[x];i;i=to[i]){
int y=ver[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
inline int LCA(int x,int y){
while(top[x]!=top[y]) (dep[top[x]]>dep[top[y]])?(x=fa[top[x]]):(y=fa[top[y]]);
return (dep[x]1;i--) node[++K]=LCA(node[i],node[i-1]);
node[++K]=1;sort(node+1,node+1+K,cmp);K=unique(node+1,node+1+K)-node-1;
for(int i=1;i<=K;i++){
while(p&&(dfn[stk[p]]+siz[stk[p]]-1 B. 神牛养成计划
我有个常数较大的后缀数组做法，每次随机过点，所有点都分着过了
简单说说
对正反串分别跑一遍 \(SA\)
然后每次对询问串二分出来他出现的所有位置，正反两个串都做一遍
相当于求集合的交了，主席树可以轻松解决
对每一个串建立一个映射，映射正串的排名在反串的排名
还有两颗 \(Trie\) 树的超高速做法
对正反串分别建出 \(Trie\) 树
\(Trie\) 上的点，每一个点的父亲都是这个点表示的字符串的一个前缀
于是让询问串在 \(Trie\) 树上面跑，失配了就输出 \(0\)
然后还是求两个集合的交
对每一个串建立一个映射，映射正串的位置在反串的位置，和上面的一样
还有个小技巧，用前向星存 \(Trie\) 树可以减小空间复杂度
每条边存个边权代表转移的字符
这样就不用乘 \(26\) 的空间复杂度了
实测对时间复杂度还有一定影响，用了前向星，速度快到飞起
Code
#include
//#define int long long
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,len,now,m,lst;
int rt[2000010];
char st[2000010];
namespace PerSeg{
#define lson t[x].ls
#define rson t[x].rs
int tot;
struct Seg{int ls,rs,sum;}t[2010*30];
void ins(int &x,int l,int r,int pos){
int pre=x;x=++tot;t[x]=t[pre];t[x].sum++;
if(l==r) return ;
int mid=(l+r)>>1;
if(pos<=mid) ins(lson,l,mid,pos);
else ins(rson,mid+1,r,pos);
}
int query(int u,int v,int l,int r,int L,int R){
if(L<=l&&r<=R) return t[v].sum-t[u].sum;
int mid=(l+r)>>1,res=0;
if(L<=mid) res+=query(t[u].ls,t[v].ls,l,mid,L,R);
if(R>mid) res+=query(t[u].rs,t[v].rs,mid+1,r,L,R);
return res;
}
}
struct Trie{
int tot;
int bl[2000010],pos[2010];
int dfn[2000010],id[2000010],siz[2000010],clo,tr[2000010][26];
int head[2000010],ver[2000010],to[2000010],edge[2000010],cnt;
inline void add(int x,int y,int z){
ver[++cnt]=y;
edge[cnt]=z;
to[cnt]=head[x];
head[x]=cnt;
}
inline int star(int x,int z){
for(int i=head[x];i;i=to[i]){
int y=ver[i];
if(edge[i]==z) return y;
}
return 0;
}
inline void ins(){
int p=0;
for(int i=1,v,V;i<=len;i++){
v=st[i]-'a';
V=star(p,v);
if(!V){add(p,++tot,v);p=tot;}
else p=V;
}
pos[bl[p]=now]=p;
}
void dfs(int x){
dfn[x]=++clo,siz[x]=1;id[clo]=x;
for(int i=head[x];i;i=to[i]){int y=ver[i];dfs(y);siz[x]+=siz[y];}
}
inline int query(){
int p=0;
for(int i=1,v,V;i<=len;i++){
v=st[i]-'a';
V=star(p,v);
if(!V) return 0;
p=V;
}
return p;
}
inline void print(){
for(int i=1;i<=tot;i++) printf("bl[%d] : %d\n",i,bl[i]);
for(int i=1;i<=tot;i++) printf("dfn[%d] : %d\n",i,dfn[i]);
for(int i=1;i<=tot;i++) printf("siz[%d] : %d\n",i,siz[i]);
for(int i=1;i<=tot;i++) printf("id[%d] : %d\n",i,id[i]);
}
}s,is;
inline void encode(){for(int i=1;i<=len;i++) st[i]=(st[i]-'a'+lst)%26+'a';}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
n=read();
for(int i=1;i<=n;i++){
scanf("%s",st+1);len=strlen(st+1);now=i;
s.ins();reverse(st+1,st+1+len);is.ins();
}
s.dfs(0);is.dfs(0);
for(int i=1;i<=s.tot+1;i++){
rt[i]=rt[i-1];
if(s.bl[s.id[i]]) PerSeg::ins(rt[i],1,is.tot+1,is.dfn[is.pos[s.bl[s.id[i]]]]);
}
m=read();
for(int i=1,p,l,r,ll,rr,pp;i<=m;i++){
scanf("%s",st+1);len=strlen(st+1);encode();pp=p=s.query();
l=s.dfn[p],r=s.dfn[p]+s.siz[p]-1;
scanf("%s",st+1);len=strlen(st+1);reverse(st+1,st+1+len);encode();p=is.query();
ll=is.dfn[p],rr=is.dfn[p]+is.siz[p]-1;
if(!pp||!p) printf("%d\n",lst=0);
else printf("%d\n",lst=PerSeg::query(rt[l-1],rt[r],1,is.tot+1,ll,rr));
}
return 0;
}
C. 串
P.S. 发现一道相同套路的题,那个题能扩展到跟 \(k\) 无关
看到 \(k\) 和 \(n\) 差不多同级，于是可以暴力维护出前 \(k\) 个的取值
对每一点维护出以他为左端点的所有右端点的答案,再维护出最大值和出现最大值的位置
再用优先队列维护每一个左端点的最大答案
每次弹掉最大的再更新成次大的，重复 \(k\) 次
再用主席树来维护
对每个点找到这个权值下一次出现的位置
在每次移动的时候都将上个位置到这个位置的前一个的权值都减一下，再在上一个的位置赋 \(-inf\)
每次弹掉最大值的时候就直接在那个位置赋 \(-inf\)
Code
#include
#define int long long
#define lson t[x].ls
#define rson t[x].rs
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,K,tot;
int rt[300010];
int a[300010],nxt[300010];
int sum[300010];
mapvis;
struct Seg{
int ls,rs,atag,mx,pos;
inline void print(){printf("mx : %lld pos : %lld atag : %lld\n",mx,pos,atag);}
}t[300010*100];
struct Data{
int mx,rt;
inline bool operator<(const Data &b)const{return mx q;
inline void pushup(int x){
t[x].mx=max(t[lson].mx,t[rson].mx);
if(t[x].mx==t[lson].mx) t[x].pos=t[lson].pos;
else t[x].pos=t[rson].pos;
t[x].mx+=t[x].atag;
}
void build(int &x,int l,int r){
x=++tot;
if(l==r) return t[x].mx=sum[l],t[x].pos=l,void();
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(x);
}
void upd(int &x,int l,int r,int L,int R,int k){
int pre=x;x=++tot;t[x]=t[pre];
if(L<=l&&r<=R) return t[x].mx+=k,t[x].atag+=k,void();
int mid=(l+r)>>1;
if(L<=mid) upd(lson,l,mid,L,R,k);
if(R>mid) upd(rson,mid+1,r,L,R,k);
pushup(x);
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
n=read(),K=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++){
sum[i]=sum[i-1];
if(vis.find(a[i])==vis.end()) sum[i]+=a[i],vis[a[i]]=i;
else nxt[vis[a[i]]]=i,vis[a[i]]=i;
}
for(auto L:vis) nxt[L.second]=n+1;
build(rt[1],1,n);q.push((Data){t[rt[1]].mx,1});
for(int i=2;i<=n;i++){
rt[i]=rt[i-1];
upd(rt[i],1,n,i-1,i-1,-inf);
if(nxt[i-1]-1>=i) upd(rt[i],1,n,i,nxt[i-1]-1,-a[i-1]);
q.push((Data){t[rt[i]].mx,i});
}
while(--K){
Data tmp=q.top();q.pop();
int x=tmp.rt,pos;pos=t[rt[x]].pos;
upd(rt[x],1,n,pos,pos,-inf);
q.push((Data){t[rt[x]].mx,x});
}
printf("%lld\n",q.top().mx);
return 0;
}