[ABC324G] Generate Arrays
第一次知道 AtCoder 还有这种数据结构题。
首先，所谓的“切分序列”是假，实际上只需要记录每个操作后，具体取到的原始数组的值域、下标域是什么。对于给定的下标域，求值域内数的个数，可以使用可持久化线段树，很类似区间第 \(k\) 大数的思路。
对于操作一，考虑外层二分到底从原始数组的哪个下标切开，修改下标域。对于操作二，直接修改值域。
本题中“空区间”非常坑人，注意特判。
#include <bits/stdc++.h>
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=200010;
using namespace std;
int n, root[N], l[N], r[N], mn[N], mx[N], Empty[N];
struct node
{
int l, r, s;
} t[N<<6]; int tot;
#define lc(p) t[p].l
#define rc(p) t[p].r
void up(int p) {t[p].s=t[lc(p)].s+t[rc(p)].s;}
int modify(int y, int l, int r, int k) // 可持久化插入一个数
{
int x=++tot; t[x]=t[y];
if(l==r) {t[x].s++; return x;}
int m=l+r>>1;
if(k<=m) lc(x)=modify(lc(y), l, m, k);
else rc(x)=modify(rc(y), m+1, r, k);
up(x); return x;
}
int query(int x, int y, int l, int r, int ql, int qr) // 查询值域区间内元素个数
{
if(ql<=l && r<=qr) return t[x].s-t[y].s;
int m=l+r>>1, res=0;
if(ql<=m) res+=query(lc(x), lc(y), l, m, ql, qr);
if(qr>m) res+=query(rc(x), rc(y), m+1, r, ql, qr);
return res;
}
int main()
{
scanf("%d", &n);
rep(i, 1, n)
{
int x; scanf("%d", &x);
root[i]=modify(root[i-1], 1, n, x);
}
int Q; scanf("%d", &Q);
l[0]=1, r[0]=n, mn[0]=1, mx[0]=n;
rep(i, 1, Q)
{
int t, s, x; scanf("%d%d%d", &t, &s, &x);
if(Empty[s]) {Empty[i]=1, puts("0"); continue;}
l[i]=l[s], r[i]=r[s], mn[i]=mn[s], mx[i]=mx[s];
if(t==1)
{
int L=l[i], R=r[i], k=-1; // k:“第x个数”对应的真实下标
while(L<=R)
{
int m=L+R>>1;
if(query(root[m], root[l[i]-1], 1, n, mn[i], mx[i])<=x)
k=m, L=m+1;
else R=m-1;
}
l[i]=max(l[i], k+1), r[s]=min(r[s], k);
if(l[i]>r[i]) Empty[i]=1;
if(l[s]>r[s]) Empty[s]=1;
}
else
{
mn[i]=max(mn[i], x+1), mx[s]=min(mx[s], x); // 修改值域
if(mn[i]>mx[i]) Empty[i]=1;
if(mn[s]>mx[s]) Empty[s]=1;
}
if(Empty[i]) puts("0");
else printf("%d\n", query(root[r[i]], root[l[i]-1], 1, n, mn[i], mx[i]));
}
return 0;
}
[ABC332G] Not Too Many Balls
一道综合性非常强的好题。
首先，本题的基本模型是一个非常裸的最大流：
原点向颜色 \(i\) 连容量 \(a_i\) 的边；
颜色 \(i\) 向盒子 \(j\) 连容量 \(i\cdot j\) 的边；
盒子 \(j\) 向汇点连容量 \(b_j\) 的边。
但暴力连边并跑最大流会超时。
考虑到无法优化建边，将最大流转化为最小割，尝试解决。
记集合 \(A=[1,n],B=[1,m]\)，如果割掉 \((s,i)\) 边，记 \(i\) 在集合 \(S\) 中；割掉 \((j,t)\) 边，记 \(j\) 在集合 \(T\) 中。最小割就是：
\[\min(\sum_{i\in S}a_i+\sum_{i\in A-S,j\in B-T}i\cdot j+\sum_{j\in T}b_j) \]中间一项的意思是，如果 \((i,j)\) 边左连原点，右连汇点，就需要割断。
看到 \(n\) 很小，考虑枚举 \(k\)，感性理解为左边不割的下标和。记：
\[k=\sum_{i\in A-S}i \]原式改写为：
\[\min(\sum_{i\in S}a_i+\sum_{j\in B-T}k\cdot j+\sum_{j\in T}b_j) \]再想一下，右边两项可以理解为，对每个 \(j\) 可以自由地选择割掉容量为 \(b_j\) 的边或容量为 \(k\cdot j\) 的边。
\[\min(\sum_{i\in S}a_i+\sum_{j\in B}\min(k\cdot j,b_j)) \]外层枚举着 \(k\)，贪心地对每个 \(j\) 自由选择，至于左边那一项，可以预处理 DP。
DP 的具体思路：
记 \(f(i,j)\) 表示到下标 \(i\) 为止，选择了若干 \(i'\) 不割掉 \((s,i')\) 边，\(\sum i'=j\)（\(j\) 其实就是上文提到的 \(k\)），最小割。
转移有：割 \((s,i)\)，\(f(i,j)=f(i-1,j)+a_i\)；不割，\(f(i,j)=f(i-1,j-i)\)。
贪心的具体思路：
对每一个 \(j\) 预处理 \(b_j\le j\cdot k\) 的最小 \(k\)，也就是到达这个 \(k\) 就开始选择 \(b_j\)。移项得 \(k\ge b_j/j\)，\(k\) 的最小整数值即为 \(b_j/j\) 上取整。按这个值排序。
一开始假设每个 \(j\) 都选 \(j\cdot k\)。随着 \(k\) 的增长，\(j\cdot k\) 会逐步被 \(b_j\) 替代掉，按照先前制定的顺序依次修改即可。
// Title: Not Too Many Balls
// Source: ABC332G
// Author: Jerrywang
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<ll, int>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=505, M=500010;
using namespace std;
inline ll read()
{
ll x=0, f=1;
char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0'; c=getchar();}
return x*f;
}
int n, m; ll a[N], b[M]; pii t[M];
ll f[N][N*N]; // a数组到i为止，不割掉的下标和为j，最小总和
int main()
{
#ifdef Jerrywang
freopen("in.txt", "r", stdin);
#endif
n=read(), m=read();
rep(i, 1, n) a[i]=read();
rep(i, 1, m) b[i]=read();
rep(i, 1, n) rep(j, 0, n*n)
{
f[i][j]=f[i-1][j]+a[i];
if(j>=i) f[i][j]=min(f[i][j], f[i-1][j-i]);
}
rep(i, 1, m) t[i]={(b[i]+i-1)/i, i}; // b[j]<=jk的最小k
sort(t+1, t+m+1);
int i=1;
ll sum1=(ll)m*(m+1)/2, sum2=0, ans=LLONG_MAX;
rep(k, 0, n*n)
{
while(i<=m && t[i].F==k)
{
sum1-=t[i].S; sum2+=b[t[i].S];
i++;
}
ans=min(ans, f[n][k]+k*sum1+sum2);
}
printf("%lld", ans);
return 0;
}