文章目錄

• 引
• 整體二分
• 幾道模板題
• • Dynamic Rankings
  • [ZJOI2013]K大數(shù)查詢
  • [國(guó)家集訓(xùn)隊(duì)]矩陣乘法
  • [THUPC2017] 天天愛(ài)射擊
  • [CTSC2018]混合果汁

引

例1. 給定 $n$ 個(gè)數(shù) $a_i$，一次詢問(wèn)，詢問(wèn)區(qū)間 $[l,r]$ 中的第 $k$ 小數(shù)。

我們通常想到二分答案，然后計(jì)數(shù)在 $[l,r]$ 區(qū)間內(nèi) $\le x$ 的數(shù)的個(gè)數(shù)，再與 $k$ 比較。

時(shí)間復(fù)雜度 $O(n\log n)$。（盡管這并不是最優(yōu)秀的做法）

例2. 給定 $n$ 個(gè)數(shù) $a_i$，多次詢問(wèn)，詢問(wèn)區(qū)間 $[1,n]$ 中的第 $k$ 小數(shù)。

由于區(qū)間是整個(gè)數(shù)列，所以我們直接排序一下，然后找第 $k$ 個(gè)數(shù)即可，時(shí)間復(fù)雜度 $O(n\log n)$。

例3. 給定 $n$ 個(gè)數(shù) $a_i$，多次詢問(wèn)，詢問(wèn)區(qū)間 $[l,r]$ 中的第 $k$ 小數(shù)。

這是一道主席樹(shù)，即可持久化線段樹(shù)的模板題。建立權(quán)值線段樹(shù)然后 $r$ 版本 $?l$ 版本，線段樹(shù)上二分。

實(shí)際上，我們?nèi)匀豢梢杂枚肿觥?/p>

但如果對(duì)于每一個(gè)詢問(wèn)都二分一次，那么時(shí)間復(fù)雜度 $O(qn\log n)$ 就爆炸了。

是否可以只用一次二分呢？——答案是顯然的。

我們理想的一次二分應(yīng)該是二分一個(gè)答案 $x$，然后利用一個(gè)數(shù)據(jù)結(jié)構(gòu)快速判斷答案和每一個(gè)詢問(wèn)的大小關(guān)系，再將詢問(wèn)分成 $\le x,>x$ 的兩部分，分別二分下去。

不難發(fā)現(xiàn)，這種假想的時(shí)間復(fù)雜度大概是帶兩個(gè) $log$ 的。

例4. 給定 $n$ 個(gè)數(shù) $a_i$，多次詢問(wèn)和修改某個(gè)位置的值，詢問(wèn)區(qū)間 $[l,r]$ 中的第 $k$ 小數(shù)。

線段樹(shù)分治？？不清楚。但這仍可以二分做。

整體二分

“引”中最后假想出來(lái)的思路就是 整體二分 。

能用整體二分解決的題目需要滿足以下性質(zhì)：

• 答案具有可二分性。
• 修改對(duì)判斷答案的貢獻(xiàn)相互獨(dú)立，即修改之間互不影響。
• 修改如果有貢獻(xiàn)，則是確定的貢獻(xiàn)，不會(huì)隨二分的答案產(chǎn)生變化。
• 貢獻(xiàn)滿足交換律，結(jié)合律，具有廣義的可加性。
• 離線。

總體算法思路：

• 記 $[l,r]$ 為二分答案的值域，$[ql,qr]$ 為定義域，即只考慮編號(hào)在 $[ql,qr]$ 中的修改和詢問(wèn)操作，這其中的詢問(wèn)的答案在 $[l,r]$ 內(nèi)。
• 首先把所有操作按 時(shí)間順序 存入數(shù)組。通常輸入順序即為操作的時(shí)間順序。然后開(kāi)始分治。
• 在每一層的分治中，利用數(shù)據(jù)結(jié)構(gòu)（常見(jiàn)為樹(shù)狀數(shù)組/線段樹(shù)）統(tǒng)計(jì)當(dāng)前查詢的答案和 $\text{mid}$ 的關(guān)系。
• 根據(jù)查詢的答案和 $\text{mid}$ 之間的關(guān)系，分成 $L,R$ 兩份，分別遞歸。
• 類(lèi)比線段樹(shù)分治，每一個(gè)分治的子問(wèn)題都是互不相關(guān)的，但卻共用同一個(gè)數(shù)據(jù)結(jié)構(gòu)。所以這里還要涉及到回退問(wèn)題。
• 當(dāng) $l=r$ 時(shí)，$[ql,qr]$ 中的所有詢問(wèn)答案即為 $l$。

