妈的智障

懵逼的 题目

传送至 Bilibili

扯淡的 题解

水, 线段树区间修改单点查询

沙茶的 代码

我在一下午的时间里

  • 查询和修改没有写push_down
  • 最后输出答案的时候把i搞成了a[i]
  • +=写成=
  • (b[dq].le + b[dq].ri) >> 1写成(le + ri) >> 1
  • 树链剖分把if (ta[ta[x].top].deep < ta[ta[y].top].deep), 写成if (ta[x].deep > ta[y].deep)

我怎么越来越沙茶了…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (300000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define int long long
using namespace std;
struct node
{
    int le, ri, zh, lazy;
}b[MAXN << 2];
struct tnode
{
    int deep, fa, hs, top, start, end, size;
}ta[MAXN];
struct tedg
{
    int from, to, next;
}tb[MAXN << 1];
int tg[MAXN], cntb, cnta, cnt[MAXN], a[MAXN];
node push_up(node ls, node rs)
{
    node re;
    re.lazy = 0;
    re.le = ls.le, re.ri = rs.ri;
    re.zh = ls.zh + rs.zh;
    return re;
}
void push_down(int dq)
{
    int &x = b[dq].lazy;
    b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1) * x;
    b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1) * x;
    b[LS(dq)].lazy += x, b[RS(dq)].lazy += x;
    x = 0;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    b[dq].zh = b[dq].lazy = 0;
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].lazy += zh;
        b[dq].zh += (ri - le + 1) * zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (b[dq].lazy)
        push_down(dq);
    if (le > mi)
        xg(RS(dq), le, ri, zh);
    else if (ri <= mi)
        xg(LS(dq), le, ri, zh);
    else
        xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
    b[dq] = push_up(b[LS(dq)], b[RS(dq)]);
}
int cx(int dq, int wz)
{
    if (b[dq].le == b[dq].ri)
        return b[dq].zh;
    if (b[dq].lazy)
        push_down(dq);
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (wz <= mi)
        return cx(LS(dq), wz);
    else
        return cx(RS(dq), wz);
}
void init(int dq, int deep)
{
    ta[dq].deep = deep;
    ta[dq].size = 1;
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            init(tb[i].to, deep + 1);
            ta[dq].size += ta[tb[i].to].size;
            if (ta[tb[i].to].size > ta[ta[dq].hs].size)
                ta[dq].hs = tb[i].to;
        }
}
void dfs(int dq)
{
    ta[dq].start = ++cnta;
    if (ta[dq].hs)
        ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
        {
            ta[tb[i].to].top = tb[i].to;
            dfs(tb[i].to);
        }
    ta[dq].end = cnta;
}
void solve(int x, int y, int zh)
{
    while (ta[x].top != ta[y].top)
    {
        if (ta[ta[x].top].deep < ta[ta[y].top].deep)
            swap(x, y);
        xg(1, ta[ta[x].top].start, ta[x].start, 1);
        x = ta[ta[x].top].fa;
    }
    if (ta[x].deep > ta[y].deep)
        swap(x, y);
    xg(1, ta[x].start, ta[y].start, 1);
}
void adn(int from, int to)
{
    tb[++cntb].next = tg[from];
    tb[cntb].from = from;
    tb[cntb].to = to;
    tg[from] = cntb;
}
main()
{
    int n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)    scanf("%lld", &a[i]);
    for (int i = 1; i < n; i++)
    {
        int srx, sry;
        scanf("%lld%lld", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    ta[1].fa = ta[1].top = 1;
    init(1, 1);
    dfs(1);
    js(1, 1, n);
    for (int i = 2; i <= n; i++)
        solve(a[i], a[i - 1], 1), ++cnt[a[i]];
    for (int i = 1; i <= n; i++)
        printf("%lld\n", cx(1, ta[i].start) - cnt[i]);
}

/*
5
1 4 5 3 2
1 2
2 4
2 3
4 5
*/

By 日渐沙茶的 Cansult