【CF739C】Alyona and towers
【CF739C】Alyona and towers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Alyona has
built n towers by
putting small cubes some on the top of others. Each cube has size 1 × 1 × 1. A tower is a
non-zero amount of cubes standing on the top of each other. The towers are next
to each other, forming a row.
Sometimes Alyona
chooses some segment towers, and put on the top of each tower several cubes.
Formally, Alyona chooses some segment of towers from li to ri and
adds di cubes on
the top of them.
Let the
sequence a1, a2, ..., an be the
heights of the towers from left to right. Let's call as a segment of
towers al, al + 1, ..., ar a hill if
the following condition holds: there is integer k (l ≤ k ≤ r) such
that al < al + 1 < al + 2 < ... < ak > ak + 1 > ak + 2 > ... > ar.
After each
addition of di cubes on the top of the towers from li to ri, Alyona wants
to know the maximum width among all hills. The width of a hill is the number of
towers in it.
Input
The first line
contain single integer n (1 ≤ n ≤ 3·105) — the
number of towers.
The second line
contain n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the
number of cubes in each tower.
The third line
contain single integer m (1 ≤ m ≤ 3·105) — the
number of additions.
The next m lines
contain 3 integers
each. The i-th of these lines contains integers li, ri and di (1 ≤ l ≤ r ≤ n, 1 ≤ di ≤ 109), that mean
that Alyona puts di cubes on the tio of each of the
towers from li to ri.
Output
Print m lines.
In i-th line print
the maximum width of the hills after the i-th addition.
Example
input
Copy
5
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1
output
Copy
2
4
5
4
5
Note
The first sample
is as follows:
After addition
of 2 cubes on
the top of each towers from the first to the third, the number of cubes in the
towers become equal to [7, 7, 7, 5, 5]. The hill with maximum width is [7, 5], thus the
maximum width is 2.
After addition
of 1 cube on
the second tower, the number of cubes in the towers become equal to [7, 8, 7, 5, 5]. The hill with
maximum width is now [7, 8, 7, 5], thus the maximum width is 4.
After addition
of 1 cube on
the fourth tower, the number of cubes in the towers become equal to [7, 8, 7, 6, 5]. The hill with
maximum width is now [7, 8, 7, 6, 5], thus the maximum width is 5.
题意翻译
现在有n个数，m个操作，每次区间加一个数，对于每一次操作，你要找出最长的al...ar ，满足
∃k∈[l,r],al<al+1<al+2<...<ak>ak+1>ak+2>...>ar
输出其长度。
输入：
第一行一个整数n，表示数的个数。
第二行n个整数ai。
第三行一个整数m，表示操作个数。
下面m行，每行3个整数， li,ri,di，表示将li到ri的数字加di。
输出：
对于每个操作，输出操作完后的答案(见题意)。
样例解释：
- 5 5 5 5 5 → 7 7 7 5 5 ，最长的是7 5，长度为2
- 7 7 7 5 5 → 7 8 7 5 5 ，最长的是7 8 7 5 ，长度为4
- 7 8 7 5 5 → 7 8 7 6 5 ，最长的是7 8 7 6 5 ，长度为5
题目较为恶心，线段树的 push_up
很难写
主要是分类讨论比较多，一类一类讨论即可
inline void push_up(const Tp &rt, const Tp &l, const Tp &r)
{
Tp mid = (l + r) >> 1;
tr[rt].L = tr[ls].L;
tr[rt].R = tr[rs].R;
tr[rt].v = std::max(tr[ls].v, tr[rs].v);
// update suf
tr[rt].suf = tr[ls].suf;
if (tr[ls].suf == mid - l + 1 && tr[rs].L < tr[ls].R)
{
tr[rt].suf += tr[rs].suf;
}
// update pre
tr[rt].pre = tr[rs].pre;
if (tr[rs].pre == r - mid && tr[ls].R < tr[rs].L)
{
tr[rt].pre += tr[ls].pre;
}
// update pre_hill && suf_hill
tr[rt].suf_hill = tr[ls].suf_hill;
tr[rt].pre_hill = tr[rs].pre_hill;
if (tr[ls].pre == mid - l + 1 && tr[ls].R < tr[rs].L)
{
tr[rt].suf_hill = std::max(tr[rt].suf_hill, tr[ls].pre + tr[rs].suf_hill);
}
if (tr[ls].pre_hill == mid - l + 1 && tr[ls].R > tr[rs].L)
{
tr[rt].suf_hill = std::max(tr[rt].suf_hill, tr[ls].suf_hill + tr[rs].suf);
}
if (tr[rs].suf == r - mid && tr[rs].L < tr[ls].R)
{
tr[rt].pre_hill = std::max(tr[rt].pre_hill, tr[rs].suf + tr[ls].pre_hill);
}
if (tr[rs].suf_hill == r - mid && tr[rs].L > tr[ls].R)
{
tr[rt].pre_hill = std::max(tr[rt].pre_hill, tr[ls].pre + tr[rs].suf_hill);
}
// update v
tr[rt].v = std::max({tr[rt].v, tr[rt].suf_hill, tr[rt].pre_hill, tr[rt].suf, tr[rt].pre});
if (tr[ls].R > tr[rs].L)
{
tr[rt].v = std::max(tr[rt].v, tr[ls].pre_hill + tr[rs].suf);
}
if (tr[ls].R < tr[rs].L)
{
tr[rt].v = std::max(tr[rt].v, tr[rs].suf_hill + tr[ls].pre);
}
}
其实官方的题解已经写得很好了
照着实现即可
整个代码见下
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include "bits/stdc++.h"
#define mem(x) memset((x), 0, sizeof((x)))
#define il __attribute__((always_inline))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#if __cplusplus > 201403L
#define r
#else
#define r register
#endif
#define c const
namespace _c
{
c double pi = acos(-1.0);
namespace min
{
c int i8 = -128;
c int i16 = -32768;
c int i = -2147483647 - 1;
c ll l = -9223372036854775807LL - 1;
} // namespace min
namespace max
{
c int i8 = 127;
c int i16 = 32767;
c int i = 2147483647;
c ll l = 9223372036854775807LL;
} // namespace max
} // namespace _c
namespace _f
{
template <typename T>
inline c T gcd(T m, T n)
{
while (n != 0)
{
T t = m % n;
m = n;
n = t;
}
return m;
}
template <typename T>
inline c T abs(c T &a)
{
return a > 0 ? a : -a;
}
template <typename T>
inline T pow(T a, T b)
{
T res = 1;
while (b > 0)
{
if (b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
template <typename T>
inline T pow(T a, T b, c T &m)
{
a %= m;
T res = 1;
while (b > 0)
{
if (b & 1)
{
res = res * a % m;
}
a = a * a % m;
b >>= 1;
}
return res % m;
}
} // namespace _f
namespace io
{
template <typename T>
inline T read()
{
r T res = 0, neg = 1;
char g = getchar();
for (; !isdigit(g); g = getchar())
{
if (g == '-')
{
neg = -1;
}
}
for (; isdigit(g); g = getchar())
{
res = res * 10 + g - '0';
}
return res * neg;
}
template <typename T>
inline void read(T &t)
{
t = read<T>();
}
template <typename T>
inline void readln(c T first, c T last)
{
for (r T it = first; it != last; it++)
{
read(*it);
}
}
template <typename T>
inline void _write(T x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
_write(x / 10);
}
putchar(x % 10 + '0');
}
template <typename T>
inline void write(c T &x, c char &sep = ' ')
{
_write(x);
putchar(sep);
}
template <typename T>
inline void writeln(c T &x)
{
write(x, '\n');
}
template <typename T>
inline void writeln(c T first, c T last, c char &sep = ' ', c char &ends = '\n')
{
for (r T it = first; it != last; it++)
{
write(*it, sep);
}
putchar(ends);
}
#if __cplusplus >= 201103L
template <typename T, typename... Args>
void read(T &x, Args &... args)
{
read(x);
read(args...);
}
#endif
} // namespace io
#undef c
#undef r
const int N = 3e5 + 5;
int n, m;
int a[N];
template <typename Tp>
struct SegTree
{
struct T
{
Tp v;
Tp L, R;
Tp pre, suf;
Tp pre_hill, suf_hill;
Tp tag;
inline void set_to(const Tp &x)
{
v = L = R = pre = suf = pre_hill = suf_hill = 1;
L = R = x;
}
} tr[N * 4];
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define ls lson(rt)
#define rs rson(rt)
inline void push_up(const Tp &rt, const Tp &l, const Tp &r)
{
Tp mid = (l + r) >> 1;
tr[rt].L = tr[ls].L;
tr[rt].R = tr[rs].R;
tr[rt].v = std::max(tr[ls].v, tr[rs].v);
// update suf
tr[rt].suf = tr[ls].suf;
if (tr[ls].suf == mid - l + 1 && tr[rs].L < tr[ls].R)
{
tr[rt].suf += tr[rs].suf;
}
// update pre
tr[rt].pre = tr[rs].pre;
if (tr[rs].pre == r - mid && tr[ls].R < tr[rs].L)
{
tr[rt].pre += tr[ls].pre;
}
// update pre_hill && suf_hill
tr[rt].suf_hill = tr[ls].suf_hill;
tr[rt].pre_hill = tr[rs].pre_hill;
if (tr[ls].pre == mid - l + 1 && tr[ls].R < tr[rs].L)
{
tr[rt].suf_hill = std::max(tr[rt].suf_hill, tr[ls].pre + tr[rs].suf_hill);
}
if (tr[ls].pre_hill == mid - l + 1 && tr[ls].R > tr[rs].L)
{
tr[rt].suf_hill = std::max(tr[rt].suf_hill, tr[ls].suf_hill + tr[rs].suf);
}
if (tr[rs].suf == r - mid && tr[rs].L < tr[ls].R)
{
tr[rt].pre_hill = std::max(tr[rt].pre_hill, tr[rs].suf + tr[ls].pre_hill);
}
if (tr[rs].suf_hill == r - mid && tr[rs].L > tr[ls].R)
{
tr[rt].pre_hill = std::max(tr[rt].pre_hill, tr[ls].pre + tr[rs].suf_hill);
}
// update v
tr[rt].v = std::max({tr[rt].v, tr[rt].suf_hill, tr[rt].pre_hill, tr[rt].suf, tr[rt].pre});
if (tr[ls].R > tr[rs].L)
{
tr[rt].v = std::max(tr[rt].v, tr[ls].pre_hill + tr[rs].suf);
}
if (tr[ls].R < tr[rs].L)
{
tr[rt].v = std::max(tr[rt].v, tr[rs].suf_hill + tr[ls].pre);
}
}
inline void build(const Tp &rt, const Tp &l, const Tp &r)
{
if (l == r)
{
tr[rt].set_to(a[l]);
return;
}
Tp mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(rt, l, r);
}
inline void push_down(const Tp &rt)
{
tr[ls].tag += tr[rt].tag;
tr[rs].tag += tr[rt].tag;
tr[ls].R += tr[rt].tag;
tr[ls].L += tr[rt].tag;
tr[rs].R += tr[rt].tag;
tr[rs].L += tr[rt].tag;
tr[rt].tag = 0;
}
inline void update(const Tp &rt, const Tp &l, const Tp &r, const Tp &ul, const Tp &ur, const Tp &k)
{
if (ul <= l && r <= ur)
{
tr[rt].tag += k;
tr[rt].L += k;
tr[rt].R += k;
return;
}
push_down(rt);
Tp mid = (l + r) >> 1;
if (ul <= mid)
{
update(ls, l, mid, ul, ur, k);
}
if (ur > mid)
{
update(rs, mid + 1, r, ul, ur, k);
}
push_up(rt, l, r);
}
#undef ls
#undef rs
#undef lson
#undef rson
};
SegTree<ll> Seg;
int main()
{
io::read(n);
io::readln(a + 1, a + n + 1);
Seg.build(1, 1, n);
io::read(m);
for (int i = 1, l, r, k; i <= m; i++)
{
io::read(l, r, k);
Seg.update(1, 1, n, l, r, k);
io::writeln(Seg.tr[1].v);
}
}
评论
发表评论