---

下面以主席樹(shù)的模板題作為例題，具體闡釋算法實(shí)現(xiàn)以及時(shí)間復(fù)雜度的計(jì)算。

• 將輸入 $a_i$ 的操作定義為類(lèi)型 $1$，即 $q[i].op=1$。并記錄下 $q[i]$ 修改的位置 $i$，修改的值 $a_i$。

• 將查詢 $[l,r],k$ 的操作定義為類(lèi)型 $2$。并記錄下詢問(wèn)的區(qū)間，$k$ 。

• 對(duì)于一個(gè)形如 $(l,r,ql,qr)$ 的子問(wèn)題，二分答案為 $mid=l+r>>1$。

• 然后處理 $[ql,qr]$ 范圍內(nèi)的類(lèi)型 $1$ 操作。

  • 修改的值 $\le mid$ 的。

    全都扔到數(shù)據(jù)結(jié)構(gòu)上。（這里使用的是樹(shù)狀數(shù)組）

    則樹(shù)狀數(shù)組上放的是 $\le mid$ 的且在 $[ql,qr]$ 操作區(qū)間內(nèi)的修改操作。

    再放入 $L$ 數(shù)組中。

  • 修改的值 $>mid$ 的。

    這種修改對(duì)于 $mid$ 答案沒(méi)有貢獻(xiàn)，直接放進(jìn) $R$ 數(shù)組中。

• 對(duì)于 $[ql,qr]$ 范圍中的類(lèi)型 $2$ 操作。直接詢問(wèn)樹(shù)狀數(shù)組中 $[q[i].l,q[i].r]$ 區(qū)間內(nèi)的個(gè)數(shù) $cnt$。

  • 如果 $cnt\le q[i].k$。

    也就是說(shuō) $[q[i].l,q[i].r]$ 中 $\le mid$ 的數(shù) $\le k$ 個(gè)。答案要么是 $mid$ 要么 $<mid$。

    根據(jù)二分原則，我們把這個(gè)詢問(wèn)放到 $L$ 數(shù)組中。

  • 如果 $cnt>q[i].k$。

    類(lèi)比線段樹(shù)二分，我們將 $q[i].k$ 減去 $cnt$。然后放到 $R$ 數(shù)組中。

    因?yàn)榈綍r(shí)候處理 $(mid+1,r,q{l}^{\prime },q{r}^{\prime })$ 的子問(wèn)題時(shí)，原本 $[q[i].l,q[i].r]$ 中 $\le mid$ 的數(shù)時(shí)一定會(huì)提供 $1$ 的個(gè)數(shù)，我們沒(méi)有必要每次都加入。

• 將數(shù)據(jù)結(jié)構(gòu)回退至當(dāng)前層未操作前的模樣。

• 此時(shí)的 $L$ 數(shù)組放的詢問(wèn)是真正 $ans\le mid$ 的詢問(wèn)，放的修改是重新計(jì)算時(shí)還可能被掛到樹(shù)狀數(shù)組上去的修改。

  $R$ 數(shù)組同理。我們已經(jīng)去掉了 $L$ 數(shù)組中所有修改對(duì) $R$ 中詢問(wèn)產(chǎn)生的貢獻(xiàn)。

  現(xiàn)在兩個(gè)數(shù)組之間的信息是完全不會(huì)有交的了。

  所以分治處理 $(l,mid,L),(mid+1,r,R)$。

