2024.03.21专题
T1 Bombs
答案显然具有单调性，多删一定比少删更优，这是明显的
一个数 \(a_i=x\) 不被删掉的充要条件为:
\[\sum\limits_{j=1}^{i-1}[a_j < x] \leq k \]其中 \(k\) 为 \(i\) 之前的炸弹数量
由单调性，考虑每次加一个炸弹后怎么快速的检查一个数合不合法，可以用线段树维护全局的 \(max\) 和区间加
时间复杂度为 \(\mathcal{O}(nlogn)\)
code
// Author: xiaruize
#ifndef ONLINE_JUDGE
#define debug(x) cerr << "On Line:" << __LINE__ << #x << "=" << x << endl
bool start_of_memory_use;
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 3e5 + 10;
struct segment_tree
{
#define ls p << 1
#define rs p << 1 | 1
struct node
{
int mx, lz;
void tag(int x)
{
mx += x;
lz += x;
}
} tr[N << 2];
void pushdown(int p)
{
tr[ls].tag(tr[p].lz);
tr[rs].tag(tr[p].lz);
tr[p].lz = 0;
}
void pushup(int p)
{
tr[p].mx = max(tr[ls].mx, tr[rs].mx);
}
void update(int p, int l, int r, int ll, int rr, int v)
{
if (ll <= l && r <= rr)
{
tr[p].tag(v);
return;
}
pushdown(p);
int mid = l + r >> 1;
if (mid >= ll)
update(ls, l, mid, ll, rr, v);
if (mid < rr)
update(rs, mid + 1, r, ll, rr, v);
pushup(p);
}
} seg;
int n;
int p[N], q[N], pos[N];
void solve()
{
cin >> n;
rep(i, 1, n)
{
cin >> p[i];
pos[p[i]] = i;
}
rep(i, 1, n) cin >> q[i];
seg.update(1, 1, n, 1, pos[n], 1);
int res = n;
cout << n << ' ';
rep(i, 1, n - 1)
{
seg.update(1, 1, n, 1, q[i], -1);
while (seg.tr[1].mx <= 0)
{
res--;
seg.update(1, 1, n, 1, pos[res], 1);
}
cout << res << ' ';
}
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}
T2 P1484 种树
\(dp\) 是 \(\mathcal{O}(nk)\) 的，且不太好优化，故考虑贪心
假设当前选择了 \(a_x\)，且 \(a_x\) 周围2格都是空，那么下一步有两种情况
- 选择 \(a_{x-1},a_{x+1}\) 并删除 \(a_x\)
- 选择不与 \(a_x\) 相邻的数 \(a_y\)
对于第一种情况的证明
考虑删除 \(a_x\) 后不选择 \(a_{x-1},a_{x+1}\)
那么，选择 \(a_x\) 和新增的一个数必然覆盖的区间更小且价值更大
所以是不优的
所以如果删除 \(a_x\) 则必然选择 \(a_{x-1},a_{x+1}\)
用链表和优先队列维护，每次选择一个，将两侧的删掉，当前的的权值改为 \(a_x\leftarrow a_{x-1}+a_{x+1}-a_x\) 并重新压入优先队列
code
// Author: xiaruize
#ifndef ONLINE_JUDGE
#define debug(x) cerr << "On Line:" << __LINE__ << #x << "=" << x << endl
bool start_of_memory_use;
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 3e5 + 10;
int n, k;
int a[N << 1], pre[N], nxt[N];
priority_queue<pii> q;
bool vis[N];
void del(int x)
{
nxt[pre[x]] = nxt[x];
pre[nxt[x]] = pre[x];
}
void solve()
{
cin >> n >> k;
rep(i, 1, n)
{
cin >> a[i];
pre[i] = i - 1;
nxt[i] = i + 1;
q.push({a[i], i});
}
int res = 0;
int ans = 0;
while (k--)
{
while (vis[q.top().second])
q.pop();
int x = q.top().second;
q.pop();
res += a[x];
ans = max(ans, res);
a[x] = a[pre[x]] + a[nxt[x]] - a[x];
q.push({a[x], x});
vis[pre[x]] = vis[nxt[x]] = true;
del(pre[x]);
del(nxt[x]);
}
cout << ans << endl;
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}