Abstract
传送门
这题是线段树+离散化的典型例子。
Idea
题目要求我们求出在至多只改变一朵花种植时间的情况下,最多有多长的时间是有且只有一朵花开放的。种花可以视为给起始时间到中止时间的区间 +1 ,挖走一朵花,只用在原来的起始时间到中止时间的区间 -1,即可,自然的想到用线段树去维护这个过程,考虑到本题 m 的大小达到了 1e9 ,故而需要加一个离散化。
顺便一提,这个题和扫描线模板非常相似。
Code
#include <bits/stdc++.h>
#define int long long
int n, m;
namespace seg
{
const int maxn = 10000000;
struct Node
{
int sum1, sum0, l, r;
bool work; // 标志这个节点是否被激活
} node[maxn];
int index[maxn];
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
#define m(l, r) (l + r >> 1)
int lazy[maxn];
void pushUp(int p)
{
if (lazy[p])
{
node[p].sum0 = 0;
if (lazy[p] > 1)
{
node[p].sum1 = 0;
}
else
{
node[p].sum1 = node[l(p)].sum0 + node[r(p)].sum0;
}
}
else
{
node[p].sum0 = node[l(p)].sum0 + node[r(p)].sum0;
node[p].sum1 = node[l(p)].sum1 + node[r(p)].sum1;
}
return;
}
void build(int p, int l, int r)
{
node[p].work = 1;
node[p].l = index[l], node[p].r = index[r];
if (r - l > 1)
{
build(l(p), l, m(l, r));
build(r(p), m(l, r), r);
pushUp(p);
}
else
{
node[p].sum0 = node[p].r - node[p].l;
node[p].sum1 = 0;
}
return;
}
void update(int p, int ql, int qr, int k)
{
int l = node[p].l, r = node[p].r;
if (ql <= l && r <= qr)
{
lazy[p] += k;
if (!node[l(p)].work)
{
if (lazy[p] > 1)
{
node[p].sum0 = 0;
node[p].sum1 = 0;
}
else if (lazy[p] == 1)
{
node[p].sum0 = 0;
node[p].sum1 = node[p].r - node[p].l;
}
else
{
node[p].sum0 = node[p].r - node[p].l;
node[p].sum1 = 0;
}
}
else
{
pushUp(p);
}
}
if (node[l(p)].r > ql)
{
update(l(p), ql, qr, k);
}
if (node[r(p)].l < qr)
{
update(r(p), ql, qr, k);
}
pushUp(p);
return;
}
};
int t[seg::maxn];
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(nullptr);
std::cin >> n >> m;
for (int i = 0; i < n; i++)
{
std::cin >> t[i];
// 离散化处理
seg::index[2 * i + 2] = t[i];
seg::index[2 * i + 1] = t[i] + m;
}
std::sort(seg::index + 1, seg::index + 2 * n + 1);
seg::build(1, 1, 2 * n);
for (int i = 0; i < n; i++)
{
seg::update(1, t[i], t[i] + m, 1);
}
// 如果初识状态就已经是最大值,直接输出 ori_ans 即可
int ori_ans = seg::node[1].sum1;
int ans = -1e8;
for (int i = 0; i < n; i++)
{
seg::update(1, t[i], t[i] + m, -1);
ans = std::max(ans, seg::node[1].sum1);
seg::update(1, t[i], t[i] + m, 1);
}
if (ori_ans >= ans + m)
{
std::cout << ori_ans;
}
else
{
std::cout << ans + m;
}
return 0;
}
标签:node,P10837,洛谷,index,int,sum1,sum0,seg,FLA
From: https://www.cnblogs.com/carboxylBase/p/18343205