陶陶摘苹果
题目大意
- 给出n个苹果的高度hi，然后从左往右依次摘高度严格递增的苹果，问最多摘几个苹果，但是有个苹果高度给错了，m次给出更正一个高度之后在求解。
输入格式
- 第一行n，m， 第二行hi，一下每行2个数表示需要修改的苹果的编号和修改后的高度
输出格式
样例输入
5 3
1 2 3 4 4
1 5
5 5
2 3
样例输出
1
5
3
Solve1
- 考虑怎么优化，就想到了改一个点都会改那些，发现对前面是没有影响的，然后在改的地方后面找第一个大于前面最大值的点，预处理出来这个点到最后的答案就好了
- 然后就是预处理，先O(n)的把1～i的答案求出来，在用ST表+二分查找+线段树区间加把i～n的答案求出来，最后询问的时候在用二分回答。
Code
Show Code
#include <cstdio>
#define Max(x, y) ({int xx = x, yy = y; xx > yy ? xx : yy;})
const int N = 1e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int n, m, a[N], f[N], g[N], tag[N<<2];
long long t[N<<2];
struct ST {
int lg[N], f[20][N];
void Init() {
for (int i = 2; i <= n; ++i)
lg[i] = lg[i>>1] + 1;
for (int i = 0; i < lg[n]; ++i)
for (int x = 1; x + (1 << i + 1) - 1 <= n; ++x)
f[i+1][x] = Max(f[i][x], f[i][x+(1<<i)]);
}
int Ask(int l, int r) {
int k = lg[r-l+1];
return Max(f[k][l], f[k][r-(1<<k)+1]);
}
}b;
void Pushdown(int rt, int l, int r) {
int mid = l + r >> 1;
tag[rt<<1] += tag[rt];
t[rt<<1] += 1LL * tag[rt] * (mid - l + 1);
tag[rt<<1|1] += tag[rt];
t[rt<<1|1] += 1LL * tag[rt] * (r - mid);
tag[rt] = 0;
}
void Change(int rt, int l, int r, int x, int y) {
if (x > r || y < l) return;
if (x <= l && r <= y) {
t[rt] += r - l + 1;
tag[rt]++;
return;
}
if (tag[rt]) Pushdown(rt, l, r);
int mid = l + r >> 1;
Change(rt << 1, l, mid, x, y);
Change(rt << 1 | 1, mid + 1, r, x, y);
t[rt] = t[rt<<1] + t[rt<<1|1];
}
void Ask(int rt, int l, int r) {
if (l == r) return g[l] = t[rt], void();
if (tag[rt]) Pushdown(rt, l, r);
int mid = l + r >> 1;
Ask(rt << 1, l, mid);
Ask(rt << 1 | 1, mid + 1, r);
}
int Find1(int l, int r, int x) {//在l到r中查找>=x的数中位置最靠右的点的编号
if (b.Ask(l, r) < x) return l - 1;
if (l == r) return l;
int mid = l + r >> 1;
if (b.Ask(mid + 1, r) >= x) return Find1(mid + 1, r, x);
else return Find1(l, mid, x);
}
int Find2(int l, int r, int x) {//在l到r中查找>x的数中位置最靠左的点的编号
if (b.Ask(l, r) <= x) return r + 1;
if (l == r) return l;
int mid = l + r >> 1;
if (b.Ask(l, mid) > x) return Find2(l, mid, x);
else return Find2(mid + 1, r, x);
}
int main() {
freopen("taopapp.in", "r", stdin);
freopen("taopapp.out", "w", stdout);
n = read(); m = read();
for (int i = 1, x = 0; i <= n; ++i) {
b.f[0][i] = a[i] = read();
f[i] = f[i-1];
if (a[i] > x) x = a[i], f[i]++;
}
b.Init();
Change(1, 1, n, 1, 1);
for (int i = 2; i <= n; ++i)
Change(1, 1, n, Find1(1, i - 1, a[i]) + 1, i);
Ask(1, 1, n);
while (m--) {
int x = read(), y = read();
if (x == n) printf("%d
", f[x-1] + (y > b.Ask(1, x - 1)));
else if (x == 1) printf("%d
", 1 + g[Find2(x + 1, n, y)]);
else printf("%d
", f[x-1] + (y > b.Ask(1, x - 1)) + g[Find2(x + 1, n, Max(b.Ask(1, x - 1), y))]);
}
return 0;
}
Solve2
- 和楼房重建一样，线段树维护一下就好了，Pushup是log的，所以总复杂度是(O(nlog^2n))的
Code
Show Code
#include <cstdio>
#include <algorithm>
#define ls (rt << 1)
#define rs (rt << 1 | 1)
const int N = 1e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int n, m, a[N], t[N<<2], h[N<<2];
int Ask(int rt, int l, int r, int w) {
if (w >= h[rt]) return 0;
if (l == r) return 1;
int mid = l + r >> 1;
if (w >= h[ls]) return Ask(rs, mid + 1, r, w);
else return Ask(ls, l, mid, w) + t[rt] - t[ls];
}
void Build(int rt, int l, int r) {
if (l == r) return t[rt] = 1, h[rt] = a[l], void();
int mid = l + r >> 1;
Build(ls, l, mid);
Build(rs, mid + 1, r);
t[rt] = t[ls] + Ask(rs, mid + 1, r, h[ls]);
h[rt] = std::max(h[ls], h[rs]);
}
void Change(int rt, int l, int r, int x, int w) {
if (l == r) return h[rt] = w, void();
int mid = l + r >> 1;
if (x <= mid) Change(ls, l, mid, x, w);
else Change(rs, mid + 1, r, x, w);
t[rt] = t[ls] + Ask(rs, mid + 1, r, h[ls]);
h[rt] = std::max(h[ls], h[rs]);
}
int main() {
freopen("taopapp.in", "r", stdin);
freopen("taopapp.out", "w", stdout);
n = read(); m = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
Build(1, 1, n);
while (m--) {
int x = read(), y = read();
Change(1, 1, n, x, y);
printf("%d
", t[1]);
Change(1, 1, n, x, a[x]);
}
return 0;
}
Solve3
- 因为每次修改是不会对以后产生影响的，然后就写个主席树维护一下，修改之后下一次直接覆盖掉上一次操作，省掉一个Change，时间上会快一些.
Code
Show Code
#include <cstdio>
#include <algorithm>
#define ls t[rt].l
#define rs t[rt].r
const int N = 1e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
struct Tree {
int s, h, l, r;
}t[N*5];
int n, m, a[N], trc, root;
int Ask(int rt, int l, int r, int w) {
if (w >= t[rt].h) return 0;
if (l == r) return 1;
int mid = l + r >> 1;
if (w >= t[ls].h) return Ask(rs, mid + 1, r, w);
else return Ask(ls, l, mid, w) + t[rt].s - t[ls].s;
}
void Build(int &rt, int l, int r) {
rt = ++trc;
if (l == r) return t[rt].s = 1, t[rt].h = a[l], void();
int mid = l + r >> 1;
Build(ls, l, mid);
Build(rs, mid + 1, r);
t[rt].s = t[ls].s + Ask(rs, mid + 1, r, t[ls].h);
t[rt].h = std::max(t[ls].h, t[rs].h);
}
void Change(int &rt, int l, int r, int x, int w) {
t[++trc] = t[rt]; rt = trc;
if (l == r) return t[rt].h = w, void();
int mid = l + r >> 1;
if (x <= mid) Change(ls, l, mid, x, w);
else Change(rs, mid + 1, r, x, w);
t[rt].s = t[ls].s + Ask(rs, mid + 1, r, t[ls].h);
t[rt].h = std::max(t[ls].h, t[rs].h);
}
int main() {
freopen("taopapp.in", "r", stdin);
freopen("taopapp.out", "w", stdout);
n = read(); m = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
Build(root, 1, n);
while (m--) {
int x = read(), y = read();
trc = n * 4 + 1;
Change(root = 1, 1, n, x, y);
printf("%d
", t[root].s);
}
return 0;
}