代码神题…又写了一两周好像…

能胡出思路并不代表能得哪怕10分…

懵逼的 题目

****

扯淡的 题解

如果我把正数放在一边, 负数放在一边…

$0 \le d$ …也就是所有的点权都不会变小…

Emmmmm…我可以算出每一个点在什么时刻变成正数了…

然后就可以在树剖的时候在单点修改一波了吧…

$\uparrow$ 想的思路, 很简单吧…

尝试写一下就毁天灭地啦

想一想我需要什么…

  • 写一个普通树剖, 维护的是点权, 只需要一个树状数组be[]支持区间加, 单点查
    • 在普通树剖下加一个函数, 把一个修改操作拆成一些区间修改…vector<question> que[MAXN]
  • 写一个不普通树剖, 维护的是点权的绝对值, 线段树b要求可以区间加, 区间求和, 单点赋值
    • 这个区间加不是普通的区间加= =…节点还需要维护两个值: zz, fz: 表示区间内正/负数的个数(在单点赋值的时候顺便维护一下, 这个好像要用树状数组吧)
  • 写一个整体二分, 来找每一个数变成正数的时间(在哪一次操作后)NT[]
    • void ef(int leq, int riq, int lea, int ria):
      • leq == riq: NT[na[lea ~ ria].bh] = leq, return ;
      • midq = (leq + riq) >> 1, 把所有在midq时间点之前的修改操作都加上, 按照权值从大到小排序, 把大于零的挪到左边, 恢复他的权值, 小于零的挪到右边(结构体里需要一个变量ok判断是否权值大于0), 权值不变, 然后继续二分
  • 然后找答案的时候要在不普通树剖里做…

总复杂度是$\mathrm O(n \lg n)$

好像也没啥东西

然后就是花式翻车啦~

  • int i = re;

翻车$\times 1$

  • 差分, 区间修改, 把区间右端点修改为了zh (应该是-zh)

翻车$\times 2$

  • b[LS(dq)].lazy += x, b[RS(dq)].lazy += x$\to$b[LS(dq)].lazy = b[RS(dq)].lazy += x

翻车$\times 3$

  • ne = ... $\to$ n = ...

翻车$\times 4$

  • 两个修改都没有用LL做形参

翻车$\times 5$

沙茶的 代码

又是写了好几天的代码…

zky学长好毒啊

10k代码了解一下

