耐心仔细地推式子才可能写出题来

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈嗝~老娘终于A辣

这里写图片描述

懵逼的 题目

传送至 Codevs

扯淡的 题解

用线段树保存 [从 left 到 right 最小的价钱 / 最大的价钱 / 从左到右最大的收益 / 从右到左最大的收益]
(minz / maxz / maxl / maxr)

b[dq].maxz = max(b[LS(dq)].maxz, b[RS(dq)].maxz);
b[dq].minz = min(b[LS(dq)].minz, b[RS(dq)].minz);
b[dq].maxl = max(max(b[LS(dq)].maxl, b[RS(dq)].maxl), // 最大的收益的买和卖的位置在左或右儿子的完整区间中
                    b[RS(dq)].maxz - b[LS(dq)].minz); // 最大收益的买和卖的位置一个在左儿子的区间内, 一个在右儿子的区间内
b[dq].maxr = max(max(b[LS(dq)].maxr, b[RS(dq)].maxr), // 同上, 但要注意是从右往左走, 注意哪个减哪个
                    b[LS(dq)].maxz - b[RS(dq)].minz);

然后发现用一个线段树存这么多东西比较麻烦, 那干脆一个存从左往右一个从右往左好了…用空间的浪费换来了一点代码复杂度…

Ⅱ 的话其实没必要用树剖做啊…

写一个简单的LCA, 记录 [从当前节点向上跳 (1 << i) 个节点的 最小价钱 / 最大价钱 / 从上向下走的最大收益 / 从下向上走的最大收益]
(minz[x][i], maxz[x][i], maxd[x][i], maxu[x][i])
建树和上面一样, 需要注意这里记录的是点权, 数组的初始值应该包括当前节点, 查询亦然

Ⅲ 是树剖…无法逃避的树剖…
还专门去学了树剖
存储的值和上面的一样…更新是单点更新也很简单…需要注意push_up的时候maxu / maxd的更新要包括最大收益的买卖节点跨过mid的情况…查询也是…要返回最大值和最小值….
然后你会发现T了3个点…因为如果分别查询最大值和最小值的话常数会大到飞起…以至于refun真 dalao都说”要是能卡过去我直播吃屎”结果真的过了233333
所以要直接返回一个结构体…包含(maxu / maxd) && maxz && minz…于是就200ms-的AC辣~ 好像比题解还快?

沙茶的 代码


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define MAXQ (200000 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(a) ((a) << 1)
#define RS(a) (((a) << 1) | 1)

const int root = 1;
using namespace std;

struct node
{
    int le;
    int ri;
    int maxz;// [le, ri]中的最大值
    int minz;// [le, ri]中的最小值
    int maxl;// 从左往右或者从右往左的最大收益
    // int ltr;// [le, ri]中, 从小(左)到大(右)走的最大值
    // int rtl;// [le, ri]中, 从大(右)到小(左)走的最大值
}bl[MAXN << 2], br[MAXN << 2];

int n;
int q;
int la[MAXN];
int ra[MAXN];
void js(int*, node*, int, int, int);
int cx(node*, int, int, int);
int cxmax(node*, int, int, int);
int cxmin(node*, int, int, int);
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &la[i]);
        ra[n - i + 1] = la[i];
    }
    js(la, bl, root, 1, n);
    js(ra, br, root, 1, n);
    scanf("%d", &q);
    int srx, sry;
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &srx, &sry);
        if (srx > sry)
        {
            printf("%d\n", cx(br, root, n - srx + 1, n - sry + 1));
        }
        else
        {
            printf("%d\n", cx(bl, root, srx, sry));
        }
    }
    return 0;
}
void js(int* a, node* b, int dq, int le, int ri)
{
    if (le > ri)
        return ;
    b[dq].le = le;
    b[dq].ri = ri;
    if (le == ri)
    {
        b[dq].maxz = b[dq].minz = a[le];
        b[dq].maxl = 0;
    }
    else
    {
        int mi = (le + ri) >> 1;
        js(a, b, LS(dq), le, mi);
        js(a, b, RS(dq), mi + 1, ri);
        b[dq].maxz = max(b[LS(dq)].maxz, b[RS(dq)].maxz);
        b[dq].minz = min(b[LS(dq)].minz, b[RS(dq)].minz);
        b[dq].maxl = max(max(b[LS(dq)].maxl, b[RS(dq)].maxl), b[RS(dq)].maxz - b[LS(dq)].minz);
    }
}
int cx(node* b, int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq].maxl;
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
        {
            return cx(b, RS(dq), le, ri);
        }
        else if (ri <= mi)
        {
            return cx(b, LS(dq), le, ri);
        }
        else
        {
            int slmax = cx(b, LS(dq), le, mi), srmax = cx(b, RS(dq), mi + 1, ri);
            int lmin = cxmin(b, dq, le, mi), rmax = cxmax(b, dq, mi + 1, ri);
            return max(max(slmax, srmax), rmax - lmin);
//            return max(max(cx(b, LS(dq), le, mi), cx(b, RS(dq), mi + 1, ri)), b[RS(dq)].maxz - b[LS(dq)].minz);
        }
    }
}
int cxmax(node* b, int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq].maxz;
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
        {
            return cxmax(b, RS(dq), le, ri);
        }
        else if (ri <= mi)
        {
            return cxmax(b, LS(dq), le, ri);
        }
        else
        {
            return max(cxmax(b, LS(dq), le, mi), cxmax(b, RS(dq), mi + 1, ri));
        }
    }
}
int cxmin(node* b, int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq].minz;
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
        {
            return cxmin(b, RS(dq), le, ri);
        }
        else if (ri <= mi)
        {
            return cxmin(b, LS(dq), le, ri);
        }
        else
        {
            return min(cxmin(b, LS(dq), le, mi), cxmin(b, RS(dq), mi + 1, ri));
        }
    }
}

