MX Day 19
OIer_ACMer · · 生活·游记
T1:
思路：
首先啊，做了这么多有关mex的题目，那么很简单，首先，我们要知道，最小未出现的数肯定是在一传连续出现的数后面，那么，我们可以发现个好玩的，首先，这个序列肯定要有个0，不然答案铁定是0，因为问的是第一个未出现的非负整数。如果有了0，那么答案一定是1，为何呢，因为当我们将0从整个数列单独抽出时，因为长度为1，且单独一个0这个数列的Mex是1，那么1/1还是1，至于别的……因为前面说过，Mex肯定是出现在一串连续数之后，那么mex/n肯定是小于等于1的，你不能找出一串连续数最后一位的大小还大于其长度。
Code：
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
char c = getchar();
int x = 0;
while (c < '0' or c > '9')
c = getchar();
while ('0' <= c and c <= '9')
x = x * 10 + (c ^ 48), c = getchar();
return x;
}
struct DS
{
// 支持动态修改某个位置的值，维护对位不相等的位置有多少个
// a_i,0 维护的是 b 序列期望应该有的数
// a_i,1 维护的是 b 序列实际应该有的数
int a[2000005][2];
int cnt;
void clear(int len)
{
cnt = 0;
for (int i = 0; i <= len; i++)
a[i][0] = a[i][1] = 0;
return;
}
void upd(int p, int k, int add)
{
cnt -= (a[p][0] != a[p][1]);
a[p][k] += add;
cnt += (a[p][0] != a[p][1]);
}
int query() { return cnt; }
} T;
int N;
int c[2000005];
int n, m;
int a[2000005], b[2000005], cnt[2000005];
int p[2000005], ll = 0;
int ans = 0;
void work()
{
// 考察，如果最大值在 a 处，有多少合法的序列
T.clear(n + m);
int mx = 0, ll = 0;
// 最大值 b 序列目前对应的指针
for (int i = 1; i <= n; i++)
if (a[i] <= n + m)
cnt[a[i]] = 0;
for (int i = 1; i <= n; i++)
{
// cout << i << endl;
int lmx = mx;
mx = max(mx, a[i]);
if (mx > n + m or ++cnt[a[i]] > 1)
break;
for (int j = lmx + 1; j <= mx; j++)
T.upd(j, 0, 1); // 这些数字需要在 b 中出现
if (a[i] <= n + m)
T.upd(a[i], 0, -1); // 这个数字不需要
while (ll != m and ll < mx - i)
{
// 左边此时对应的长度
if (b[++ll] <= n + m)
T.upd(b[ll], 1, 1);
}
while (ll != 0 and ll > mx - i)
{
if (b[ll] <= n + m)
T.upd(b[ll], 1, -1);
--ll;
}
if (!T.query())
++ans;
}
}
signed main()
{
freopen("mex.in", "r", stdin);
freopen("mex.out", "w", stdout);
N = read();
for (int i = 1; i <= N; i++)
c[i] = read();
p[ll = 1] = 0;
for (int i = 1; i <= N; i++)
if (c[i] == 0)
p[++ll] = i;
p[++ll] = N + 1;
if (ll == 2)
{
cout << 1ll * N * (N + 1) / 2 << endl;
return 0;
}
for (int i = 2; i < ll; i++)
{
n = m = 0;
for (int j = p[i] - 1; j > p[i - 1]; j--)
a[++n] = c[j];
for (int j = p[i] + 1; j < p[i + 1]; j++)
b[++m] = c[j];
// 统计跨过目前这个 0 的贡献
++ans;
work();
swap(a, b), swap(n, m);
work();
}
cout << ans << endl;
}T2：
思路：
首先，这道题我们先不看求max，因为我们可以将其转化成其它的形式，例如，我们可以将其变为在折线上取最小值，然后算海拔高度差，就相当于取0然后完成剩余操作。
现在，我们可以知道最终折线位于哪里，要找的是我们的最小值定位在哪（也可以叫做那个地方最终取0，这是不确定的），由于我们上述操作就相当于是在原题的基础上将每一个减ai的操作给具象化了，说白了就是给每个数都减到ai，而不是跟零进行比较。那么我们再将减AI的操作转化为加bi时，我们只用将原先没有对，零求最大值的折线数列加上ai+bi就可以了。那么为了答案最大，我们要加上末尾的最大的k个ai+bi才能够保证我们的答案最优。
啥？你问我为什么没有考虑到当你选的点不是最小值的时候，答案会出错。那很简单啊，因为我们如果选择点没有到达零，那么只会让答案偏小，毕竟答案最后是由折线最后一个数s减去折线最小值mn得到的。如果mn选择数较大，那么答案主要偏小，不可能再发生变化。
Code：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x & (-x))
const int inf = 1e18;
struct DS
{
priority_queue<int, vector<int>, greater<int>> q1, del1;
priority_queue<int> q2, del2;
int sum = 0;
void clear()
{
sum = 0;
while (q1.size())
{
q1.pop();
}
while (q2.size())
{
q2.pop();
}
while (del1.size())
{
del1.pop();
}
while (del2.size())
{
del2.pop();
}
}
void add(int x)
{
while (del1.size() and del1.top() == q1.top())
{
del1.pop(), q1.pop();
}
if (q1.size() and x >= q1.top())
{
q1.push(x), sum += x;
}
else
{
q2.push(x);
}
}
void del(int x)
{
while (del1.size() and del1.top() == q1.top())
{
q1.pop(), del1.pop();
}
if (q1.size() and x >= q1.top())
{
del1.push(x), sum -= x;
}
else
{
del2.push(x);
}
}
int query(int k)
{
while (q1.size() - del1.size() < k and q2.size() > del2.size())
{
while (del2.size() and del2.top() == q2.top())
{
del2.pop(), q2.pop();
}
q1.push(q2.top());
sum += q2.top();
q2.pop();
}
while (q1.size() - del1.size() > k)
{
while (del1.size() and del1.top() == q1.top())
{
del1.pop(), q1.pop();
}
q2.push(q1.top());
sum -= q1.top();
q1.pop();
}
return sum;
}
} T;
int n, x;
int a[300005], b[300005];
int pre[300005], ans[300005];
void solve(int l, int r, int pl, int pr)
{
if (l > r)
{
return;
}
int p = -1, mx = -inf, mid = l + r >> 1;
for (int i = pr; i >= pl; i--)
{
if (i != n + 1)
{
T.add(b[i]);
}
int v = T.query(mid) + pre[i - 1];
if (v > mx)
{
mx = v, p = i;
}
}
ans[mid] = mx;
for (int i = pl; i <= p; i++)
{
if (i != n + 1)
{
T.del(b[i]);
}
}
solve(mid + 1, r, pl, p);
for (int i = p + 1; i <= pr; i++)
{
if (i != n + 1)
{
T.del(b[i]);
}
}
solve(l, mid - 1, p, pr);
}
void solve()
{
T.clear();
cin >> n >> x;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
for (int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1] + a[i];
}
for (int i = 1; i <= n; i++)
{
b[i] += a[i];
}
solve(1, n, 1, n + 1);
for (int i = 1; i <= n; i++)
{
ans[i] -= pre[n];
}
sort(b + 1, b + 1 + n), reverse(b + 1, b + 1 + n);
int sum = 0;
for (int i = 1; i <= n; i++)
{
sum += b[i];
ans[i] = max(x + sum - pre[n], ans[i]);
}
for (int i = 1; i <= n; i++)
{
cout << ans[i] << ' ';
}
cout << '\n';
}
signed main()
{
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}