切題 problem

• description
• solution
• code

description

在一個神秘的 JOSLFN 上，wzy 和 lqs2015 常年占據(jù)著切題榜的 rk1 和 rk2。現(xiàn)在他們在研究
如何快速造題并驗(yàn)題。
分工是這樣的：有 n 個 wzy 負(fù)責(zé)造題，第 i 個 wzy 會造出恰好 ai 道題。有 m 個 lqs2015 負(fù)責(zé)
驗(yàn)題，第 j 個 lqs2015 最多能驗(yàn) bj 道題。每個 wzy 需要把他造的每一道題都給一個 lqs2015 來驗(yàn)。
不過有一條限制，就是每個 wzy 的 ai 道題必須給不同的 lqs2015 ，否則這個 lqs2015 會因?yàn)轵?yàn)到了
來自同一個 wzy 的題而感到厭煩并且讓所有 wzy 和 lqs2015 都消失。
在一旁瑟瑟發(fā)抖的 superay 想要知道，是否存在一種符合限制的驗(yàn)題的分配方案。
隨著時間的推移，會有 q 次對 a, b 的修改。每次修改有如下四種：
? 1 i 表示將 ai 加 1。
? 2 i 表示將 ai 減 1。
? 3 j 表示將 bj 加 1。
? 4 j 表示將 bj 減 1。
superay 想知道每次修改之后還是否存在合法方案。

Input
第一行兩個正整數(shù) n, m。
第二行 n 個非負(fù)整數(shù) a1, a2, ···, an。
第三行 m 個非負(fù)整數(shù) b1, b2, ···, bm。
第四行一個正整數(shù) q。
接下來 q 行，每行是如下四種之一：
? 1 i (1 ≤i ≤n)
? 2 i (1 ≤i ≤n)
? 3 j (1 ≤j ≤m)
? 4 j (1 ≤j ≤m)
保證任意時刻 a, b 都非負(fù)。

Output
輸出 q 行，第 i 行表示在第 i 次操作之后的答案，有解輸出 1，無解輸出 0。

solution

subtask1: n,m,q<=50

這么小的數(shù)據(jù)，肯定是暴力基礎(chǔ)分，直接貪心做

貪心：造題數(shù)越多的人越先處理，驗(yàn)題數(shù)越多的人越先驗(yàn)

顯然，這是為了留下更多的驗(yàn)題人和越小需要不同驗(yàn)題人數(shù)的造題人

---

subtask2: n,m,q<=1000

當(dāng)時以為是什么$n^2\log n$的算法，整個數(shù)據(jù)結(jié)構(gòu)

沒想到原來是留給暴力網(wǎng)絡(luò)流的

這是個最大網(wǎng)絡(luò)流模板，如果告訴了是網(wǎng)絡(luò)流，建圖方式是顯然的

超級源點(diǎn)$S$，超級匯點(diǎn)$T$

造題人和$S$連邊，流量為$a_i$，驗(yàn)題人和$T$連邊，流量為$b_i$，然后每個造題人和每個驗(yàn)題人之間都有連邊，流量為$1$

肯定的，網(wǎng)絡(luò)流只有滿流了才表示有解，即最大流為${\sum }_{i=1}^n{a}_i$

最后就是暴力跑網(wǎng)絡(luò)流了

---

subtask3~4: n,m,q<=250000

$\text{subtask3}$可能是給正解寫爆了的人準(zhǔn)備的

通過$\text{subtask2}$，已經(jīng)知道是明顯的網(wǎng)絡(luò)流了，但是數(shù)據(jù)顯然不允許直接硬剛

顯然，剩下的工作就是尋找優(yōu)化

眾所周知，最大網(wǎng)絡(luò)流等于最小割

將$a_i$從大到小排序，滿流等價于$?k\in [0,n]$，有${\sum }_{i=1}^k{a}_i\le {\sum }_{i=1}^m\min (b_i,k)$

（可以用最小割來理解，也可以用貪心的思路來理解）

巧妙地轉(zhuǎn)化一下，設(shè)$c_k$表示$b_i\ge k$的個數(shù)，則${\sum }_{i=1}^m\min (b_i,k)={\sum }_{i=1}^k{c}_i$

所以滿流要求等價于，$?k\in [0,n]$ ，${\sum }_{i=1}^k{c}_i?a_i\ge 0$

這個可以用線段樹來維護(hù)每個$k$的${\sum }_{i=1}^k{c}_i?a_i$最小值

• 具體而言，記錄$sum={\sum }_{i=1}^n{a}_i$（$a_i$是已經(jīng)排序后的結(jié)果）

  要求${\sum }_{i=1}^k{c}_k?a_k\ge 0$，但是隨著$k$的變化，$a$的累和也在變，不同的$c_k$要大于的$a_k$累和也不一樣

  我們不妨通過一些累加，使得最后要比較的對象都是$sum$

  即，$c_k\leftarrow {\sum }_{i=k+1}^n{a}_i$

  所以線段樹上每個$k$放的其實(shí)是${\sum }_{i=1}^k{c}_i$

  最后就是比較線段樹的最小值是否$\ge sum$即可