#include <bits/stdc++.h> using namespace std; #define maxn 400005 #define inf 0x7f7f7f7f int n, m; int ans[maxn]; struct node { int op, l, r, k, id; }q[maxn], Left[maxn], Right[maxn];namespace BIT {int t[maxn];void add( int i, int x ) { for( ;i <= n;i += i & -i ) t[i] += x; }int ask( int i ) { int cnt = 0; for( ;i;i -= i & -i ) cnt += t[i]; return cnt; } }void solve( int l, int r, int ql, int qr ) {if( ql > qr ) return;if( l == r ) { for( int i = ql;i <= qr;i ++ ) if( q[i].op == 2 ) ans[q[i].id] = l;return;}int mid = l + r >> 1, cntL = 0, cntR = 0;for( int i = ql;i <= qr;i ++ )if( q[i].op == 1 ) {if( q[i].k > mid ) Right[++ cntR] = q[i];else BIT :: add( q[i].id, 1 ), Left[++ cntL] = q[i];}else {int cnt = BIT :: ask( q[i].r ) - BIT :: ask( q[i].l - 1 );if( q[i].k <= cnt ) Left[++ cntL] = q[i];else q[i].k -= cnt, Right[++ cntR] = q[i];}for( int i = 1;i <= cntL;i ++ ) if( Left[i].op == 1 ) BIT :: add( Left[i].id, -1 );for( int i = 1;i <= cntL;i ++ ) q[i + ql - 1] = Left[i];for( int i = 1;i <= cntR;i ++ ) q[i + ql + cntL - 1] = Right[i];solve( l, mid, ql, ql + cntL - 1 );solve( mid + 1, r, ql + cntL, qr ); }int main() {scanf( "%d %d", &n, &m );for( int i = 1, x;i <= n;i ++ ) {scanf( "%d", &x );q[i] = (node){ 1, -inf, inf, x, i };}for( int i = 1, l, r, k;i <= m;i ++ ) {scanf( "%d %d %d", &l, &r, &k );q[i + n] = (node){ 2, l, r, k, i };}solve( -inf, inf, 1, n + m );for( int i = 1;i <= m;i ++ ) printf( "%d\n", ans[i] );return 0; }

最后來(lái)分析一下這個(gè)時(shí)間復(fù)雜度：

• 首先是二分的答案值，$O(\log V)$ 的。
• 對(duì)于同一層的分治，總共的區(qū)間定義域是 $O(n)$。類(lèi)比線段樹(shù) $1,2,4$ 的劃分，但同一層的總和仍是 $n$。
• 每個(gè)數(shù)在同一層的若干個(gè)分治中最多只會(huì)被掛在數(shù)據(jù)結(jié)構(gòu)上一次，然后撤銷(xiāo)。
• 時(shí)間復(fù)雜度應(yīng)為 $O(n\log n\log V)$。

幾道模板題

Dynamic Rankings

Dynamic Rankings

本題才是真的修改操作，即“引”中的例4 。

其實(shí)也沒(méi)有什么特別的，可以類(lèi)比線段樹(shù)分治，一個(gè)數(shù)存在時(shí)間是一段連續(xù)的區(qū)間。

具體見(jiàn)代碼即可明白。