/*
10
2 8 15 1 10 5 19 19 3 5
1
6 3
*/


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define MAXQ (10000 + 5)
#define MAXL (20 + 5)
#define INF (0x7ffffff)
#define LL long long
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
//#define DBG emmmmm
const int root = 1;
using namespace std;

struct edg
{
    int from;
    int to;
    int next;
} b[MAXN << 1];
int cntb = 0;
int g[MAXN];

int n;
int q;
int lgn;

int d[MAXN][MAXL];
int fa[MAXN];
int mon[MAXN];
int minc[MAXN][MAXL];
int maxc[MAXN][MAXL];
int maxd[MAXN][MAXL]; // 从上到下
int maxu[MAXN][MAXL]; // 从下到上
int deep[MAXN];

int lg(int);
void init(int, int);
int lca(int,  int);
void adn(int, int);
int main()
{
    scanf("%d", &n);
    lgn = lg(n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &mon[i]);
    }
    int srx, sry;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    d[root][0] = fa[root] = root;
    // maxc[root][0] = minc[root][0] = mon[root];
    init(root, 1);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &srx, &sry);
        printf("%d\n", max(0, lca(srx, sry)));
    }
    return 0;
}
void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}
int lg(int x)
{
    int re = 0;
    for (; (1 << re) <= x; re++)
        ;
    return re;
}
void init(int dq, int de)
{
    deep[dq] = de;
    minc[dq][0] = min(mon[dq], mon[fa[dq]]);
    maxc[dq][0] = max(mon[dq], mon[fa[dq]]);
    maxd[dq][0] = mon[dq] - mon[fa[dq]];
    maxu[dq][0] = mon[fa[dq]] - mon[dq];
    for (int i = 1; i <= lgn; i++)
    {
        d[dq][i] = d[d[dq][i - 1]][i - 1];
        maxc[dq][i] = max(maxc[dq][i - 1], maxc[d[dq][i - 1]][i - 1]);
        minc[dq][i] = min(minc[dq][i - 1], minc[d[dq][i - 1]][i - 1]);
        maxd[dq][i] = max(max(maxd[dq][i - 1], maxd[d[dq][i - 1]][i - 1]), maxc[dq][i - 1] - minc[d[dq][i - 1]][i - 1]);
        maxu[dq][i] = max(max(maxu[dq][i - 1], maxu[d[dq][i - 1]][i - 1]), maxc[d[dq][i - 1]][i - 1] - minc[dq][i - 1]);
    }
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].to != fa[dq])
        {
            d[b[i].to][0] = fa[b[i].to] = dq;
            init(b[i].to, de + 1);
        }
    }
}
int lca(int x, int y)
{
//    int re = 0;
    int dqu = 0;
    int dqd = 0;
    int dqmax = 0;
    int dqmin = INF;
    int tmin = INF;
    int fmax = 0;
    if (deep[x] <= deep[y])
    {
        dqmin = mon[x];
        for (int i = lgn; i >= 0; i--)
        {
            if (deep[x] == deep[y])
                break;
            if (deep[x] <= deep[d[y][i]])
            {
                tmin = minc[y][i];
                dqd = max(dqd, maxd[y][i]);
                dqd = max(dqd, dqmax - tmin);
                dqmax = max(dqmax, maxc[y][i]);
                y = d[y][i];
            }
        }
    }
    else
    {
        dqmax = mon[y];
        for (int i = lgn; i >= 0; i--)
        {
            if (deep[x] == deep[y])
                break;
            if (deep[d[x][i]] >= deep[y])
            {
                fmax = maxc[x][i];
                dqu = max(dqu, maxu[x][i]);
                dqu = max(dqu, fmax - dqmin);
                dqmin = min(dqmin, minc[x][i]);
                x = d[x][i];
            }
        }
    }
    if (x == y)
    {
        return max(dqmax - dqmin, max(dqu, dqd));
    }
    for (int i = lgn; i >= 0; i--)
    {
        if (d[x][i] != d[y][i])
        {
            tmin = minc[y][i];
            fmax = maxc[x][i];
            dqu = max(dqu, maxu[x][i]);
            dqd = max(dqd, maxd[y][i]);
            dqu = max(dqu, fmax - dqmin);
            dqd = max(dqd, dqmax - tmin);
            dqmin = min(dqmin, minc[x][i]);
            dqmax = max(dqmax, maxc[y][i]);
            x = d[x][i], y = d[y][i];
        }
    }
    dqu = max(dqu, maxu[x][0]);
    dqd = max(dqd, maxd[y][0]);
    dqmax = max(dqmax, maxc[y][0]);
    dqmin = min(dqmin, minc[x][0]);
    return max(dqmax - dqmin, max(dqd, dqu));
}

