头像

lzyz000




离线:1天前


最近来访(13)
用户头像
夏旭日
用户头像
AC摆渡人
用户头像
Pipipapi
用户头像
Immature
用户头像
luxcgo
用户头像
lzyz222
用户头像
莫斯科不相信眼泪
用户头像
用户头像
邈云汉
用户头像
烧魔芋
用户头像
kukudewen
用户头像
不想罚座
用户头像
QAQlzy


lzyz000
2天前

最近在做树链剖分的时候,在luogu上遇到了一道非常毒瘤的题目: luogu P1505 旅游,其中涉及到了边权转为点权的一系列问题。

y总在进阶课中并没有涉及边权转点权的内容。我的思路是将两个点中间的边权转到这两个点中深度较深的点上面,在进行树链剖分,求精通树剖的dalao纠正思路,谢谢。 关于树剖中边权转点权思路及图示.png
(顺便再给两道边权转点权的例题呗QAQ)




lzyz000
4天前

题目比较简单,就是一道树剖裸题

题意简介:
现在给定一棵根为零的树,树上节点点权都是零
现在给定两个操作:

  • Add u v k, 表示将树从uv的路径上的点全都加上k;

  • Query u, 表示询问u的子树点权和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;
const int N = 100010, M = N << 1;
int h[N], e[M], ne[M], idx;
int id[N], top[N], cnt;
int sz[N], son[N], fa[N], dep[N];
int n, m;

struct Tree
{
    int l, r;
    LL add, sum;
}tr[N << 2];

int len(int u)
{
    return tr[u].r - tr[u].l + 1;
}

void add(int a, int b)
{
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs1(int u, int father, int depth)
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;

    for (int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int t)
{
    id[u] = ++ cnt, top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);

    for (int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    int k = tr[u].add;
    if (k)
    {
        tr[u << 1].add += k, tr[u << 1 | 1].add += k;
        tr[u << 1].sum += len(u << 1) * k, tr[u << 1 | 1].sum += len(u << 1 | 1) * k;
        tr[u].add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l == r) return;

    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].add += k, tr[u].sum += len(u) * k;
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r, k);
    if (r > mid) modify(u << 1 | 1, l, r, k);
    pushup(u);
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL res = 0;
    if (l <= mid) res = query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);

    return res;
}

void modify_path(int u, int v, int k)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        modify(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }

    if (dep[u] < dep[v]) swap(u, v);
    modify(1, id[v], id[u], k);
} 

LL query_tree(int u)
{
    return query(1, id[u], id[u] + sz[u] - 1);
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a += 1, b += 1;
        add(a, b), add(b, a);
    }

    dfs1(1, 0, 1), dfs2(1, 1), build(1, 1, n);
    scanf("%d", &m);
    char op[6];
    int u, v, k;

    while (m -- )
    {
        scanf("%s%d", op, &u);
        u += 1;
        if (*op == 'A')
        {
            scanf("%d%d", &v, &k);
            v += 1;
            modify_path(u, v, k);
        }
        else
            printf("%lld\n", query_tree(u));
    }

    return 0;
}


活动打卡代码 AcWing 2568. 树链剖分

lzyz000
10天前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010, M = N << 1;
int n, m;
int w[N], h[N], e[M], ne[M], idx;
int sz[N], nw[N], top[N], fa[N], son[N];
int dep[N], id[N], cnt;
struct Tree
{
    int l, r;
    LL add, sum;
}tr[N << 2];

void add(int a, int b)
{
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

// _____________________ 树链剖分 __________________________
void dfs1(int u, int father, int depth)
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int t)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);

    for (int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

// _____________________ 线段树 ___________________________ 

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    if (tr[u].add)
    {
        tr[u << 1].add += tr[u].add, tr[u << 1].sum += tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1);
        tr[u << 1 | 1].add += tr[u].add, tr[u << 1 | 1].sum += tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
        tr[u].add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, nw[r]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int k)
{
    if (l <= tr[u].l && r >= tr[u].r)
    {
        tr[u].add += k, tr[u].sum += k * (tr[u].r - tr[u].l + 1);
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r, k);
    if (r > mid) modify(u << 1 | 1, l, r, k);
    pushup(u);
}