#include <bits/stdc++.h> using namespace std; #define maxn 400005 struct node { int op, x, y, k, id; }q[maxn], L[maxn], R[maxn]; int n, m; int ans[maxn], a[maxn];namespace BIT {int t[maxn];void add( int i, int x ) { for( ;i <= n;i += i & -i ) t[i] += x; }int ask( int i ) { int cnt = 0; for( ;i;i -= i & -i ) cnt += t[i]; return cnt; } }void solve( int l, int r, int ql, int qr ) {if( ql > qr ) return;if( l == r ) { for( int i = ql;i <= qr;i ++ ) if( q[i].op == 2 ) ans[q[i].id] = l; return; }int mid = l + r >> 1;int cntl = 0, cntr = 0;for( int i = ql;i <= qr;i ++ )if( q[i].op == 2 ) {int cnt = BIT :: ask( q[i].y ) - BIT :: ask( q[i].x - 1 );if( q[i].k <= cnt ) L[++ cntl] = q[i];else q[i].k -= cnt, R[++ cntr] = q[i];}else {if( q[i].x <= mid ) BIT :: add( q[i].k, q[i].y ), L[++ cntl] = q[i];else R[++ cntr] = q[i];}for( int i = ql;i <= qr;i ++ )if( q[i].op == 1 and q[i].x <= mid )BIT :: add( q[i].k, -q[i].y );for( int i = 1;i <= cntl;i ++ ) q[i + ql - 1] = L[i];for( int i = 1;i <= cntr;i ++ ) q[i + ql + cntl - 1] = R[i];solve( l, mid, ql, ql + cntl - 1 );solve( mid + 1, r, ql + cntl, qr ); }int main() {int cnt = 0, Max = 0;scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) {scanf( "%d", &a[i] );q[++ cnt] = (node){ 1, a[i], 1, i, cnt };Max = max( Max, a[i] );}char op[10]; int x, y, k;for( int i = 1;i <= m;i ++ ) {scanf( "%s", op );if( op[0] == 'Q' ) {scanf( "%d %d %d", &x, &y, &k );q[++ cnt] = (node) { 2, x, y, k, cnt };}else {scanf( "%d %d", &x, &y );q[++ cnt] = (node){ 1, a[x], -1, x, cnt };a[x] = y;q[++ cnt] = (node){ 1, a[x], 1, x, cnt };Max = max( Max, y );}}solve( 0, Max, 1, cnt );sort( q + 1, q + cnt + 1, []( node x, node y ) { return x.id < y.id; } );for( int i = 1;i <= cnt;i ++ )if( q[i].op == 2 ) printf( "%d\n", ans[q[i].id] );return 0; }

[ZJOI2013]K大數(shù)查詢

[ZJOI2013]K大數(shù)查詢

注意這里是 $k$ 大數(shù)，不是 $k$ 小數(shù)。

那么二分答案時(shí)候，把 $>mid$ 的掛上去即可。

或者你整體取相反數(shù)后做 $k$ 小數(shù)，最后輸出答案再取反回來(lái)也行。

#include <bits/stdc++.h> using namespace std; #define maxn 50005 #define int long long struct node { int op, x, y, k, id; }q[maxn], L[maxn], R[maxn]; int n, m; int ans[maxn];namespace SGT {struct node { int cnt, tag; }t[maxn << 2];#define lson now << 1#define rson now << 1 | 1#define mid (l + r >> 1)void pushdown( int now, int l, int r ) {if( ! t[now].tag ) return;t[lson].tag += t[now].tag;t[lson].cnt += t[now].tag * (mid - l + 1);t[rson].tag += t[now].tag;t[rson].cnt += t[now].tag * (r - mid);t[now].tag = 0;}void modify( int now, int l, int r, int L, int R, int x ) {if( R < l or r < L ) return;if( L <= l and r <= R ) { t[now].tag += x; t[now].cnt += x * (r - l + 1); return; }pushdown( now, l, r );modify( lson, l, mid, L, R, x );modify( rson, mid + 1, r, L, R, x );t[now].cnt = t[lson].cnt + t[rson].cnt;}int query( int now, int l, int r, int L, int R ) {if( R < l or r < L ) return 0;if( L <= l and r <= R ) return t[now].cnt;pushdown( now, l, r );return query( lson, l, mid, L, R ) + query( rson, mid + 1, r, L, R );}#undef lson#undef rson#undef mid }void solve( int l, int r, int ql, int qr ) {if( ql > qr ) return;if( l == r ) { for( int i = ql;i <= qr;i ++ ) ans[q[i].id] = l; return; }int mid = l + r >> 1;int cntl = 0, cntr = 0;for( int i = ql;i <= qr;i ++ )if( q[i].op == 1 ) {if( q[i].k > mid ) SGT :: modify( 1, 1, n, q[i].x, q[i].y, 1 ), R[++ cntr] = q[i];else L[++ cntl] = q[i];}else {int cnt = SGT :: query( 1, 1, n, q[i].x, q[i].y );if( q[i].k <= cnt ) R[++ cntr] = q[i];else q[i].k -= cnt, L[++ cntl] = q[i];}for( int i = 1;i <= cntr;i ++ )if( R[i].op == 1 )SGT :: modify( 1, 1, n, R[i].x, R[i].y, -1 );for( int i = 1;i <= cntl;i ++ ) q[ql + i - 1] = L[i];for( int i = 1;i <= cntr;i ++ ) q[ql + i + cntl - 1] = R[i];solve( mid + 1, r, ql + cntl, qr );solve( l, mid, ql, ql + cntl - 1 ); }signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1, op, x, y, k;i <= m;i ++ ) {scanf( "%lld %lld %lld %lld", &op, &x, &y, &k );q[i] = (node){ op, x, y, k, i };}solve( -n, n, 1, m );sort( q + 1, q + m + 1, []( node x, node y ) { return x.id < y.id; } );for( int i = 1;i <= m;i ++ ) if( q[i].op == 2 ) printf( "%lld\n", ans[q[i].id] );return 0; }

