# DP優化
---
## Outlines
* 前綴和優化
* 單調隊列優化
* 矩陣快速冪優化
* Aliens優化
* 分治優化
* 斜率優化
---
## 前綴和優化
用來優化$dp_i =\sum_{l_i \leq j \leq r_i} w_j$這種轉移，$w_j$必須和$i$無關
----
### 例題
[CF-985E. Pencils and Boxes](https://codeforces.com/contest/985/problem/E)
有$N$支筆要放進盒子，每盒至少放$k$支，盒子數量不限，第$i$支長度$a_i$，同一個盒子裡最長和最短的筆相差不超過$d$，問能不能放完所有筆
$N \leq 5 \cdot 10^5$
----
縮短全距?先把長度排序後分割成一些區間
----
簡單的$O(N^2)$作法: $dp[i]$是一個bool，代表前$i$項能不能放完，轉移就枚舉最後一次取的數量
```cpp=
for (int j = 0; j < i; ++j)
if (i - j >= k && a[i] - a[j + 1] <= d)
dp[i] |= dp[j];
```
----
因為已經排序好了，所以轉移的範圍是一段區間
那要怎麼維護區間OR?
----
就用區間和就好了，把bool當成int處理，區間和$>0$代表有1，而區間和可以$O(1)$用前綴和的差得到
----
區間的右界是簡單的$i-k$，那左界怎麼求?
排好了當然能二分搜，總複雜度$O(NlogN)$
<!-- .element: class="fragment" data-fragment-index="1" -->
對於較大的$i$左界會遞增，所以可以雙指標 ~~，那其實區間和用雙指標就好了不用前綴和~~，但是因為sort，總複雜度還是$O(NlogN)$~~，所以砸資結就好了~~
<!-- .element: class="fragment" data-fragment-index="2" -->
----
### 更多例題
[CF-479E. Riding in a Lift](https://codeforces.com/contest/479/problem/E)
[CF-1188C. Array Beauty](https://codeforces.com/contest/1188/problem/C)
[CF-1225E. Rock Is Push](https://codeforces.com/contest/1225/problem/E)
---
## 單調隊列優化
----
### 經典題
[滑動窗口極值](https://zerojudge.tw/ShowProblem?problemid=a146)
給一個長度$N$的陣列和$K$，請對每個長度$K$的區間分別輸出最大值和最小值
$N \leq 10^6$
----
由左掃到右，維護一個deque，裡面存當前看的區間內所有可能成為之後看的區間的答案的位置，剩下的值都不用管。那哪些值是可能的呢?
----
以最大值為例，假設現在看到$[i,i+k)$，最大值是$a_j$(假設有多個找最右邊)，那$j$一定在裡面。
----
其他比$a_j$小的值怎樣才有機會成為答案?因為窗口滑太右邊後就取不到$a_j$了，所以$max_{j < t < i + k}a_t$也有機會(還不知道$i+k$後面長怎樣)，令他為$j_1$，為方便順便令$j_0=j$，還能繼續找出$j_2,j_3,...$，這些就是deque裡的數
----
觀察$j_0, j_1, ...$，會得到一些性質
* $j_0 < j_1 < ...$
* $a_{j_0} > a_{j_1} > ...$
* $\max\limits_{j_i < j' < j_{i+1}}a_j' \leq a_{j_{i+1}}$
因為有單調性，所以稱為單調隊列
----
那來看跑到$i+1$時會發生什麼事，首先，最前面的元素可能會超出窗口而"過期"，過期就直接pop掉。中間這些數字暫時不變。後面會有新掃到的元素要加進來，注意到他是最晚過期的，所以不管再小都有機會，因為還沒掃到的那些可能更小。
----
但是新元素不能直接push，因為多得到一些資訊後，先前有機會的可能就失敗了。如果deque中有一個$x$滿足$a_x \leq a_{i+k}$，那因為之後看的所有包含$x$的區間也包含$i+k$，所以$x$就沒機會了
----
前面提過這個deque有單調性，所以$\leq a_{i+k}$的是一段後綴，把這些元素全部pop掉之後才能塞$i+k$。顯然的，單調性依舊存在
----
此時$[i+1,i+k+1)$的極值會在哪呢?前面就提過了，最大值在最前面，直接取就好了
----
整個過程
1. pop前面過期的
2. pop後面太小的
3. push新的
4. 取front當答案
基本上單調隊列的步驟都是這樣
----
那來分析複雜度，push在每個位置進行一次，$O(N)$，那pop呢?
反正丟幾個進去最多就出來幾次，所以也是$O(N)$
<!-- .element: class="fragment" data-fragment-index="1" -->
----
### 例題
[CF-372C. Watching Fireworks is Fun](https://codeforces.com/contest/372/problem/C)
你在數線上$[1,N]$中看煙火，有$M$個煙火，第$i$個會在時間$t_i$位置$a_i$綻放，此時若你在$x$，會獲得$b_i-|a_i-x|$的開心度。你可以任選起始位置，之後每秒可以往左右移動最多$d$，不能超出$[1,N]$，問總開心度的最大值
$N \leq 150000, M \leq 300,$煙火照時間先後排
----
定義$dp[i][j]$代表在位置$j$看完煙火$i$時的最大開心度，轉移式
$dp[i][j] = \max\limits_{|k-j| \leq d \cdot (t_i - t_{i-1})}dp[i-1][k] + b_i - |a_i - j|$
----
會發現枚舉$k$時唯一影響DP值的只有前一次的DP值，所以轉移其實就是問一個區間最大值再另外加上只和$i,j$有關的東西
----
而且這個區間是單調向右跑的，所以可以用單調隊列線性算好一個時刻的所有位置，然後重複$M$次就做完了，複雜度$O(NM)$
----
注意記憶體可能會爆炸，但可以用滾動壓掉空間複雜度
----
### 經典題
**多重背包**
$N$種東西，重$w_i$、值$c_i$、共$m_i$個，裝進容量$W$的背包裡，求最大價值和
----
$O(NWlogW)$講過了，這邊講一個$O(NW)$的做法
----
這是暴力枚舉第$i$種取幾個的轉移式
$dp[i][j] = \max\limits_{0 \leq k \leq m_i}dp[i-1][j-w_i \cdot k] + c_i \cdot k$
----
這是同一條式子
$dp[i][j] = \max\limits_{j-w_i \cdot m_i \leq t \leq j, t \equiv j(mod\ w_i)} dp[i-1][t] + c_i \cdot \frac j{w_i} - c_i \cdot \frac t{w_i}$
盯著他看，假設把$t \equiv j(mod\ w_i)$拉出來會發生什麼事?
----
他變滑窗了
----
處理$i$這一層的時候，先把重量依照$mod\ w_i$分類，轉移只會在同一類中發生，而且單看一類的話會是滑動窗口極值，所以可以$O(\frac W{w_i} \cdot w_i)$做完，乘上枚舉物品，複雜度$O(NW)$
----
### 更多例題
[CF-940E. Cashback](https://codeforces.com/contest/940/problem/E)
[CF-1237D. Balanced Playlist](https://codeforces.com/contest/1237/problem/D)
---
## 矩陣快速冪優化
當你的DP維度連線性都會爆的時候用的，要滿足轉移是線性的，而且轉移的範圍不大
----
### 例題
[CSA-Partial Ladder Graph](https://csacademy.com/contest/archive/task/partial_ladder_graph/)
給$N$，問這張圖有多少種邊集刪掉後保持連通
$N \leq 10^{18}$
----
先想DP，由左而右做到$(i,n+i)$時，有兩種情況，一種是前面連通，一種是有兩塊，$i,n+i$不同塊，晚點再把他們連起來
----
新增的邊只有三條，狀態從兩種轉移到兩種，這麼少動手畫一畫就好了
$dp[i][0] = dp[i-1][0] + dp[i-1][1] \cdot 2$
$dp[i][1] = dp[i-1][0] + dp[i-1][1] \cdot 4$
----
但是線性跑到$10^{18}$會爆炸，考慮把轉移寫成矩陣
$\begin{equation}\begin{bmatrix}dp[i][0]\\dp[i][1]\end{bmatrix} = \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}\begin{bmatrix}dp[i-1][0]\\dp[i-1][1]\end{bmatrix}\end{equation}$
----
繼續寫
$\begin{equation}\begin{bmatrix}dp[i][0]\\dp[i][1]\end{bmatrix} = \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}\begin{bmatrix}dp[i-1][0]\\dp[i-1][1]\end{bmatrix} = \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^2\begin{bmatrix}dp[i-2][0]\\dp[i-2][1]\end{bmatrix}\end{equation}$
----
最後
$\begin{equation}\begin{bmatrix}dp[i][0]\\dp[i][1]\end{bmatrix} = \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^{i-1}\begin{bmatrix}dp[1][0]\\dp[1][1]\end{bmatrix}\end{equation}$
----
所以我們要求的東西變成這個矩陣的$N-1$次方。跟乘法快速冪一樣，矩陣也可以用快速冪，一種作法是求出該矩陣的$2^0, 2^1, ...$次方，然後根據$N-1$二進位中1出現的位置把對應的矩陣乘上去
----
$\begin{equation}\begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^{2^i} = \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^{2^{i-1}} \cdot \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^{2^{i-1}}\end{equation}$
$\begin{equation}\begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^{100101_2} = \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^{100000_2} \cdot \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^{100_2} \cdot \begin{bmatrix}1\ \ 2\\1\ \ 4\end{bmatrix}^{1_2}\end{equation}$
----
所以就進行$O(logN)$次矩陣乘法就好了，$m\times m$矩陣的矩陣乘法可以用簡單的三層迴圈得到，$O(m^3)$，所以這題的複雜度是$O(2^3logN)$
----
諸如以下形式的都可以用矩陣快速冪解決，通常矩陣維度要在100以內
$f(i) =a_1f(i-1)+a_2f(i-2)+...+a_kf(i-k)+bi+c$
$f(i)=a\cdot f(i-1)+b\cdot g(i-1), g(i)=c\cdot f(i-1)+d\cdot g(i-1)$
----
### 更多例題
[CF-1117D. Magic Gems](https://codeforces.com/contest/1117/problem/D)
[CSA-Bunny on Number Line](https://csacademy.com/contest/archive/task/bunny-on-number-line/)
---
## Aliens優化
也叫WQS二分搜，一種神奇的二分搜，通常題目長的像"在序列中找恰(至多)$k$個點，使得...最大(最小)"
----
### 例題
[2017全國賽-P6. AI-666 賺多少](https://tioj.ck.tp.edu.tw/problems/2039)
你要在$N$個時間點內買賣一個東西，他在第$i$個時間的價格是$a_i$(買賣一樣)，但你一次只能買一個，賣掉後才能再買，而且最多買賣$K$次，問最多能賺多少錢
$N \leq 2 \cdot 10^6$
----
官解是Greedy，但應該沒多少人用Greedy寫這題，而且我到現在還是不會
二維DP很直覺，但會爆
這題需要通靈
----
假設不管次數限制，很顯然的DP解是看現在在哪以及下一個動作是買或賣，然後算最大值。
----
我們可以在過程中順便DP最少要買賣幾次才有這個價值。假設很幸運次數沒爆，那可以直接輸出解了，但通常當然沒這麼幸運。
----
那我們要想個辦法逼他買賣少次一點。假設規定他每賣一次就要繳稅，次數是不是就會少一點了?
----
但是這樣要怎麼知道他原本賺的錢?
別忘了我們可以算次數，把繳稅後的獲利加上稅金乘以次數就好了
<!-- .element: class="fragment" data-fragment-index="1" -->
----
這邊還有一個很重要的觀察，因為繳稅只和次數有關，我們令$f(i)$代表原本買賣$i$次的最大獲利，$g(i)$代表繳稅時的，每次的稅金是$cost$，那下面的等式恆成立
$f(i)=g(i)+i \cdot cost$
----
也就是說，在固定次數時的策略是固定的，不受$cost$影響
----
那Aliens要怎麼利用這個$cost$?想像一下當$cost$很少時，是不是可以買很多次，但$cost$很多時，就會放棄交易
----
那就二分搜一下$cost$，當次數太多時就增加$cost$，太少時就減少$cost$，只要控制讓$k$次是最佳解，就可以用前面的等式反推我們要的答案了。這樣的總複雜度是$O(NlogC)$，會過
----
但其實還有很多問題，Aliens並沒有這麼方便
* 怎麼證明可以二分搜(有單調性)
* 這樣只算恰$k$次，如果少次一點其實更好呢?
* 一定找的到恰$k$次的$cost$嗎
----
接下來的部分我不會證明，可以自己感覺一下
----
假設把$(i, f(i))$畫在二維平面上，會是一個凹函數，也就是當次數遞增時，獲利會先增加後減少，且變化量($f(i)-f(i-1)$)遞減
----
不嚴謹理解，就是你一開始每多一次可能就會多出一次很好的買賣，但隨著次數用多了，好的用完，就只能多賺一點點，到最後甚至只剩虧本生意
----
總之如果是凹函數，就能重新理解一下二分搜在幹嘛了。其實我們就是在二分搜一個斜率，使得該斜率的直線和圖形切於$k,f(k)$
----
偷個WiwiHo的優質GIF，圖中藍色是$f(x)$，紅色是$g(x)$，金色是極值位置
----
假設我們已經理解Aliens的原理了，那來解決剩下的問題吧
* 這樣只算恰$k$次，如果少次一點其實更好呢?
* 一定找的到恰$k$次的$cost$嗎
----
少於$k$次比較好怎麼解決?觀察圖形應該會發現此時最好的就是少於$k$次，所以跟一開始說的一樣，不帶cost跑一遍就好了
----
**找不到恰$k$次怎麼辦?**
先想想什麼時候會發生
----
----
這樣搜到我們要的斜率時次數會太少(因為DP時Greedy最少次數)，但是斜率再大又太多次。怎麼辦?
----
再看仔細一點
----
這個次數下$g(x)$的極值跟$g(k)$一樣!所以答案就是$max(g(x)) + cost \cdot k$
----
那這題就這樣結束了，這邊講幾個細節:
* 二分搜的$l,r$要取到值域上下界，注意可能有負的，負數做`(a+b)/2`是向上取整，容易爛掉，建議`a+b>>1`
* 如果值域有浮點數，就要搜到浮點數
* 剛才說找不到極值在$k$時用小於的最大數$x$取代，記得此時$cost$要加$k$倍不是$x$倍
----
* 因為只是對斜率二分，所以凸函數也可以，注意二分搜方向
* 根據DP時Greedy最大或最小次數判斷找不到的時候取稍大還是稍小，不確定就都試試
* 通常是Aliens的題目都很容易看出來，也不會特別證明，就直接砸。但有些不是的可能會誤以為是，de到死都de不出來，建議生隨機測資驗或是想其他做法
----
### 例題
[CF-125E. MST Company](https://codeforces.com/contest/125/problem/E)
給一張圖，邊權都是正的，請找到權值和最小的邊集，恰包含k條1的臨邊，且能讓圖連通
----
顯然是MST
注意到那k條邊不會形成環，因此當選的子圖不是樹的時候一定能在環上找其他邊移除
----
恰k條邊?Aliens砸下去
----
讓每條1的臨邊邊權額外加上一個cost，二分搜cost，跑MST，使得有恰k條邊被選中。相同的，只需要在正整數上二分搜就好，如果找不到恰k條的cost，可能是這三種情況:
1. cost再大都取太多
2. cost再小都取太少
3. 某個cost會取太多，+1就變太少
----
**1. cost再大都取太多**
如果1的臨邊已經比其他邊都大，代表這些邊是讓圖連通必須取的，因此無解
----
**2. cost再小都取太少**
代表邊數根本不夠，無解，其實一開始就能判掉
----
**3. 某個cost會取太多，+1就變太少**
就是正常Aliens的case，取最接近的去算答案
----
### 更多例題
[CSA-Or Problem](https://csacademy.com/contest/archive/task/or-problem)
[TIOJ-1737 . [APIO '07] Backup](https://tioj.ck.tp.edu.tw/problems/1737)
[TIOJ-1341 . [IOI 2007, Day 1] Aliens](https://tioj.ck.tp.edu.tw/problems/1341)
---
## 分治優化
處理轉移點單調又有離線代價的問題，透過分治減少不必要的枚舉
----
現在對於一些$i$，想計算$max\ f(i, j)$，那得到最佳解時的那個$j$稱為轉移點，記作$g(i)=argmax_j\ f(i, j)$。假設滿足$\forall i, g(i) \leq g(i+1)$，就稱為轉移點單調。
----
假設我在計算$max\ f(i, j)$時，必須知道$max\ f(i-1,j)$才能算，那就稱代價在線，反之，我用任何順序都可以時，稱代價離線
----
另外，要快速檢查轉移點的單調性可以用**Monge condition**
> 給一個$n \times m$矩陣$B$，若$\forall 1 \leq i < n, 1 \leq j < m$都有
> $B[i][j] + B[i + 1][j + 1]$
> $\leq(\geq) B[i][j+1] + B[i+1][j]$
> ，則說他滿足convex(concave) Monge condition
----
> 若滿足convex(concave) Monge condition，則具有凸(凹)單調性
但是有單調性不一定滿足Monge condition
那分治優化到底是什麼?
<!-- .element: class="fragment" data-fragment-index="1" -->
----
### 例題
[CF-1601C. Optimal Insertion](https://codeforces.com/contest/1601/problem/C)
給你長度分別為$n,m$的陣列$a,b$，你要把$b$的元素都塞到$a$裡，其中$a$原本的元素的相對順序要固定，$b$可以亂插，求最後長度$n+m$的陣列最少有幾個逆序數對
$n,m \leq 10^6$
----
首先$a$的順序固定，可以先算裡面的逆序數對
----
$b$的順序可變，那先sort看看
----
那來考慮某個$b_i$塞進去時和$a$產生的逆序數對，假設他塞在$a_j,a_{j+1}$之間，那就數前面比他大+後面比他小就好了
----
不難猜到對$b_i$來說插的位置單調，這邊證一下。假設$b_i, b_{i+1}$分別插在$a_j,a_j'$前面最好(一樣好挑最左)，$j>j'$，設$a$中$[j',j)$有$l_1$個數$<b_i$、$l_2$個數$<b_{i+1}$、$r_1$個數$>b_i$、$r_2$個數$>b_{i+1}$，則有
$r_1 < l_1$
$l_2 \leq r_2$
$l_1 \leq l_2$
$r_2 \leq r_1$
顯然矛盾
----
接著可以發現讓每個$b_i$都挑最好的時，他們會照順序，所以在$b$的元素間的逆序數對是0，也就是這樣會是最好的
----
現在可以來解釋分治優化了。一開始，我們直接暴力看$b_\frac m2$要放哪，$O(N)$掃就好，假設是$a_x$旁邊
$\forall i < \frac m2, b_i$會放在$[a_1,a_x]$
<!-- .element: class="fragment" data-fragment-index="1" -->
$\forall i > \frac m2, b_i$會放在$[a_x,a_n]$
<!-- .element: class="fragment" data-fragment-index="1" -->
----
意思是，我們接下來如果遞迴處理$\frac m2$的兩邊，左邊暴力跑的時候只要枚舉一部分的轉移點就好，右邊只要枚舉另一部份的轉移點就好，所以大概有一半的枚舉在這邊被省略。當遞迴下去時，又會繼續省略$\frac 14,\frac 18, ...$，最後的複雜度只需要$O(NlogN)$就好
----
複雜度可以看這張圖理解
----
```cpp=
void dc(int l, int r, int _l, int _r) {
//處理[l,r), 轉移點[_l,_r)
if (l >= r)
return;
int m = l + r >> 1;
int best;//m的轉移點
//計算best
//...
dc(l, m, _l, best + 1);
dc(m + 1, r, best, _r);
}
```
----
這題要注意的是，當只考慮$[\_l,\_r)$的轉移點，暴力跑的時候就只會跑這邊，所以算出來的逆序數對數並不是全部的，所以利用分治優化找完全部的轉移點後，要再跑一次正常的逆序數對，這部分可以用分治或資結做到，總複雜度$O(NlogN)$
----
那如果遇到轉移點單調的問題，但是代價不能離線，要怎麼做?有個神奇的東西叫CDQ分治，總之就是分治的一種，可以花$log$的代價讓在線的東西變成一堆離線的問題，但這裡先不介紹。
----
### 更多例題
[CF-673E. Levels and Regions](https://codeforces.com/contest/673/problem/E)
[CF-321E. Ciel and Gondolas](https://codeforces.com/contest/321/problem/E)
[CF-868F. Yet Another Minimization Problem](https://codeforces.com/contest/868/problem/F)
---
## 斜率優化
處理轉移式是一堆斜直線的極值問題
----
斜率優化的轉移式通常長這樣
$dp_i = \max\limits_{j<i}(a_j \cdot x_i + b_i) + c_i$
可以想像把一堆$y=ax+b$丟到平面上，然後問$x=x_i$和他們最高的交點
----
一般的斜率優化需要比較複雜的資料結構或演算法來處理，所以這邊只會講簡單的特例—斜率和詢問單調的斜率優化
----
### 例題
[TIOJ-1745 . [APIO '10] Commando](https://tioj.ck.tp.edu.tw/problems/1745)
有$N$個士兵，第$i$個有戰鬥力$x_i$，你要把他們分割成一些連續區間。假設一個區間的戰鬥力總和是$x=x_L+x_{L+1}+...+x_R$，那戰鬥力定義為$ax^2+bx+c$。詢問所有區間的戰鬥力總和最大是多少
$N \leq 10^6, a < 0, x_i > 0$
----
先列DP式
$dp_i = max_{j<i}(dp_j+a \cdot x(i,j)^2+b \cdot x(i,j) + c)$
----
看起來非常麻煩，先把$x(i,j)$用前綴和表示並展開
$\begin{align}dp_i = max_{j<i}(&dp_j + a \cdot pre_i^2 - 2a \cdot pre_i \cdot pre_j \\ + &a \cdot pre_j^2+ b \cdot pre_i - b \cdot pre_j + c)\end{align}$
----
整理一下
$\begin{align}dp_i = &a \cdot pre_i^2 + b \cdot pre_i + c\\+ &max_{j<i}(-2a \cdot pre_j \cdot pre_i \\ + &dp_j + a \cdot pre_j^2 - b \cdot pre_j)\end{align}$
現在明顯是斜率優化了
<!-- .element: class="fragment" data-fragment-index="1" -->
----
前面提過斜率和詢問要單調，轉移式中斜率為$-2a \cdot pre_j$，因為$x_i>0$，$pre_j$是遞增的，而$-2a$是正的常數，符合單調。詢問是$pre_i$，也單調。
----
那要怎麼處理呢?既然是要求一些$x$的最大值，那只要維護所有直線的下凸包就好了
----
要怎麼表達一個下凸包?就按照順序紀錄每條凸包上的直線就好了
----
那先想想要怎麼查詢某個$x$的最大值
----
前面提過詢問單調，也就是說所有在$x$左邊的直線之後都沒用了，所以可以一直看前兩條線的交點是不是在$x$左邊，是的話就pop第一條，否則代表最左邊那條有包含$x$，因此直接查那條直線在$x$的值就好了
----
接下來是修改，也就是插入一條直線
----
插入的會是當前斜率最大的直線，他顯然會在下凸包最右邊，但是在插入前，要檢查會不會有直線被淘汰掉，也就是原本在凸包上的區間被新的直線覆蓋
----
可以發現被覆蓋的會是一段後綴
----
所以就一直檢查新的和倒數第二條的交點，如果最後一條在那裡輸了，那他的右半會被新直線覆蓋，所以要pop掉，否則代表剩下的線都還在凸包上，此時再把新的直線放入最後面
----
其實整個操作就是單調隊列，所以複雜度也一樣是$O(N)$
----
單調的題目較少，這邊就不放了。非單調的斜率優化經典做法是維護動態凸包，也可以用~~怪科技~~李超線段樹輕鬆寫掉，如果硬要的話，還可以套CDQ分治強制當成單調的做，有興趣自己搜尋
{"metaMigratedAt":"2023-06-16T18:55:17.366Z","metaMigratedFrom":"Content","title":"DP優化","breaks":true,"contributors":"[{\"id\":\"bc9b0353-6035-4ee1-b41d-067c386529fd\",\"add\":15511,\"del\":2716}]"}