0%

树链剖分

最近在学树链剖分,记录一下做的题目。

几道都是树状数组写的,线段树还需要好好练习啊。

模板

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define Rint register int
#define mem(a,b) memset(a,(b),sizeof(a))
#define Temp template<typename T>
using namespace std;
typedef long long LL;
Temp inline void read(T &x){
    x=0;T w=1,ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}

#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)

const int maxn=200000+10;
int n,m,r,mod;

int e,beg[maxn],nex[maxn],to[maxn],w[maxn],wt[maxn];

int a[maxn<<2],laz[maxn<<2];

int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn]; 

int res=0;

inline void add(int x,int y){
    to[++e]=y;
    nex[e]=beg[x];
    beg[x]=e;
}
inline void pushdown(int rt,int lenn){
    laz[rt<<1]+=laz[rt];
    laz[rt<<1|1]+=laz[rt];
    a[rt<<1]+=laz[rt]*(lenn-(lenn>>1));
    a[rt<<1|1]+=laz[rt]*(lenn>>1);
    a[rt<<1]%=mod;
    a[rt<<1|1]%=mod;
    laz[rt]=0;
}

inline void build(int rt,int l,int r){
    if(l==r){
        a[rt]=wt[l];
        if(a[rt]>mod)a[rt]%=mod;
        return;
    }
    build(lson);
    build(rson);
    a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
}

inline void query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R){res+=a[rt];res%=mod;return;}
    else{
        if(laz[rt])pushdown(rt,len);
        if(L<=mid)query(lson,L,R);
        if(R>mid)query(rson,L,R);
    }
}

inline void update(int rt,int l,int r,int L,int R,int k){
    if(L<=l&&r<=R){
        laz[rt]+=k;
        a[rt]+=k*len;
    }
    else{
        if(laz[rt])pushdown(rt,len);
        if(L<=mid)update(lson,L,R,k);
        if(R>mid)update(rson,L,R,k);
        a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
    }
}
inline int qRange(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res=0;
        query(1,1,n,id[top[x]],id[x]);
        ans+=res;
        ans%=mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    res=0;
    query(1,1,n,id[x],id[y]);
    ans+=res;
    return ans%mod;
}

inline void updRange(int x,int y,int k){
    k%=mod;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,1,n,id[x],id[y],k);
}

inline int qSon(int x){
    res=0;
    query(1,1,n,id[x],id[x]+siz[x]-1);
    return res;
}

inline void updSon(int x,int k){
    update(1,1,n,id[x],id[x]+siz[x]-1,k);
}

inline void dfs1(int x,int f,int deep){
    dep[x]=deep;
    fa[x]=f; 
    siz[x]=1;
    int maxson=-1;
    for(Rint i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>maxson)son[x]=y,maxson=siz[y];
    }
}

inline void dfs2(int x,int topf){
    id[x]=++cnt;
    wt[cnt]=w[x];
    top[x]=topf;
    if(!son[x])return;
    dfs2(son[x],topf);
    for(Rint i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}

int main(){
    read(n);read(m);read(r);read(mod);
    for(Rint i=1;i<=n;i++)read(w[i]);
    for(Rint i=1;i<n;i++){
        int a,b;
        read(a);read(b);
        add(a,b);add(b,a);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int k,x,y,z;
        read(k);
        if(k==1){
            read(x);read(y);read(z);
            updRange(x,y,z);
        }
        else if(k==2){
            read(x);read(y);
            printf("%d\n",qRange(x,y));
        }
        else if(k==3){
            read(x);read(y);
            updSon(x,y);
        }
        else{
            read(x);
            printf("%d\n",qSon(x));
        }
    }
}

P2982

#include<bits/stdc++.h>
using namespace std;
#define lowbit (x&-x)

const int maxn=1000005;
int n,cnt,head[maxn],p[maxn],tr[maxn],ans[maxn];
struct node{
    int n,v;
}q[maxn<<1];

int read() {
    int s=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') {s=s*10+ch-'0';ch=getchar();}
    return s*f;
}
void add(int x,int y) {
    q[++cnt].n=head[x];
    q[cnt].v=y;
    head[x]=cnt;
    q[++cnt].n=head[y];
    q[cnt].v=x;
    head[y]=cnt;
}
void up(int x,int k) {
    while(x<=n) {
        tr[x]+=k;
        x+=lowbit;
    }
}
int sum(int x) {
    int rec=0;
    while(x) {
        rec+=tr[x];
        x-=lowbit;
    }
    return rec;
}
void dfs(int u,int fa) {
    ans[p[u]]=sum(p[u]);
    up(p[u],1);
    for(int i=head[u];i;i=q[i].n) {
        int v=q[i].v;
        if(v==fa) continue;
        dfs(v,u);
    }
    up(p[u],-1);
}

int main() {
    ios::sync_with_stdio(false);
    n=read();
    for(int i=1;i<n;i++) {
        add(read(),read());
    }
    for(int i=1;i<=n;i++) {p[read()]=i;}
    dfs(1,-1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}

P3038

#include<bits/stdc++.h>
using namespace std;
#define lowbit (x&-x)

const int maxn=1000005;
int n,m,cnt,head[maxn],p[maxn],tr[maxn],ans[maxn];
int son[maxn],fa[maxn],top[maxn],dfn[maxn],dep[maxn],siz[maxn],unk;
struct node{
    int n,v;
}q[maxn<<1];

int read() {
    int s=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') {s=s*10+ch-'0';ch=getchar();}
    return s*f;
}
void addedge(int x,int y) {
    q[++cnt].n=head[x];
    q[cnt].v=y;
    head[x]=cnt;
    q[++cnt].n=head[y];
    q[cnt].v=x;
    head[y]=cnt;
}
void up(int x,int k) {
    while(x<=n) {
        tr[x]+=k;
        x+=lowbit;
    }
}
int sum(int x) {
    int rec=0;
    while(x) {
        rec+=tr[x];
        x-=lowbit;
    }
    return rec;
}
void ranup(int l,int r,int k) {
    up(l,k);
    up(r+1,-k);
}
void dfs1(int u,int f,int d) {
    fa[u]=f,dep[u]=d,siz[u]=1;
    for(int i=head[u];i;i=q[i].n) {
        int v=q[i].v;
        if(v==f) continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int t) {
    top[u]=t,dfn[u]=++unk;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=q[i].n) {
        int v=q[i].v;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
void add(int x,int y,int k) {
    int tx=top[x],ty=top[y];
    while(tx!=ty) {
        if(dep[tx]>=dep[ty]) ranup(dfn[tx],dfn[x],k),x=fa[tx],tx=top[x];
        else ranup(dfn[ty],dfn[y],k),y=fa[ty],ty=top[y];
    }
    if(x==y) return;
    if (dfn[x]<=dfn[y]) ranup(dfn[x] + 1, dfn[y], k);
    else ranup(dfn[y] + 1, dfn[x], k);
}
int main() {
    n=read(),m=read();
    for(int i=1;i<n;i++) {
        addedge(read(),read());
    }
    dfs1(1,-1,1);
    dfs2(1,1);
    while(m--) {
        char o=getchar();
        int x,y;
        while(o != 'P' && o != 'Q') o=getchar();
        x=read(),y=read();
        if(o=='P') {
            add(x,y,1);
        }
        else if(o=='Q'){
            if(dep[x]>dep[y])cout<<sum(dfn[x])<<endl;
            else cout<<sum(dfn[y])<<endl;
        }
    }
    return 0;
}