[國(guó)家集訓(xùn)隊(duì)]矩陣乘法

[國(guó)家集訓(xùn)隊(duì)]矩陣乘法

數(shù)據(jù)結(jié)構(gòu)用二維樹(shù)狀數(shù)組即可。

#include <bits/stdc++.h> using namespace std; #define maxn 505 #define maxm 400005 struct node { int op, l1, r1, l2, r2, k, id; }q[maxm], L[maxm], R[maxm]; int n, m; int ans[maxm];namespace BIT {int t[maxn][maxn];void add( int x, int y, int v ) {for( int i = x;i <= n;i += i & -i )for( int j = y;j <= n;j += j & -j )t[i][j] += v;}int ask( int x, int y ) {int cnt = 0;for( int i = x;i;i -= i & -i )for( int j = y;j;j -= j & -j )cnt += t[i][j];return cnt;} }void solve( int l, int r, int ql, int qr ) {if( qr < ql ) return;if( l == r ) { for( int i = ql;i <= qr;i ++ ) ans[q[i].id] = l; return; }int mid = l + r >> 1;int cntl = 0, cntr = 0;for( int i = ql;i <= qr;i ++ )if( q[i].op == 1 ) {if( q[i].k <= mid ) BIT :: add( q[i].l1, q[i].r1, 1 ), L[++ cntl] = q[i];else R[++ cntr] = q[i];}else {int cnt = BIT :: ask( q[i].l2, q[i].r2 ) - BIT :: ask( q[i].l1 - 1, q[i].r2 ) - BIT :: ask( q[i].l2, q[i].r1 - 1 ) + BIT :: ask( q[i].l1 - 1, q[i].r1 - 1 );if( q[i].k <= cnt ) L[++ cntl] = q[i];else q[i].k -= cnt, R[++ cntr] = q[i];}for( int i = 1;i <= cntl;i ++ ) if( L[i].op == 1 ) BIT :: add( L[i].l1, L[i].r1, -1 );for( int i = 1;i <= cntl;i ++ ) q[ql + i - 1] = L[i];for( int i = 1;i <= cntr;i ++ ) q[ql + cntl + i - 1] = R[i];solve( l, mid, ql, ql + cntl - 1 );solve( mid + 1, r, ql + cntl, qr ); }int main() {scanf( "%d %d", &n, &m );int cnt = 0;for( int i = 1;i <= n;i ++ )for( int j = 1, x;j <= n;j ++ ) {scanf( "%d", &x );q[++ cnt] = (node){ 1, i, j, i, j, x, cnt };}for( int i = 1, l1, r1, l2, r2, k;i <= m;i ++ ) {scanf( "%d %d %d %d %d", &l1, &r1, &l2, &r2, &k );q[++ cnt] = (node){ 2, l1, r1, l2, r2, k, cnt };}solve( 0, 1e9, 1, cnt );sort( q + 1, q + cnt + 1, []( node x, node y ) { return x.id < y.id; } );for( int i = 1;i <= cnt;i ++ ) if( q[i].op == 2 ) printf( "%d\n", ans[q[i].id] );return 0; }

