建设网站网站,网站群维护方案,网站怎么做脚注,重庆长寿网站建设切题 problemdescriptionsolutioncodedescription
在一个神秘的 JOSLFN 上#xff0c;wzy 和 lqs2015 常年占据着切题榜的 rk1 和 rk2。现在他们在研究 如何快速造题并验题。 分工是这样的#xff1a;有 n 个 wzy 负责造题#xff0c;第 i 个 wzy 会造出恰好 ai 道题。有 m…
切题 problemdescriptionsolutioncodedescription
在一个神秘的 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。
solution
subtask1: n,m,q50
这么小的数据肯定是暴力基础分直接贪心做
贪心造题数越多的人越先处理验题数越多的人越先验
显然这是为了留下更多的验题人和越小需要不同验题人数的造题人 subtask2: n,m,q1000
当时以为是什么n2lognn^2\log nn2logn的算法整个数据结构
没想到原来是留给暴力网络流的
这是个最大网络流模板如果告诉了是网络流建图方式是显然的
超级源点SSS超级汇点TTT
造题人和SSS连边流量为aia_iai验题人和TTT连边流量为bib_ibi然后每个造题人和每个验题人之间都有连边流量为111
肯定的网络流只有满流了才表示有解即最大流为∑i1nai\sum_{i1}^na_i∑i1nai
最后就是暴力跑网络流了 subtask3~4: n,m,q250000
subtask3\text{subtask3}subtask3可能是给正解写爆了的人准备的
通过subtask2\text{subtask2}subtask2已经知道是明显的网络流了但是数据显然不允许直接硬刚
显然剩下的工作就是寻找优化
众所周知最大网络流等于最小割
将aia_iai从大到小排序满流等价于∀k∈[0,n]\forall k\in[0,n]∀k∈[0,n]有∑i1kai≤∑i1mmin(bi,k)\sum_{i1}^ka_i\le \sum_{i1}^m\min(b_i,k)∑i1kai≤∑i1mmin(bi,k)
可以用最小割来理解也可以用贪心的思路来理解
巧妙地转化一下设ckc_kck表示bi≥kb_i\ge kbi≥k的个数则∑i1mmin(bi,k)∑i1kci\sum_{i1}^m\min(b_i,k)\sum_{i1}^kc_i∑i1mmin(bi,k)∑i1kci
所以满流要求等价于∀k∈[0,n]\forall k\in[0,n]∀k∈[0,n] ∑i1kci−ai≥0\sum_{i1}^kc_i-a_i\ge 0∑i1kci−ai≥0
这个可以用线段树来维护每个kkk的∑i1kci−ai\sum_{i1}^kc_i-a_i∑i1kci−ai最小值 具体而言记录sum∑i1naisum\sum_{i1}^na_isum∑i1naiaia_iai是已经排序后的结果 要求∑i1kck−ak≥0\sum_{i1}^k c_k-a_k\ge 0∑i1kck−ak≥0但是随着kkk的变化aaa的累和也在变不同的ckc_kck要大于的aka_kak累和也不一样 我们不妨通过一些累加使得最后要比较的对象都是sumsumsum 即ck←∑ik1naic_k\leftarrow \sum_{ik1}^na_ick←∑ik1nai 所以线段树上每个kkk放的其实是∑i1kci\sum_{i1}^kc_i∑i1kci 最后就是比较线段树的最小值是否≥sum\ge sum≥sum即可 虽然放的是∑i1kci\sum_{i1}^kc_i∑i1kci但我们还是通过∑i1mmin(bi,k)\sum_{i1}^m\min(b_i,k)∑i1mmin(bi,k)求得的 将bbb从小到大排序后枚举kkk用指针nownownow指向最后一个≤k\le k≤k的bib_ibi 后面[now1,n][now1,n][now1,n]的和自然是k×(n−now)k\times (n-now)k×(n−now) 前nownownow个的bib_ibi可以前缀和预处理上面累加的区间aia_iai同理
接下来就是考虑四种操作对线段树造成的影响 操作1:ai11:a_i11:ai1 首先找到aia_iai排序后的区间[l,r][l,r][l,r]很有可能不只一个值为aia_iai 只会对线段树上a[0,l)a[0,l)a[0,l)区间造成111的影响 仔细想想只有[0,l)[0,l)[0,l)才会得到后面部分[l,n][l,n][l,n]特殊手段的累加最后比较对象才会是sumsumsum 当ai1a_i1ai1后假设重新排序就会在[l,r][l,r][l,r]前面真正影响的是比aia_iai大的a[0,l)a[0,l)a[0,l) 操作2:ai−12:a_i-12:ai−1 与操作111同理只不过是对a[0,r)a[0,r)a[0,r)区间造成−1-1−1的影响 当ai−1a_i-1ai−1后假设重新排序就会在[l,r][l,r][l,r]后面[l,r][l,r][l,r]也被影响到 操作3:bi13:b_i13:bi1 只有原本满足ck≥bi1c_k\ge b_i1ck≥bi1的ckc_kck才会111 操作4:bi−14:b_i-14:bi−1 只有原本满足ck≥bic_k\ge b_ick≥bi的ckc_kck才会−1-1−1
都是区间加减的操作
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;
}
