做了 # P3642 [APIO2016] 煙花表演 本來是想用 \(slope trick\) 來做的，結果一打開題解，發現還有可并堆的做法，這不巧了嗎，最近剛學，所以打算明天寫一發可并堆，然后一起總結了。

這是2025.5.27的后續，首先，先想吐槽的是，題解能不能寫清楚啊！我認為的是純可并堆，但是，其實是 \(slope trick\) ！ 然后用可并堆維護，求你了！下次寫清楚一點吧！這道題真的代碼很簡單，只是有點難推而已。

那么我們可以設計一個非常暴力的dp狀態就是dp(u,i)表示將u子樹中的所有葉子節點調整至距u的父親距離為j的最小代價

那么我們的轉移方程也是十分的平凡的,枚舉u和父親的邊到底變成了什么值然后進行取min操作

可以推出這樣的一個式子： latex不打了！

詳見這

我們發現我們處理的函數是一個類似于min卷積一樣的式子, 顯然快速的計算這個東西是沒什么可能的……

不過我們的f(u,x)這個函數相當的有特點，在接下來我們將會使用歸納法證明f(u,x)是一個關于x的分段函數并且在每段都是線性的

那么對于函數的min卷積這個運算，盡管一般情況下是沒有什么性質的，但是在這道題里我們有一個函數是絕對值函數，而另一個函數是一個簡單的分段函數

此時我們就有可能會有一些性質了

那么我們手動分情況大力討論一波……（想證明的人自己手丸去吧,推式子推了我一個下午）

會發現min卷積大概有這么幾個性質

1.一個斜率比-1大的直線卷積上斜率為-1的直線之后新函數截距為兩個函數的截距之和,斜率不變

2.一個常數函數和一個斜率為-1的直線卷積之后截距為兩個函數截距之和而斜率變為-1

3.對于一個下凸的分段函數并且每一段的斜率都大于1,和一個斜率為+1的直線卷積之后,這個函數將會變成一條斜率為1的直線

事實上剛才的結論只是一個感性理解,因為我們在卷積的時候遠不止這幾種情況

然后我們胡亂爆推一波結論之后可以得到這個式子,如果我們給f(u,x)這個函數添加一條父親邊的話我們函數會做這樣的變化，假設這個函數在[L,R]處取值為0

1.將函數在[1,L]的一段向上平移val個單位

2.將函數在[R,+∞]的一段向右平移val個單位并且斜率改為+1

3.將函數在[L,R]的一段向右平移val個單位

4.此時你發現中間空出了一段斜率為-1,val個單位高val個單位寬的線段,在中間插入一個線段就行了

合并相鄰的子樹就是將函數簡單的相加起來

那么我們采用這樣的方式來存儲一個函數f(u,x)

通過數學歸納法可以得到f(u,x)的最右端斜率等于1,而在插入父親之前函數的最左段斜率=u的兒子數目

我們現在通過存儲這個分段函數的每一個拐點的x坐標來表示這個函數

并且我們認為，從右向左,每經過一個拐點，函數的斜率-1

那么初始的時候我們需要存儲一個絕對值函數,這樣的話我們就用兩個在同一個位置的拐點來描述這個絕對值函數

這樣儲存函數有一個好處就是當我們把函數相加的時候只需要簡易的將兩個函數的拐點列表合并一下再將最右端斜率簡單相加就可以完成函數的合并工作了

那么我們現在已經可以完成函數相加的操作了,我們現在需要支持的操作就是將函數所有斜率為正的拐點全部彈出這個操作了(至于修改斜率什么的其實簡單的就是插入兩個拐點就行了)

那么我們發現其實這個操作就等價于彈出函數中x坐標前k大的拐點其中 k 為我們當前處理的點的孩子個數

那么這個操作很顯然就是刪除k次最大值

又發現我們之前將兩個函數相加的操作就是將兩個函數的拐點列表合并

所以我們寫一個可并的大根堆(或者直接使用pb_ds)就可以完成合并函數和插入一條邊的操作了

最后我們得到了根節點的函數,顯然 這 也就是所有邊的和,而最右段的斜率就是根節點的度數，我們還知道每經過一個點函數的斜率就會-1,因此根據這3點我們就可以反推出整個函數的表達式

然后就可以做了,提取一下這個分段函數斜率為0的那一段值就ok了

代碼如下

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 3e5 + 10;

int n, m, ans;
int fa[N], w[N], deg[N];
int val[N << 1], d[N << 1], rt[N], tot;
int lc[N << 1], rc[N << 1];

int create(int v)
{
    val[++tot] = v, d[tot] = 0;
    return tot;
}
int merge(int p, int q)
{
    if(p == 0 || q == 0) return p + q;
    if(val[p] < val[q]) swap(p, q);
    rc[p] = merge(rc[p], q);
    if(d[lc[p]] < d[rc[p]]) swap(lc[p], rc[p]);
    d[p] = d[rc[p]] + 1;
    return p;
}