[THUPC2017] 天天愛(ài)射擊

[THUPC2017] 天天愛(ài)射擊

直接從子彈入手并不好做，這里稍微繞個(gè)彎，當(dāng)我們知道所有木板最后一次被哪顆子彈射中，就能統(tǒng)計(jì)出每個(gè)子彈射穿的木板數(shù)。

所以應(yīng)當(dāng)以木板為因變量。考慮每次二分最后被射擊的子彈 $mid$，然后 $\text{check}$ 前 $mid$ 個(gè)子彈能否射穿該木板。

發(fā)現(xiàn)這個(gè)可以整體二分做。

這里的 $[l,r]$ 不再是權(quán)值，而是二分的子彈編號(hào)。

我們這里依然把子彈和木板放在同一個(gè)操作數(shù)組里面，子彈為類(lèi)型 $1$，木板為類(lèi)型 $2$。

注意兩種操作的時(shí)間順序安排，我們應(yīng)該是先把所有子彈打了過(guò)后，再檢查該木板被射中的次數(shù)是否達(dá)到承載值。

單點(diǎn)修改，區(qū)間查詢，樹(shù)狀數(shù)組可做。

如果次數(shù)到達(dá)承載值，證明可能在更早時(shí)刻就已經(jīng)被射穿，放入左邊，否則放入右邊，遞歸分治。

#include <bits/stdc++.h> using namespace std; #define maxn 400005 struct node { int op, x, y, k, id; }q[maxn], L[maxn], R[maxn]; int n, m; int ans[maxn];namespace BIT {int t[maxn];void add( int i, int x ) { for( ;i < maxn;i += i & -i ) t[i] += x; }int ask( int i ) { int cnt = 0; for( ;i;i -= i & -i ) cnt += t[i]; return cnt; } }void solve( int l, int r, int ql, int qr ) {if( ql > qr ) return;if( l == r ) { for( int i = ql;i <= qr;i ++ ) if( q[i].op == 2 ) ans[l] ++; return; }int mid = l + r >> 1;int cntl = 0, cntr = 0;for( int i = ql;i <= qr;i ++ )if( q[i].op == 1 ) {if( q[i].k <= mid ) BIT :: add( q[i].x, 1 ), L[++ cntl] = q[i];else R[++ cntr] = q[i];}else {int cnt = BIT :: ask( q[i].y ) - BIT :: ask( q[i].x - 1 );if( q[i].k <= cnt ) L[++ cntl] = q[i];else q[i].k -= cnt, R[++ cntr] = q[i];}for( int i = 1;i <= cntl;i ++ ) if( L[i].op == 1 ) BIT :: add( L[i].x, -1 );for( int i = 1;i <= cntl;i ++ ) q[ql + i - 1] = L[i];for( int i = 1;i <= cntr;i ++ ) q[ql + cntl + i - 1] = R[i];solve( l, mid, ql, ql + cntl - 1 );solve( mid + 1, r, ql + cntl, qr ); }int main() {scanf( "%d %d", &n, &m );for( int i = 1, x, y, k;i <= n;i ++ ) {scanf( "%d %d %d", &x, &y, &k );q[i + m] = (node){ 2, x, y, k, i + m };}for( int i = 1, x;i <= m;i ++ ) {scanf( "%d", &x );q[i] = (node){ 1, x, 0, i, i };}solve( 1, m + 1, 1, n + m );for( int i = 1;i <= m;i ++ ) printf( "%d\n", ans[i] );return 0; }

[CTSC2018]混合果汁

[CTSC2018]混合果汁

顯然我們可以整體二分最低的美味度 $mid$。

然后把所有美味度 $\ge mid$ 的果汁都放入數(shù)據(jù)結(jié)構(gòu)中。

但果汁有錢(qián)數(shù)和購(gòu)買(mǎi)上限。

在二分后有個(gè)顯然的貪心：越便宜的越先買(mǎi)。