/*
10
5 3 2 1 6 5 4 6 0 8 
1 9
1 10
10 7
10 3
1 8
7 6
9 2
2 5
5 4
10
7 5
*/

/*
10
2 1 5 2 5 5 3 9 5 8 
1 2
2 9
9 4
9 3
4 7
3 8
1 6
7 10
10 5
1
8 10
*/

调到怀疑人生的链剖…


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define MAXQ (100000 + 5)
#define INF (0x7ffffff)
#define LL long long
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(a) ((a) << 1)
#define RS(a) (((a) << 1) | 1)
using namespace std;
const int root = 1;
struct edg
{
    int from;
    int to;
    int next;
} tb[MAXN << 1];
int cntb;
int g[MAXN];

struct tnode
{
    int wei;
    int deep;
    int fa;
    int top;
    int hs;
    int sum;
    int start;
    int end;
} ta[MAXN];

struct node
{
    int le;
    int ri;
    int maxz; // 一条重链内的最大值
    int minz; // 一条重链内的最小值
    int maxu; // 链内 从下面节点到上面节点的最大值
    int maxd; // 链内 从上面节点到下面节点的最大值
} b[MAXN << 2];

int n;
int a[MAXN];
int cnts;

inline void push_up(int); //
void js(int, int, int); //
void xg(int, int, int); //
node cxmaxd(int, int, int); // 查询链内的    最大向下收益
node cxmaxu(int, int, int); //                 最大向上收益
int cxmaxz(int, int, int); //                 最大价钱
int cxminz(int, int, int); //                最小价钱
inline int solve(int, int);
void init(int, int);
void dfs(int);
inline void adn(int, int); //
inline void read(int&);
int main()
{
//    scanf("%d", &n);
    read(n);
    for (int i = 1; i <= n; i++)
    {
//        scanf("%d", &ta[i].wei);
        read(ta[i].wei);
    }
    int sre, srx, sry;
    for (int i = 1; i < n; i++)
    {
//        scanf("%d%d", &srx, &sry);
        read(srx), read(sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    ta[root].fa = root;
    ta[root].top = root;
    init(root, 1);
    dfs(root);
    js(1, 1, n);
    int q;
//    scanf("%d", &q);
    read(q);
    for (int i = 1; i <= q; i++)
    {
//        scanf("%d%d%d", &sre, &srx, &sry);
        read(sre), read(srx), read(sry);
        if (!sre)
        {
            xg(1, ta[srx].start, sry);
        }
        else
        {
            printf("%d\n", solve(srx, sry));
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
inline void adn(int from, int to)
{
    tb[++cntb].next = g[from];
    tb[cntb].from = from;
    tb[cntb].to = to;
    g[from] = cntb;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le;
    b[dq].ri = ri;
    if (le == ri)
    {
        b[dq].maxz = b[dq].minz = a[le];
        b[dq].maxu = b[dq].maxd = 0;
    }
    else
    {
        int mi = (le + ri) >> 1;
        js(LS(dq), le, mi);
        js(RS(dq), mi + 1, ri);
        push_up(dq);
    }
}
int cxmaxz(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq].maxz;
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
        {
            return cxmaxz(RS(dq), le, ri);
        }
        else if (ri <= mi)
        {
            return cxmaxz(LS(dq), le, ri);
        }
        else
        {
            return max(cxmaxz(LS(dq), le, mi), cxmaxz(RS(dq), mi + 1, ri));
        }
    }
}
int cxminz(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq].minz;
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
        {
            return cxminz(RS(dq), le, ri);
        }
        else if (ri <= mi)
        {
            return cxminz(LS(dq), le, ri);
        }
        else
        {
            return min(cxminz(LS(dq), le, mi), cxminz(RS(dq), mi + 1, ri));
        }
    }
}
node cxmaxu(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq];
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        node re;
        if (le > mi)
        {
            re =  cxmaxu(RS(dq), le, ri);
        }
        else if (ri <= mi)
        {
            re = cxmaxu(LS(dq), le, ri);
        }
        else
        {
            node lr = cxmaxu(LS(dq), le, mi);
            node rr = cxmaxu(RS(dq), mi + 1, ri);
            re.maxu = max(max(lr.maxu, rr.maxu), lr.maxz - rr.minz);
            re.maxz = max(lr.maxz, rr.maxz);
            re.minz = min(lr.minz, rr.minz);
//            cxmaxz(LS(dq), le, mi) - cxminz(RS(dq), mi + 1, ri);
        }
        return re;
    }
}
node cxmaxd(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq];
    }
    else
    {
        node re;
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (le > mi)
        {
            re = cxmaxd(RS(dq), le, ri);
        }
        else if (ri <= mi)
        {
            re = cxmaxd(LS(dq), le, ri);
        }
        else
        {
            node lr = cxmaxd(LS(dq), le, mi);
            node rr = cxmaxd(RS(dq), mi + 1, ri);
            re.maxd = max(max(lr.maxd, rr.maxd), rr.maxz - lr.minz);
            re.maxz = max(lr.maxz, rr.maxz);
            re.minz = min(lr.minz, rr.minz);
//            return max(max(cxmaxd(LS(dq), le, mi), cxmaxd(RS(dq), mi + 1, ri)), cxmaxz(RS(dq), mi + 1, ri) - cxminz(LS(dq), le, mi));
        }
        return re;
    }
}
void xg(int dq, int wz, int zh)
{
    if (b[dq].le == b[dq].ri)
    {
        if (b[dq].le == wz)
        {
            b[dq].maxz = b[dq].minz = zh;
        }
    }
    else
    {
        int mi = (b[dq].le + b[dq].ri) >> 1;
        if (wz > mi)
        {
            xg(RS(dq), wz, zh);
        }
        else if (wz <= mi)
        {
            xg(LS(dq), wz, zh);
        }
        push_up(dq);
    }
}
inline void push_up(int dq)
{
    int mi = (b[dq].le + b[dq].ri) >> 1;
    int le = b[dq].le, ri = b[dq].ri;
    b[dq].maxz = max(b[LS(dq)].maxz, b[RS(dq)].maxz);
    b[dq].minz = min(b[LS(dq)].minz, b[RS(dq)].minz);
    b[dq].maxd = max(max(max(b[LS(dq)].maxd, b[RS(dq)].maxd), b[RS(dq)].maxz - b[LS(dq)].minz), b[RS(dq)].maxz - b[LS(dq)].minz);
    b[dq].maxu = max(max(max(b[LS(dq)].maxu, b[RS(dq)].maxu), b[LS(dq)].maxz - b[RS(dq)].minz), b[LS(dq)].maxz - b[RS(dq)].minz);
}