LL query(int u, int l, int r)
{
    if (l <= tr[u].l && r >= tr[u].r)
        return tr[u].sum;

    pushdown(u);
    LL res = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) res = query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);

    return res;
}

// // _____________________ 询问函数 ___________________________ 
void modify_path(int u, int v, int k)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        modify(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }

    if (dep[u] < dep[v]) swap(u, v);
    modify(1, id[v], id[u], k);
}

void modify_tree(int u, int k)
{
    modify(1, id[u], id[u] + sz[u] - 1, k);
}

LL query_path(int u, int v)
{
    LL res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }

    if (dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);

    return res;
}

LL query_tree(int u)
{
    return query(1, id[u], id[u] + sz[u] - 1);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &w[i]);

    for (int i = 1; i < n; i ++ )
    {
        int a, b;
        scanf ("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);

    scanf("%d", &m);

    while (m -- )
    {
        int t, u, v, k;
        scanf("%d%d", &t, &u);
        if (t == 1)
        {
            scanf("%d%d", &v, &k);
            modify_path(u, v, k);
        }
        else if (t == 2)
        {
            scanf("%d", &k);
            modify_tree(u, k);
        }
        else if (t == 3)
        {
            scanf("%d", &v);
            printf("%lld\n", query_path(u, v));
        }
        else
            printf("%lld\n", query_tree(u));
    }

    return 0;
}



lzyz000
3个月前

解释都在代码里;

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Splay
{
    int s[2], p, v; // s[0] 代表左儿子,s[1] 代表右儿子,p 代表父亲,v 代表权值
    int size, flag; // size 代表大小,flag 代表懒标记,表示当前序列需不需要旋转

    void init(int _v, int _p) // 初始化
    {
        v = _v, p = _p;
        size = 1;
    }
}tr[N];

int root, idx, n, m;

void pushup(int x) // 用儿子的信息更新父亲
{
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1; // 父亲的大小 = 左儿子大小 + 右儿子大小 + 根节点
}

void pushdown(int x) // 下传懒标记
{
    if (tr[x].flag)
    {
        swap(tr[x].s[0], tr[x].s[1]); // 先将序列反转
        tr[tr[x].s[0]].flag ^= 1;
        tr[tr[x].s[1]].flag ^= 1;
        tr[x].flag = 0; // 清空懒标记
    }
}

void rotate(int x) // 旋转,包括左旋和右旋;
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;

    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;

    pushup(y), pushup(x); // 一定要先pushup(y), 才能pushup(x);
}

void splay(int x, int k)
{
    while (tr[x].p != k)
    {
        int y = tr[x].p;
        int z = tr[y].p;

        if (z != k)
        {
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(y); // 判断是链是折线
            else rotate(x);
        }
        rotate(x);
    }

    if (!k) root = x;
}

void insert(int v)
{
    int u = root, p = 0;
    while (u) p = u, u = tr[u].s[v > tr[u].v]; // 判断插入左边还是右边

    u = ++ idx;
    if(p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v, p);

    splay(u, 0);
}

int get_k(int k)
{
    int u = root;

    while (true)
    {
        pushdown(u);

        if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].size + 1 ==k ) return u;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }

    return -1;
}

void output(int u) // 输出中序遍历
{
    pushdown(u);

    if (tr[u].s[0]) output(tr[u].s[0]);
    if (tr[u].v >= 1 && tr[u].v <= n) printf("%d ", tr[u].v);
    if (tr[u].s[1]) output(tr[u].s[1]);
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i <= n + 1; i ++ ) insert(i); // 别忘了加上两个 “哨兵”

    while ( m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);

        l=get_k(l), r=get_k(r+2);

        splay(l, 0), splay(r, l);

        tr[tr[r].s[0]].flag ^= 1;
    }

    output(root);

    return 0;
}


活动打卡代码 AcWing 158. 项链