• 雖然放的是${\sum }_{i=1}^k{c}_i$，但我們還是通過${\sum }_{i=1}^m\min (b_i,k)$求得的

  將$b$從小到大排序后，枚舉$k$，用指針$now$指向最后一個$\le k$的$b_i$

  后面$[now+1,n]$的和自然是$k\times (n?now)$

  前$now$個的$b_i$，可以前綴和預(yù)處理，上面累加的區(qū)間$a_i$同理

接下來就是考慮四種操作對線段樹造成的影響

• 操作$1:a_i+1$

  首先找到$a_i$排序后的區(qū)間$[l,r]$（很有可能不只一個值為$a_i$）

  只會對線段樹上$a[0,l)$區(qū)間造成$1$的影響

  仔細(xì)想想，只有$[0,l)$才會得到后面部分$[l,n]$特殊手段的累加，最后比較對象才會是$sum$

  當(dāng)$a_i+1$后，假設(shè)重新排序就會在$[l,r]$前面，真正影響的是比$a_i$大的$a[0,l)$

• 操作$2:a_i?1$

  與操作$1$同理，只不過是對$a[0,r)$區(qū)間造成$?1$的影響

  當(dāng)$a_i?1$后，假設(shè)重新排序就會在$[l,r]$后面，$[l,r]$也被影響到

• 操作$3:b_i+1$

  只有原本滿足$c_k\ge b_i+1$的$c_k$才會$+1$

• 操作$4:b_i?1$

  只有原本滿足$c_k\ge b_i$的$c_k$才會$?1$

都是區(qū)間加減的操作

code

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define int long long #define maxn 250005 #define N 500005 int n, m, Q, sum; int A[maxn], B[maxn], a[maxn], b[maxn], suma[maxn], sumb[maxn], c[maxn], tree[maxn];void add( int i, int x ) {i ++;for( ;i < N;i += i & -i ) tree[i] += x; }int ask( int i ) {i ++; int ans = 0;for( ;i > 0;i -= i & -i ) ans += tree[i];return ans; }#define lson now << 1 #define rson now << 1 | 1 int Min[maxn << 2], tag[maxn << 2];void build( int now, int l, int r ) {if( l == r ) { Min[now] = c[l]; return; };int mid = ( l + r ) >> 1;build( lson, l, mid );build( rson, mid + 1, r );Min[now] = min( Min[lson], Min[rson] ); }void pushdown( int now ) {Min[lson] += tag[now];tag[lson] += tag[now];Min[rson] += tag[now];tag[rson] += tag[now];tag[now] = 0; }void modify( int now, int l, int r, int L, int R, int x ) {if( R < l or r < L or L > R ) return;if( L <= l and r <= R ) {Min[now] += x;tag[now] += x;return;}pushdown( now );int mid = ( l + r ) >> 1;modify( lson, l, mid, L, R, x );modify( rson, mid + 1, r, L, R, x );Min[now] = min( Min[lson], Min[rson] ); }signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= n;i ++ ) {scanf( "%lld", &A[i] );add( A[i], 1 );a[i] = A[i];sum += a[i];} for( int i = 1;i <= m;i ++ ) {scanf( "%lld", &B[i] );b[i] = B[i];}sort( a + 1, a + n + 1, []( int x, int y ) { return x > y; } );sort( b + 1, b + m + 1 );b[m + 1] = 1e9;for( int i = 1;i <= max( n, m );i ++ ) {suma[i] = suma[i - 1] + a[i];sumb[i] = sumb[i - 1] + b[i];}c[0] = sum;for( int i = 1, now = 0;i <= n;i ++ ) {while( b[now + 1] <= i ) now ++;c[i] = suma[n] - suma[i] + sumb[now] + i * ( m - now );}build( 1, 0, n );scanf( "%lld", &Q );while( Q -- ) {int opt, i;scanf( "%lld %lld", &opt, &i );switch( opt ) {case 1 : {sum ++;int x = n - ask( A[i] ) + 1;modify( 1, 0, n, 0, x - 1, 1 );add( A[i], -1 ), add( ++ A[i], 1 );break;}case 2 : {sum --;int x = n - ask( A[i] - 1 );modify( 1, 0, n, 0, x - 1, -1 );add( A[i], -1 ), add( -- A[i], 1 ); break;}case 3 : {modify( 1, 0, n, ++ B[i], n, 1 );break;}case 4 : {modify( 1, 0, n, B[i] --, n, -1 );break;}}if( Min[1] < sum ) printf( "0\n" );else printf( "1\n" );}return 0; }

總結(jié)

以上是生活随笔為你收集整理的切题 (problem)（线段树+最大流最小割）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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