- description
- solution
- code
在一个神秘的 JOSLFN 上，wzy 和 lqs2015 常年占据着切题榜的 rk1 和 rk2。现在他们在研究
如何快速造题并验题。
分工是这样的：有 n 个 wzy 负责造题，第 i 个 wzy 会造出恰好 ai 道题。有 m 个 lqs2015 负责
验题，第 j 个 lqs2015 最多能验 bj 道题。每个 wzy 需要把他造的每一道题都给一个 lqs2015 来验。
不过有一条限制，就是每个 wzy 的 ai 道题必须给不同的 lqs2015 ，否则这个 lqs2015 会因为验到了
来自同一个 wzy 的题而感到厌烦并且让所有 wzy 和 lqs2015 都消失。
在一旁瑟瑟发抖的 superay 想要知道，是否存在一种符合限制的验题的分配方案。
随着时间的推移，会有 q 次对 a, b 的修改。每次修改有如下四种：
• 1 i 表示将 ai 加 1。
• 2 i 表示将 ai 减 1。
• 3 j 表示将 bj 加 1。
• 4 j 表示将 bj 减 1。
superay 想知道每次修改之后还是否存在合法方案。
Input
第一行两个正整数 n, m。
第二行 n 个非负整数 a1, a2, ···, an。
第三行 m 个非负整数 b1, b2, ···, bm。
第四行一个正整数 q。
接下来 q 行，每行是如下四种之一：
• 1 i (1 ≤i ≤n)
• 2 i (1 ≤i ≤n)
• 3 j (1 ≤j ≤m)
• 4 j (1 ≤j ≤m)
保证任意时刻 a, b 都非负。
Output
输出 q 行，第 i 行表示在第 i 次操作之后的答案，有解输出 1，无解输出 0。
subtask1: n,m,q<=50
这么小的数据，肯定是暴力基础分，直接贪心做
贪心：造题数越多的人越先处理，验题数越多的人越先验
显然，这是为了留下更多的验题人和越小需要不同验题人数的造题人
subtask2: n,m,q<=1000
当时以为是什么 n 2 log n n^2log n n2logn的算法，整个数据结构
没想到原来是留给暴力网络流的
这是个最大网络流模板，如果告诉了是网络流，建图方式是显然的
超级源点 S S S，超级汇点 T T T
造题人和 S S S连边，流量为 a i a_i ai，验题人和 T T T连边，流量为 b i b_i bi，然后每个造题人和每个验题人之间都有连边，流量为 1 1 1
肯定的，网络流只有满流了才表示有解，即最大流为 ∑ i = 1 n a i sum_{i=1}^na_i ∑i=1nai
最后就是暴力跑网络流了
subtask3~4: n,m,q<=250000
subtask3 text{subtask3} subtask3可能是给正解写爆了的人准备的
通过 subtask2 text{subtask2} subtask2，已经知道是明显的网络流了，但是数据显然不允许直接硬刚
显然，剩下的工作就是寻找优化
众所周知，最大网络流等于最小割
将 a i a_i ai从大到小排序，满流等价于 ∀ k ∈ [ 0 , n ] forall kin[0,n] ∀k∈[0,n]，有 ∑ i = 1 k a i ≤ ∑ i = 1 m min ( b i , k ) sum_{i=1}^ka_ile sum_{i=1}^mmin(b_i,k) ∑i=1kai≤∑i=1mmin(bi,k)
（可以用最小割来理解，也可以用贪心的思路来理解）
巧妙地转化一下，设 c k c_k ck表示 b i ≥ k b_ige k bi≥k的个数，则 ∑ i = 1 m min ( b i , k ) = ∑ i = 1 k c i sum_{i=1}^mmin(b_i,k)=sum_{i=1}^kc_i ∑i=1mmin(bi,k)=∑i=1kci
所以满流要求等价于， ∀ k ∈ [ 0 , n ] forall kin[0,n] ∀k∈[0,n] ， ∑ i = 1 k c i − a i ≥ 0 sum_{i=1}^kc_i-a_ige 0 ∑i=1kci−ai≥0
这个可以用线段树来维护每个 k k k的 ∑ i = 1 k c i − a i sum_{i=1}^kc_i-a_i ∑i=1kci−ai最小值
-
具体而言，记录 s u m = ∑ i = 1 n a i sum=sum_{i=1}^na_i sum=∑i=1nai（ a i a_i ai是已经排序后的结果）
要求 ∑ i = 1 k c k − a k ≥ 0 sum_{i=1}^k c_k-a_kge 0 ∑i=1kck−ak≥0，但是随着 k k k的变化， a a a的累和也在变，不同的 c k c_k ck要大于的 a k a_k ak累和也不一样
我们不妨通过一些累加，使得最后要比较的对象都是 s u m sum sum
即， c k ← ∑ i = k + 1 n a i c_kleftarrow sum_{i=k+1}^na_i ck←∑i=k+1nai
所以线段树上每个 k k k放的其实是 ∑ i = 1 k c i sum_{i=1}^kc_i ∑i=1kci
最后就是比较线段树的最小值是否 ≥ s u m ge sum ≥sum即可
-
虽然放的是 ∑ i = 1 k c i sum_{i=1}^kc_i ∑i=1kci，但我们还是通过 ∑ i = 1 m min ( b i , k ) sum_{i=1}^mmin(b_i,k) ∑i=1mmin(bi,k)求得的
将 b b b从小到大排序后，枚举 k k k，用指针 n o w now now指向最后一个 ≤ k le k ≤k的 b i b_i bi
后面 [ n o w + 1 , n ] [now+1,n] [now+1,n]的和自然是 k × ( n − n o w ) ktimes (n-now) k×(n−now)
前 n o w now now个的 b i b_i bi，可以前缀和预处理，上面累加的区间 a i a_i ai同理
接下来就是考虑四种操作对线段树造成的影响
-
操作 1 : a i + 1 1:a_i+1 1:ai+1
首先找到 a i a_i ai排序后的区间 [ l , r ] [l,r] [l,r]（很有可能不只一个值为 a i a_i ai）
只会对线段树上 a [ 0 , l ) a[0,l) a[0,l)区间造成 1 1 1的影响
仔细想想，只有 [ 0 , l ) [0,l) [0,l)才会得到后面部分 [ l , n ] [l,n] [l,n]特殊手段的累加，最后比较对象才会是 s u m sum sum
当 a i + 1 a_i+1 ai+1后，假设重新排序就会在 [ l , r ] [l,r] [l,r]前面，真正影响的是比 a i a_i ai大的 a [ 0 , l ) a[0,l) a[0,l)
-
操作 2 : a i − 1 2:a_i-1 2:ai−1
与操作 1 1 1同理，只不过是对 a [ 0 , r ) a[0,r) a[0,r)区间造成 − 1 -1 −1的影响
当 a i − 1 a_i-1 ai−1后，假设重新排序就会在 [ l , r ] [l,r] [l,r]后面， [ l , r ] [l,r] [l,r]也被影响到
-
操作 3 : b i + 1 3:b_i+1 3:bi+1
只有原本满足 c k ≥ b i + 1 c_kge b_i+1 ck≥bi+1的 c k c_k ck才会 + 1 +1 +1
-
操作 4 : b i − 1 4:b_i-1 4:bi−1
只有原本满足 c k ≥ b i c_kge b_i ck≥bi的 c k c_k ck才会 − 1 -1 −1
都是区间加减的操作
code#include#include #include 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( "0n" ); else printf( "1n" ); } return 0; }