lzyz000
5个月前
#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n;
char s[2][N];
int get(int x)
{
    int i=1,j=2,k;
    while(i<=n&&j<=n)
    {
        k=0;
        while(k<n&&s[x][i+k]==s[x][j+k])  k++;
        if(k==n)  break;
        if(s[x][i+k]>s[x][j+k])  i+=k+1;
        else  j+=k+1;
        if(i==j)  j++;
    }return min(i,j);
} 
int main()
{
    scanf("%s\n%s",s[0]+1,s[1]+1);n=strlen(s[0]+1);
    for(int i=1;i<=n;i++)  s[0][i+n]=s[0][i],s[1][i+n]=s[1][i];
    int x=get(0),y=get(1);
    for(int i=0;i<n;i++)
        if(s[0][x+i]!=s[1][y+i])  {printf("No");return 0;}
    printf("Yes\n");
    for(int i=0;i<n;i++)  putchar(s[0][i+x]);
    return 0;
}


活动打卡代码 AcWing 3189. Lomsat gelral

lzyz000
5个月前
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long LL; 
int n,m,h[N],nx[N<<1],to[N<<1],cnt,c[N],sz[N],hs[N],mx,tot[N];
LL ans[N],sum;
inline int read()
{
    int s=0;char c=getchar();
    while(!isdigit(c))  c=getchar();
    while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
    return s;
}
void add(int x,int y) {to[++cnt]=y;nx[cnt]=h[x];h[x]=cnt;}
void size(int x,int f)
{
    sz[x]=1;
    for(int i=h[x];i;i=nx[i])
        if(to[i]!=f)
        {
            size(to[i],x);sz[x]+=sz[to[i]];
            if(sz[to[i]]>sz[hs[x]])  hs[x]=to[i];
        }
}
void update(int x,int f,int k,int son)
{
    tot[c[x]]+=k;
    if(k>0)
        if(tot[c[x]]>mx)  mx=tot[c[x]],sum=c[x];
        else if(tot[c[x]]==mx)  sum+=c[x];
    for(int i=h[x];i;i=nx[i])
        if(to[i]!=f&&to[i]!=son)  update(to[i],x,k,son);
}
void dfs(int x,int f,bool w)
{
    for(int i=h[x];i;i=nx[i])
        if(to[i]!=f&&to[i]!=hs[x])  dfs(to[i],x,0);
    if(hs[x])  dfs(hs[x],x,1);
    update(x,f,1,hs[x]);ans[x]=sum;
    if(!w)  update(x,f,-1,0),sum=mx=0;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)  c[i]=read();
    for(int i=1,x,y;i<n;i++)  x=read(),y=read(),add(x,y),add(y,x);
    size(1,0);dfs(1,0,1);
    for(int i=1;i<=n;i++)  printf("%lld ",ans[i]);
    return 0;
}


活动打卡代码 AcWing 2154. 梦幻布丁

lzyz000
5个月前
#include<bits/stdc++.h>
using namespace std;
const int N=100002,M=N*10;
int n,m,h[M],mp[M],nx[N],a[N],ans,sz[M]; 
inline int read()
{
    int s=0;char c=getchar();
    while(!isdigit(c))  c=getchar();
    while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
    return s;
}
void merge(int &x,int &y)
{
    if(x==y)  return;
    if(sz[x]>sz[y])  swap(x,y);
    for(int i=h[x];i;i=nx[i])  ans-=(a[i-1]==y)+(a[i+1]==y);
    for(int i=h[x];i;i=nx[i])
    {
        a[i]=y;
        if(!nx[i])  {nx[i]=h[y];h[y]=h[x];break;}
    }sz[y]+=sz[x],sz[x]=0;h[x]=0;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=M-20;i++)  mp[i]=i;
    for(int i=1;i<=n;i++)  a[i]=read(),ans+=a[i]!=a[i-1],nx[i]=h[a[i]],h[a[i]]=i,sz[a[i]]++;
    while(m--)
    {
        int op=read()-1,x,y;
        if(op)  printf("%d\n",ans);
        else  x=read(),y=read(),merge(mp[x],mp[y]);
    }return 0;
}