/**************************************************************
    Problem: 4127
    User: Cansult
    Language: C++
    Result: Accepted
    Time:15528 ms
    Memory:33524 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (100000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define lowbit(i) ((i) & (-(i)))
#define LL long long
using namespace std;
struct tnode
{ int deep, fa, top, size, hs, begin, end; };
struct tedg
{ int from, to, next; };
struct question
{
    int x, y, zh;
    question() {}
    question(int dqx, int dqy, int dqzh): x(dqx), y(dqy), zh(dqzh) {}
};
struct snode
{
    int le, ri;
    LL zh, lazy;
};
struct anode
{
    int bh, ok;
    LL zh;
};
struct bitt
{
    LL b[MAXN];
    int n;
    void init(int xn)
    { n = xn; }
    void txg(int wz, LL zh)
    {
        for (int i = wz; i <= n; i += lowbit(i))
            b[i] += zh;
    }
    void xg(int le, int ri, LL zh)
    { txg(le, zh), txg(ri + 1, -zh); }
    LL cx(int wz)
    {
        LL re = 0;
        for (int i = wz; i; i -= lowbit(i))
            re += b[i];
        return re;
    }
};
struct bitt2
{
    int b[MAXN], n;
    void init(int xn) { n = xn; }
    void xg(int wz, int zh)
    {
        for (int i = wz; i <= n; i += lowbit(i))
            b[i] += zh;
    }
    int cx(int le, int ri)
    {
        int re = 0;
        for (int i = le - 1; i; i -= lowbit(i))
            re -= b[i];
        for (int i = ri; i; i -= lowbit(i))
            re += b[i];
        return re;
    }
};
struct segt
{
    int n;
    snode b[MAXN << 2];
    bitt2 fn;
    void push_up(int dq)
    { b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh; }
    void push_down(int dq)
    {
        LL& x = b[dq].lazy;
        b[LS(dq)].lazy += x;
        b[RS(dq)].lazy += x;
        int ne = fn.cx(b[LS(dq)].le, b[LS(dq)].ri);
        b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1 - ne) * x;
        b[LS(dq)].zh -= x * ne;
        ne = fn.cx(b[RS(dq)].le, b[RS(dq)].ri);
        b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1 - ne) * x;
        b[RS(dq)].zh -= x * ne;
        x = 0;
    }
    void js(int dq, int le, int ri, int *a)
    {
        b[dq].le = le, b[dq].ri = ri;
        if (le == ri)
        {
            b[dq].zh = abs(a[le]);
            if (a[le] < 0)
                fn.xg(le, 1);
            return ;
        }
        int mi = (le + ri) >> 1;
        js(LS(dq), le, mi, a);
        js(RS(dq), mi + 1, ri, a);
        push_up(dq);
    }
    void xgs(int dq, int le, int ri, LL zh) // 区间加
    {
        if (b[dq].le == le && b[dq].ri == ri)
        {
            b[dq].lazy += zh;
            int ne = fn.cx(le, ri);
            b[dq].zh += (ri - le + 1 - ne) * zh;
            b[dq].zh -= ne * zh;
            return ;
        }
        if (b[dq].lazy)
            push_down(dq);
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
            xgs(RS(dq), le, ri, zh);
        else if (ri <= mi)
            xgs(LS(dq), le, ri, zh);
        else
            xgs(LS(dq), le, mi, zh), xgs(RS(dq), mi + 1, ri, zh);
        push_up(dq);
    }
    void xgn(int dq, int wz, LL zh) // 单点赋值
    {
        if (b[dq].le == b[dq].ri)
        {
            b[dq].zh = zh;
            fn.xg(wz, -1);
            return ;
        }
        if (b[dq].lazy)
            push_down(dq);
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (wz > mi)
            xgn(RS(dq), wz, zh);
        else
            xgn(LS(dq), wz, zh);
        push_up(dq);
    }
    LL cx(int dq, int le, int ri)
    {
        if (b[dq].le == le && b[dq].ri == ri)
            return b[dq].zh;
        if (b[dq].lazy)
            push_down(dq);
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
            return cx(RS(dq), le, ri);
        else if (ri <= mi)
            return cx(LS(dq), le, ri);
        else
            return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
    }
    void init(int xn, int *a)
    {
        fn.init(n = xn);
        js(1, 1, n, a);
    }
};
struct tree
{
    int a[MAXN], n, cnta, g[MAXN], cntb;
    tedg tb[MAXN << 1];
    tnode ta[MAXN];
    segt b;
    void adn(int from, int to)
    {
        tb[++cntb].next = g[from];
        tb[cntb].from = from;
        tb[cntb].to = to;
        g[from] = cntb;
    }
    void init(int dq, int deep)
    {
        ta[dq].deep = deep;
        ta[dq].size = 1;
        for (int i = g[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, int *xa)
    {
        a[ta[dq].begin = ++cnta] = xa[dq];
        if (ta[dq].hs)
            ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs, xa);
        for (int i = g[dq]; i; i = tb[i].next)
            if (tb[i].to != ta[dq].hs && tb[i].to != ta[dq].fa)
            {
                ta[tb[i].to].top = tb[i].to;
                dfs(tb[i].to, xa);
            }
        ta[dq].end = cnta;
    }
    LL cx(int x, int y)
    {
        LL re = 0;
        while (ta[x].top != ta[y].top)
        {
            if (ta[ta[x].top].deep < ta[ta[y].top].deep)
                swap(x, y);
            re += b.cx(1, ta[ta[x].top].begin, ta[x].begin);
            x = ta[ta[x].top].fa;
        }
        if (ta[x].deep > ta[y].deep)
            swap(x, y);
        re += b.cx(1, ta[x].begin, ta[y].begin);
        return re;
    }
    void QwQ(int x, int y, vector<question>& dqq, int zh) // 分解询问
    {
        while (ta[x].top != ta[y].top)
        {
            if (ta[ta[x].top].deep < ta[ta[y].top].deep)
                swap(x, y);
            dqq.push_back(question(ta[ta[x].top].begin, ta[x].begin, zh));
            x = ta[ta[x].top].fa;
        }
        if (ta[x].deep > ta[y].deep)
            swap(x, y);
        dqq.push_back(question(ta[x].begin, ta[y].begin, zh));
    }
    void QAQ(int xn, int *xa) // 初始化
    {
        n = xn;
        ta[1].top = ta[1].fa = 1;
        init(1, 1);
        dfs(1, xa);
        b.init(n, a);
    }
}TA;
int q, n, xgq, cxq;
LL bz[MAXN];
anode a[MAXN], tmp[MAXN];
bitt b;
question cx[MAXN];
vector<question> que[MAXN];
vector<int> tim[MAXN];
bool cmp(anode x, anode y)
{ return x.ok > y.ok; }
bool cmpz(anode x, anode y)
{ return x.zh < y.zh; }
void ef(int leq, int riq, int lea, int ria)
{
    if (lea > ria)
        return ;
    if (leq == riq)
    {
        for (int i = 0; i < que[leq].size(); i++)
            b.xg(que[leq][i].x, que[leq][i].y, que[leq][i].zh);
        for (int i = lea; i <= ria; i++)
        {
            LL dqc = b.cx(TA.ta[a[i].bh].begin);
            if (a[i].zh + dqc >= 0)
                tim[leq].push_back(a[i].bh), bz[a[i].bh] = a[i].zh + dqc;
        }
        for (int i = 0; i < que[leq].size(); i++)
            b.xg(que[leq][i].x, que[leq][i].y, -que[leq][i].zh);
        return ;
    }
    int mi = (leq + riq) >> 1;
    for (int i = leq; i <= mi; i++)
        for (int j = 0; j < que[i].size(); j++)
            b.xg(que[i][j].x, que[i][j].y, que[i][j].zh);
    int nria = lea - 1;
    for (int i = lea; i <= ria; i++)
    {
        a[i].ok = 0;
        LL dqc = b.cx(TA.ta[a[i].bh].begin);
        if (a[i].zh + dqc > 0)
            ++nria, a[i].ok = 1;
        else
            a[i].zh += dqc;
    }
    for (int i = leq; i <= mi; i++)
        for (int j = 0; j < que[i].size(); j++)
            b.xg(que[i][j].x, que[i][j].y, -que[i][j].zh);
    sort(a + lea, a + ria + 1, cmp);
    ef(leq, mi, lea, nria);
    ef(mi + 1, riq, nria + 1, ria);
}
int main()
{
    int sra[MAXN];
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i].zh), sra[i] = a[i].zh, a[i].bh = i;
    for (int i = 1, srx, sry; i < n; i++)
    {
        scanf("%d%d", &srx, &sry);
        TA.adn(srx, sry);
        TA.adn(sry, srx);
    }
    TA.QAQ(n, sra);
    for (int i = 1, sre, srx, sry, srz; i <= q; i++)
    {
        scanf("%d", &sre);
        if (sre == 1)
        {
            ++xgq;
            scanf("%d%d%d", &srx, &sry, &srz);
            TA.QwQ(srx, sry, que[xgq], srz);
        }
        else
        {
            ++cxq;
            scanf("%d%d", &cx[cxq].x, &cx[cxq].y);
            cx[cxq].zh = xgq;
        }
    }
    sort(a + 1, a + n + 1, cmpz);
    int zn = 0;
    a[n + 1].zh = 1;
    for (int i = 1; i <= n + 1; i++)
        if (a[i].zh >= 0)
        {
            zn = i - 1;
            break;
        }
    b.init(n);
    if (xgq)
        ef(1, xgq, 1, zn);
    for (int i = 0, cxi = 1; i <= xgq; i++)
    {
        for (int j = 0; j < que[i].size(); j++)
            TA.b.xgs(1, que[i][j].x, que[i][j].y, que[i][j].zh);
        for (int j = 0; j < tim[i].size(); j++)
        {
            int wz = TA.ta[tim[i][j]].begin;
            TA.b.xgn(1, wz, bz[tim[i][j]]);
        }
        while (cxi <= cxq && cx[cxi].zh == i)
            printf("%lld\n", TA.cx(cx[cxi].x, cx[cxi].y)), ++cxi;
    }
    return 0;
}
/*
6 3
6 0 -6 2 0 5 
1 4
1 2
1 5
2 6
6 3
1 2 3 3
1 6 6 6
2 4 4
*/

By 沙茶 Cansult