/*
struct tnode
{
    int wei; ok in main
    int deep; ok in init
    int fa; ok in init
    int top;
    int hs; ok in init
    int sum; ok in init
    int start;
    int end;
}ta[MAXN];
*/

void init(int dq, int de)
{
    ta[dq].deep = de;
    ta[dq].sum = 1;
    int maxs = 0;
    int hs = 0;
    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, de + 1);
            ta[dq].sum += ta[tb[i].to].sum;
            if (ta[tb[i].to].sum > maxs)
            {
                maxs = ta[tb[i].to].sum;
                hs = tb[i].to;
            }
        }
    }
    ta[dq].hs = hs;
}

/*
struct tnode
{
    int wei; ok in main
    int deep; ok in init
    int fa; ok in init
    int top;
    int hs; ok in init
    int sum; ok in init
    int start;
    int end;
}ta[MAXN];
*/


void dfs(int dq)
{
    ta[dq].start = ++cnts;
    a[cnts] = ta[dq].wei;
    if (ta[dq].hs)
    {
        ta[ta[dq].hs].top = ta[dq].top;
        dfs(ta[dq].hs);
    }
    for (int i = g[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 = cnts;
}

inline int solve(int fr, int to)
{ 
    node zz;
    int re = 0;
    int dqd = 0;
    int dqu = 0;
    int fmax = 0;
    int tmax = 0;
    int fmin = cxminz(1, ta[fr].start, ta[fr].start);
    int tmin = cxminz(1, ta[to].start, ta[to].start);
    while (ta[fr].top != ta[to].top)
    {
        if (ta[ta[fr].top].deep > ta[ta[to].top].deep)
        {
            zz = cxmaxu(1, ta[ta[fr].top].start, ta[fr].start);
            dqu = max(dqu, zz.maxu);
            fmax = zz.maxz;
            dqu = max(dqu, fmax - fmin);
            fmin = min(fmin, zz.minz);
            fr = ta[ta[fr].top].fa;
        }
        else
        {
            zz = cxmaxd(1, ta[ta[to].top].start, ta[to].start);
            dqd = max(dqd, zz.maxd);
            tmin = zz.minz;
            dqd = max(dqd, tmax - tmin);
            tmax = max(tmax, zz.maxz);
            to = ta[ta[to].top].fa;
        }
    }
    if (ta[fr].deep > ta[to].deep)
    {
        zz = cxmaxu(1, ta[to].start, ta[fr].start);
        dqu = max(dqu, zz.maxu);
        fmax = zz.maxz;
        dqu = max(dqu, fmax - fmin);
        fmin = min(fmin, zz.minz);
    }
    else
    {
        zz = cxmaxd(1, ta[fr].start, ta[to].start);
        dqd = max(dqd, zz.maxd);
        tmin = zz.minz;
        dqd = max(dqd, tmax - tmin);
        tmax = max(tmax, zz.maxz);
    }
    re = max(max(dqd, dqu), tmax - fmin);
    return re;
}

inline void read(int& re)
{
    re = 0;
    bool f = false;
    char x = 0;
    while (x > '9' || x < '0')
    {
        x = getchar();
        if (!(x ^ '-'))
        {
            f = true;
            x = getchar();
        }
    }
    while (x <= '9' && x >= '0')
    {
        re = (re << 1) + (re << 3) + (x - '0');
        x = getchar();
    }
    re = (f) ? (-re) : (re);
}

/*
4
16 5 1 15
1 2
1 3
2 4
3
1 3 4
0 3 17
1 4 3
*/

By 工作重心转移 弃坑 的 Cansult