活动打卡代码 AcWing 2424. 保龄球

lzyz000
5个月前
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ty;
typedef double db;
ty rd[55];
int n,ans,m;
inline int read()
{
    int s=0;char c=getchar();
    while(!isdigit(c))  c=getchar();
    while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
    return s;
}
int calc()
{
    int nw=0;
    for(int i=1;i<=m;i++)
    {
        nw+=rd[i].fi+rd[i].se;
        if(rd[i].fi+rd[i].se==10)  nw+=rd[i+1].fi;
        if(rd[i].fi==10)  nw+=rd[i+1].se;
    }ans=max(ans,nw);return nw;
}
int rnd(int l,int r) {return rand()%(r-l)+l;}
void work()
{
    for(db t=1e4;t>1e-4;t*=0.99)
    {
        int a=rand()%m+1,b=rand()%m+1,x=calc();
        while(a==b)  b=rand()%m+1;
        swap(rd[a],rd[b]);
        if(n+(rd[n].fi==10)==m)
        {
            int dlt=calc()-x;
            if(exp(dlt/t)<(db)rand()/RAND_MAX)  swap(rd[a],rd[b]);
        }
        else  swap(rd[a],rd[b]);
    }
}
int main()
{
    m=n=read();
    for(int i=1;i<=n;i++)  rd[i].fi=read(),rd[i].se=read();
    if(rd[n].fi==10)  rd[++m].fi=read(),rd[m].se=read();
    for(int i=1;i<=n;i++)  work();
    printf("%d",ans);return 0;
}


活动打卡代码 AcWing 3167. 星星还是树

lzyz000
5个月前
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef double db;
typedef pair<db,db> ty;
ty p[103];
int n;
db ans=1e16;
inline int read()
{
    int s=0;char c=getchar();
    while(!isdigit(c))  c=getchar();
    while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
    return s;
}
db rnd(db l,db r) {return 1.0*rand()/RAND_MAX*(r-l)+l;}
db calc(ty x)
{
    db rt=0;
    for(int i=1;i<=n;i++)  rt+=sqrt((x.x-p[i].x)*(x.x-p[i].x)+(x.y-p[i].y)*(x.y-p[i].y));
    ans=min(ans,rt);return rt;
}
void work()
{
    ty nw(rnd(0,10000),rnd(0,10000));
    for(db t=1e4;t>1e-2;t*=0.99)
    {
        ty x(rnd(nw.x-t,nw.x+t),rnd(nw.y-t,nw.y+t));
        db dlt=calc(x)-calc(nw);
        if(exp(-dlt/t)>rnd(0,1))  nw=x;
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)  p[i].x=read(),p[i].y=read();
    for(int i=1;i<=100;i++)  work();
    printf("%.0lf",ans);return 0;
}


活动打卡代码 AcWing 210. 异或运算

lzyz000
5个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int T,n,q,k;
LL a[10005];
inline LL read()
{
    LL s=0;char c=getchar();
    while(!isdigit(c))  c=getchar();
    while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
    return s;
}
int main()
{
    T=read();
    for(int t=1;t<=T;t++)
    {
        printf("Case #%d:\n",t);n=read();k=0;
        for(int i=0;i<n;i++)  a[i]=read();
        for(int i=59;~i;i--)
        {
            for(int j=k;j<n;j++)
                if(a[j]&(1ll<<i))  {swap(a[j],a[k]);break;}
            if(!(a[k]&(1ll<<i)))  continue;
            for(int j=0;j<n;j++)
                if(j!=k&&(a[j]&(1ll<<i)))  a[j]^=a[k];
            if(++k==n)  break;
        }reverse(a,a+k);q=read();
        while(q--)
        {
            LL x=read()-(k<n),ans=0;
            if(x>=(1ll<<k))  ans=-1;
            else
                for(int i=0;i<k;i++)
                    if(x&(1ll<<i))  ans^=a[i];
            printf("%lld\n",ans);
        }
    }
    return 0;
}