void pop(int &p)
{
    p = merge(lc[p], rc[p]); 
}

signed main() 
{
    cin >> n >> m;
    for (int i = 2; i <= n + m; i++)
    {
        cin >> fa[i] >> w[i];
        ans += w[i];
        deg[fa[i]] ++ ;
    }
    for(int u = n + m ; u >= 2 ; u -- ) 
    {
        if(u <= n) while (deg[u]-- > 1) pop(rt[u]);
        int R = val[rt[u]];
        pop(rt[u]);
        int L = val[rt[u]];
        pop(rt[u]);
        rt[u] = merge(rt[u], merge(create(L + w[u]), create(R + w[u])));
        rt[fa[u]] = merge(rt[fa[u]], rt[u]);
    }
    while(deg[1] -- ) pop(rt[1]);
    while(rt[1])
    {
        ans -= val[rt[1]];
        pop(rt[1]);
    }
    cout << ans;
    return 0;
}

還做了 # CF1707E Replace,其實就是 \(\text{Chy}\) 上周模擬賽的T1啦，其實就是倍增，不過真的很難想到，剛剛看了一眼，還能交題解誒，明天水一發，總結也一起寫吧！

好說好說，這道 3500 真的不太難(至少代碼不太難，結論也不太難

這是一看就能看出來的倍增吧，我們只要維護 \([l, r]\) 被操作 \(2^k\) 后的區間就好了吧，但是，這區間也太多了吧！這可不行呀，那我們就得考慮考慮，該怎么把一個區間分成若干個區間，還能保證，操作之后合并起來是原區間的結果呢？

我們發現 \(f(l \cup r) = f(l) \cup f(r)\),那么如果我們想要維護 \(f(l,r)\)，其實只要維護 \(f(l, l+1),f(l+1, l+2) \dots f(r -1,r)\),然后 \(f(l,l + 1) \cup f(l + 1, l + 2) \dots \cup f(r - 1, r)\) 就是 \(f(l,r)\) 了，所以不用維護 \([l, r]\) 只要維護 \([i,i+1]\) 就可以啦，轉移就是先設 \([l, r] = f^{2^{k-1}}(i, i+1)\)求 $ \overset{r-1}{\underset{i=l}{\cup}}(i, i+1)$ 就可以了，查詢也是一樣的吧。那這個就用 \(st\) 表來維護就好了！

時間復雜度：\(O(n\log^2n + q\log_{}n)\)。

代碼不好看，但是還是放放：

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

const int N = 1e5 + 10;

int n, q;
pair<int, int> f[22][N][22];
int lg[N];

pair<int, int> query(int l, int r, int id)
{
    if(l >= r) return make_pair(n + 1, 0);
    int k = lg[r - l];
    return make_pair(min(f[id][l][k].x, f[id][r - (1 << k)][k].x), max(f[id][l][k].y, f[id][r - (1 << k)][k].y));
}

int query(int l, int r) 
{
    if(l == 1 && r == n) return 0;
    pair<int, int> ans = query(l, r, 20);
    int res = 0;
    if(ans.x != 1 || ans.y != n) return -1;
    for(int i = 19 ; i >= 0 ; i -- )
    {
        ans = query(l, r, i);
        if(ans.x != 1 || ans.y != n)
        {
            l = ans.x;
            r = ans.y;
            res += 1 << i;
        }
    }
    return res + 1;
}

int a[N];

void init()
{
    for(int j = 1 ; j < n ; j ++ ) f[0][j][0] = make_pair(min(a[j], a[j + 1]), max(a[j], a[j + 1]));
    for(int k = 1 ; k <= 20 ; k ++ )
        for(int j = 1 ; j + (1 << k) <= n ; j ++ ) 
            f[0][j][k].y = max(f[0][j][k - 1].y, f[0][j + (1 << k - 1)][k - 1].y), f[0][j][k].x = min(f[0][j][k - 1].x, f[0][j + (1 << k - 1)][k - 1].x);
    for(int i = 1 ; i <= 20 ; i ++ )
    {
        for(int j = 1 ; j < n ; j ++ ) f[i][j][0] = query(f[i - 1][j][0].x, f[i - 1][j][0].y, i - 1);
        for(int k = 1 ; k <= 20 ; k ++ )
            for(int j = 1 ; j + (1 << k) <= n ; j ++ ) 
                f[i][j][k].y = max(f[i][j][k - 1].y, f[i][j + (1 << k - 1)][k - 1].y), f[i][j][k].x = min(f[i][j][k - 1].x, f[i][j + (1 << k - 1)][k - 1].x);
    }
}

signed main()
{
    cin >> n >> q;
    for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    for(int i = 2 ; i <= n ; i ++ ) lg[i] = lg[i >> 1] + 1;
    init();
    while(q -- )
    {
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << endl;
    }
    return 0;
}