E. Tracking Segments
给定初始长度为
n，且全为0的序列a，然后给出m个线段，如果一个线段中1的个数严格大于0的个数，那么该线段称为一个漂亮线段，现在给出q次操作，每次操作使得序列a中位置x上的0变为1，请你求出第一次使得所有线段中出现漂亮线段的询问
题解：二分答案
- 容易发现答案具有单调性，所以我们可以考虑二分答案
- 我们发现在
check的时候只要提前预处理好1和0个数前缀和数组即可，然后即可\(O(m)\)检验合法性- 分析其时间复杂度为：\(O(m\times logq)\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, m, q;
int L[N], R[N];
int qry[N];
bool check(int mid)
{
vector<int> a(n + 10), pre0(n + 10), pre1(n + 10);
for (int i = 1; i <= mid; ++i)
a[qry[i]] = 1;
for (int i = 1; i <= n; ++i)
{
pre1[i] = pre1[i - 1] + (a[i] == 1);
pre0[i] = pre0[i - 1] + (a[i] == 0);
}
for (int i = 1; i <= m; ++i)
{
if (pre1[R[i]] - pre1[L[i] - 1] > pre0[R[i]] - pre0[L[i] - 1])
return true;
}
return false;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; ++i)
cin >> L[i] >> R[i];
cin >> q;
for (int i = 1; i <= q; ++i)
cin >> qry[i];
int l = 1, r = q;
bool flag = false;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
{
r = mid - 1;
flag = true;
}
else
l = mid + 1;
}
if (flag)
cout << l << endl;
else
cout << -1 << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
F1. Omsk Metro (simple version)
给一棵有根树，每次给定点
v，询问从根节点到v路径上的某个连续子段的和能否等于k
题解：\(dp\)——最大/最小子段和
- 容易发现从根节点到\(v\)的路径上子段和的取值范围为\([最小子段和，最大字段和]\)
- 所以我们可以\(dp\)即可
- 状态转移时有3种选择：
- 选择接在前面的子段上
- 不接在前面的字段上，变成一个新的子段
- 选择成为空子段
- 查询时验证\(k\)是否在范围内即可
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n;
void solve()
{
cin >> n;
int idx = 1;
vector<int> fmin(n + 10, INF), fmax(n + 10, -INF);
vector<int> mi(n + 10, INF), mx(n + 10, -INF);
fmin[1] = 0;
fmax[1] = 1;
mi[1] = min({mi[1], fmin[1], 0LL});
mx[1] = max({mx[1], fmax[1], 0LL});
for (int i = 1; i <= n; ++i)
{
char op;
int u, v, k, x;
cin >> op;
if (op == '+')
{
cin >> u >> x;
idx++;
fmin[idx] = min({fmin[u] + x, x, 0LL});
fmax[idx] = max({fmax[u] + x, x, 0LL});
mi[idx] = min(mi[u], fmin[idx]);
mx[idx] = max(mx[u], fmax[idx]);
}
else
{
cin >> u >> v >> k;
if (mi[v] <= k && mx[v] >= k)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}