zcmimi's blog

arrow_back主席树共14篇文章

avatar
zc
2020-09-22 22:01:00
查看原题

点击跳转

链上的情况

情况一

记录每个点i前一个与它一样的位置pre_i,

那么区间[l,r]内不同的个数也就是[l,r]pre_i<l的个数

主席树统计即可

情况二

考虑每个点对答案的贡献,分类讨论

  1. i\in [1,A]

    那么满足的y\in (pre_i,i],x\in [i,A]

    x\in (pre_i,i],y\in [i,B]

    总贡献为\sum (i-pre_i)\times(A+B-2i+2)-1

    (-1为了避免[i,i]被重复计算)

    拆下式子: (A+B+2)(\sum i-pre_i)-2(\sum i(i-pre_i))-\sum 1

    可以发现这种情况可以直接前缀和维护

  2. i\in (A,B],满足pre_i<A

    那么满足的x\in (pre_i,A],y\in [i,B]

    总贡献为\sum (A-pre_i)\times(B-i+1)

    拆下式子(A\sum 1-\sum pre_i)(B+1)-A\sum i+\sum ipre_i

    可以发现这种情况可以用主席树维护

树上情况

观察数据形成方式:

  • p个点形成一条主链,其他点随机向主链连边
    所以树上任意点对的\texttt{lca}距离他们期望为\mathcal O(\log n)
  • 每个点的颜色在[1,n]中随机,每种颜色数目期望为1

pre_ii的祖先中颜色与i相同的深度最大的点

第一问

xyx\texttt{lca}(x,y)更近

首先求出y\texttt{lca}链上的颜色总数,

然后再暴力枚举x\texttt{lca}链上的颜色更新答案

第二问

ABA\texttt{lca}(A,B)更近

分类讨论:

  1. x\in [1,\texttt{lca}],y\in [1,B],与链上的情况相同
  2. x\in [\texttt{lca},A],y\in [1,\texttt{lca}]

    x\in [1,A],y\in [1,\texttt{lca}]的答案减去

    x,y\in [1,\texttt{lca})的答案\sum (2(i-pre_i)(\texttt{lca}-i)-1)

    拆下式子: 2\texttt{lca}\sum (i-pre_i) - 2\sum i(i-pre_i)-\sum 1

  3. x\in [\texttt{lca},A],y\in [\texttt{lca},B]

    先求出i\in [\texttt{lca,B}]的贡献\sum (B-i+1)(A-\texttt{lca}+1)

    拆下式子: (A-\texttt{lca}+1)(\sum B+1 - \sum i)

    然后用i\in (\texttt{lca},A]更新

    pre_i\le\texttt{lca},设j[\texttt{lca},B]中第一个与它颜色相同的点

    贡献: (A-i+1)(j-\texttt{lca})

avatar
zc
2020-09-21 21:09:00

查看原题

点击跳转

解法

记录每个点i前一个与它一样的位置pre_i,

那么区间[l,r]内不同的个数也就是[l,r]pre_i<l的个数

主席树

#include<bits/stdc++.h>
const int N=1000011;
int n,q,lst[N],RT[N],sz,s[N*20],ls[N*20],rs[N*20];
void build(int&x,int l,int r){
    x=++sz;
    if(l==r)return;
    int m=l+r>>1;
    build(ls[x],l,m);build(rs[x],m+1,r);
}
void ins(int&x,int pre,int p,int l,int r){
    s[x=++sz]=s[pre]+1;
    if(l==r)return;
    ls[x]=ls[pre],rs[x]=rs[pre];
    int m=l+r>>1;
    if(p<=m)ins(ls[x],ls[pre],p,l,m);
    else ins(rs[x],rs[pre],p,m+1,r);
}
int ask(int x,int y,int R,int l,int r){
    if(r<=R)return s[y]-s[x];
    int m=l+r>>1;
    return ask(ls[x],ls[y],R,l,m)+(R>m?ask(rs[x],rs[y],R,m+1,r):0);
}
void read(int&x){
    x=0;char c=getchar();
    for(;c<'0'||'9'<c;c=getchar());
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-48;
}
int main(){
    read(n);
    int x,l,r;
    build(RT[0],1,n);
    for(int i=1;i<=n;++i)
        read(x),
        ins(RT[i],RT[i-1],lst[x]+1,1,n),
        lst[x]=i;
    read(q);
    while(q--)
        read(l),read(r),
        printf("%d\n",ask(RT[l-1],RT[r],l,1,n));
}

主席树理论上是可以过的,可是为了卡莫队,主席树也TLE了

R.I.P

树状数组

还是求[l,r]pre_i<l的个数

离线处理

询问按右端点从小到大排序

枚举区间,将[1,r]中的点,i位置+1,pre_i位置-1(i之前pre_i已经贡献过了)

那么r减去l-1的前缀和就是答案

avatar
zc
2020-03-01 11:57:00
查看原题

点击跳转

看题意想到了主席树和LCT

LCT套主席树可行,但是比较麻烦,我们用另一种方法

启发式合并+主席树(\mathcal{n \log^2 n})

每次将小的插入到大的,顺便更新倍增LCA

每个节点在父节点的基础上插入自身的值

即每个节点的主席树记录的是自身到根节点的路径

具体看代码

avatar
zc
2020-02-02 17:36:00
查看原题

点击跳转

AC自动机建完fail树之后子树的siz就是里面相同字符串的个数

每个询问可以拆成r的前缀和-l的前缀和

然后离线处理后用树状数组维护就可以了

主席树在线也可以

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

dfs序作为下标,深度作为时间轴

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

模板

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

a是确定的,考虑b的情况:

  1. a的祖先

    可以作为b的点的数量是\min(d_x,k)(d_xx的深度),

    a的子树中除a外其他点都可以作为c

    总方案数为\min(d_x,k)\times(siz_x-1)

  2. a子树中

    对于每个b,可以作为c的点的数量为siz_b-1

    我们可以dfs序,记录当前区间中深度为d的数

    然后用主席树(可持久化权值线段树)维护

    这样就可以查询深度\in [d_a+1,d_a+k]的所有'点的子树大小-1'的和

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

可以看成两道题吧

50\%: 二维前缀和+二分

50\%: 主席树同时维护区间大于k的个数、总和,然后二分即可

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

可以算是kruskal重构树的模板题

建完kruskal重构树,我们可以发现一个节点(新建的带点权的点)能走到的节点一定在它的子树中

那么我们可以用dfs序+主席树维护

kruskal重构树

我们回想一下kruskal生成最小生成树的过程:

先将边按边权从小到大排序,然后依次加入

如果x,y已经联通,则跳过这条边

否则连接x,y

kruskal重构树是在kruskal生成最小生成树的,

连接x,y时,将边权变成一个新的节点t权值为边权,然后连边> t\rightarrow x,t\rightarrow y

代码:

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

解法1

主席树+离散化(深度太大需要离散化)

1/2
Search
search