我們可以用權(quán)值線段樹(shù)，以單價(jià)為下標(biāo)，然后記錄總個(gè)數(shù)和總支付錢(qián)數(shù)。

查詢時(shí)先看左區(qū)間，再看右區(qū)間。查詢買(mǎi)最便宜的 $l$ 個(gè)的錢(qián)數(shù)是否在小朋友承受范圍內(nèi)。

但這里我們發(fā)現(xiàn)，好像這里的貢獻(xiàn)提前去掉和前面幾個(gè)模板題目不太一樣。因?yàn)楫?dāng) $mid$ 移動(dòng)時(shí)可能會(huì)加入更便宜的果汁，所以我們不能在現(xiàn)在就把某些小朋友的錢(qián)數(shù)減去一部分。

那怎么辦？——我們直接不減，就只是把小朋友不斷分組即可。

每次撤銷(xiāo)就類(lèi)似莫隊(duì)，用一個(gè)指針移動(dòng)。仔細(xì)想想（可見(jiàn)下面代碼）每一種果汁最多上線段樹(shù)兩次。

總時(shí)間復(fù)雜度是可以保證的。

本題我將果汁和小朋友兩種操作分開(kāi)存的，可能更直白一點(diǎn)。

這里的順序不再是時(shí)間順序，而是果汁美味度大小的順序。

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 100005 struct juice { int d, p, l; }g[maxn]; struct child { int g, l, id; }q[maxn], L[maxn], R[maxn]; int n, m, now; int ans[maxn];namespace SGT {struct node { int cnt, sum; }t[maxn << 2];#define lson now << 1#define rson now << 1 | 1#define mid (l + r >> 1)void modify( int p, int x, int now = 1, int l = 1, int r = 1e5 ) {if( l == r ) { t[now].cnt += x; t[now].sum += x * p; return; }if( p <= mid ) modify( p, x, lson, l, mid );else modify( p, x, rson, mid + 1, r );t[now].cnt = t[lson].cnt + t[rson].cnt;t[now].sum = t[lson].sum + t[rson].sum;}int query( int x, int now = 1, int l = 1, int r = 1e5 ) {if( ! x ) return 0;if( l == r ) return l * x;if( x <= t[lson].cnt ) return query( x, lson, l, mid );else return t[lson].sum + query( x - t[lson].cnt, rson, mid + 1, r );}#undef lson#undef rson#undef mid }void solve( int l, int r, int ql, int qr ) {if( ql > qr ) return;if( l == r ) { for( int i = ql;i <= qr;i ++ ) ans[q[i].id] = g[l].d; return; }int mid = l + r >> 1;while( now < mid ) ++ now, SGT :: modify( g[now].p, g[now].l );while( mid < now ) SGT :: modify( g[now].p, -g[now].l ), now --;int cntl = 0, cntr = 0;for( int i = ql;i <= qr;i ++ ) {if( SGT :: t[1].cnt < q[i].l ) R[++ cntr] = q[i];else if( SGT :: query( q[i].l ) <= q[i].g ) L[++ cntl] = q[i];else R[++ cntr] = q[i];}for( int i = 1;i <= cntl;i ++ ) q[ql + i - 1] = L[i];for( int i = 1;i <= cntr;i ++ ) q[ql + cntl + i - 1] = R[i];solve( l, mid, ql, ql + cntl - 1 );solve( mid + 1, r, ql + cntl, qr ); }signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= n;i ++ ) scanf( "%lld %lld %lld", &g[i].d, &g[i].p, &g[i].l );for( int i = 1;i <= m;i ++ ) scanf( "%lld %lld", &q[i].g, &q[i].l ), q[i].id = i;sort( g + 1, g + n + 1, []( juice x, juice y ) { return x.d > y.d; } );g[++ n] = { -1, 0, (int)1e18 };solve( 1, n, 1, m );for( int i = 1;i <= m;i ++ ) printf( "%lld\n", ans[i] );return 0; }

總結(jié)

以上是生活随笔為你收集整理的【学习笔记】整体二分的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。