线段树学习笔记 - 练习题（3）

1. 前言

线段树系列文章：

• 线段树学习笔记。
• 线段树学习笔记 - 练习题（1）。
• 线段树学习笔记 - 练习题（2）。

前一篇做了几道线段树的题目，这篇文章就继续看下线段树的相关题目，还是一样，学习视频：算法讲解113【扩展】线段树专题4-线段树解决区间合并的问题，题目都是左神视频上的，思路也可以看这个视频。

2. 线段树维护区间合并问题

假设现在有一个题目，给定一个长度为 n 的数组 arr，内部只有 0 和 1 两种值，下标从 1 开始，现在需要维护 [l，r] 范围上面连续 1 的最长子串长度，那么这个要怎么维护。

首先最长连续 1 这个事，父亲节点能不能根据子节点来得到，假设我们现在可以通过 max 数组维护左右两个子节点的最长连续 1。答案是不可以，比如下面的情况。

左子节点是 1111000111，最大连续 1 的子串长度是 4，右子节点是 11100011111，最大连续 1 的子串长度是 5，但是汇总之后父结点 max[i] = 6，就是左串和右串拼起来之后中间那一段 1 也拼起来了，所以可以看到只通过一个数组是不可以完成最长连续 1 的维护问题的。

既然用一个数组没办法解决这个事，我们就用三个数组去维护，len 数组维护连续 1 的最长子串长度，pre 维护连续 1 的最长前缀，suf 维护连续 1 的最长后缀，定义好之后下面的线段树就是这样的。

可以看到，对于左节点 pre[l] = 4，suf[l] = 3，len[l]= 4，对于右节点 pre[r] = 3，suf[r] = 5，len[r] = 5。那么父结点的这三个数组需要怎么维护呢？最直观看着就是：

• pre[i] = pre[l] = 5
• suf[i] = suf[r] = 5
• len[l] = Math.max(len[l]，Math.max(len[r]，suf[l] + pre[r])) = 6

这样直观看起来确实没什么问题，父结点的最长前缀就取左节点的 pre[l] 值，最长后缀就取右节点的 suf[r] 值，然后最长长度分别取左右节点的 len 以及左节点的 suf[l] 加上右节点的 pre[r] 作比较取最大值，实际上 len 这样取是没问题的，但是 pre 和 suf 还得再加工一下，比如遇到下面这种情况。

可以看到左节点全部都是 1，这种情况下 pre[l] = suf[l] = len[l] = 10，那么更新父结点的 pre 的时候就不能简单设置 pre[i] = pre[l]，还得加上 pre[r]，所以可以这么写：pre[i] = pre[l] < ln ? pre[l] : pre[l] + pre[r]，然后更新 suf[i] 可以写成：suf[i] = suf[r] < rn ? suf[r] : suf[l] + suf[r]，更新 len[i] 还是一样，不需要变，这样我们就更新好了这个线段树。

3. 洛谷 P2572 [SCOI2010] 序列操作

P2572 [SCOI2010] 序列操作

题目描述

lxhgww 最近收到了一个 $01$ 序列，序列里面包含了 $n$ 个数，下标从 $0$ 开始。这些数要么是 $0$，要么是 $1$，现在对于这个序列有五种变换操作和询问操作：

• 0 l r 把 $[l,r]$ 区间内的所有数全变成 $0$；
• 1 l r 把 $[l,r]$ 区间内的所有数全变成 $1$；
• 2 l r 把 $[l,r]$ 区间内的所有数全部取反，也就是说把所有的 $0$ 变成 $1$，把所有的 $1$ 变成 $0$；
• 3 l r 询问 $[l,r]$ 区间内总共有多少个 $1$；
• 4 l r 询问 $[l,r]$ 区间内最多有多少个连续的 $1$。

对于每一种询问操作，lxhgww 都需要给出回答，聪明的程序员们，你们能帮助他吗？

输入格式

第一行两个正整数 $n,m$，表示序列长度与操作个数。
第二行包括 $n$ 个数，表示序列的初始状态。
接下来 $m$ 行，每行三个整数，表示一次操作。

输出格式

对于每一个询问操作，输出一行一个数，表示其对应的答案。

输入输出样例 #1

输入 #1

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

输出 #1

5
2
6
5

说明/提示

【数据范围】
对于 $30\%$ 的数据，$1\le n,m\le 1000$；
对于$100\%$ 的数据，$1\le n,m\le 10^5$。

思路：

这道题就是相当于范围重置和范围取反，维护连续 1 的最长子串长度，由于设计到范围取反，因此我们不单单要维护连续 1 的最长长度，也需要维护连续 0 的最长长度，因此定义 6 个数组 pre1、suf1、len1、pre0、suf0、len0，前三个数组就是用来维护连续 1 的最长长度，后面三个数组用来维护连续 0 的最长长度。

接下来操作 0 和 操作 1 要维护范围更新，因此需要定义 update 和 change 数组来进行懒更新，然后取反也要定义 reverse 来懒更新，最后 sum 数组来维护区间 1 的累加和，用来解决操作 3，那么这几个数组懒更新的时候如何处理。

首先是 sum 数组，如果是范围修改，比如某个范围修改成 0，那么 sum[i] = 0，如果修改成 1，那么 sum[i] = cnt，cnt 就是这个范围的数字个数，所以可以 O(1) 时间完成更新，而范围取反就是 sum[i] = cnt - sum[i]。然后就是上面这 6 个数组，范围更新如果更新成 0，那么 pre0[i] = suf0[i] = len0[i] = cnt，pre1[i] = suf1[i] = len1[i] = 0，如果更新成 1，那么 pre0[i] = suf0[i] = len0[i] = 0，pre1[i] = suf1[i] = len1[i] = cnt。

然后是范围反转，上面说过 sum[i] 的更新了，而 pre、suf、len 三个就是 0 和 1 的交换，使用下面的方法。

private static void lazyReverse(int i, int cnt) {sum[i] = cnt - sum[i];reverse(len0, len1, i);reverse(pre0, pre1, i);reverse(suf0, suf1, i);reverse[i] = !reverse[i];
}private static void reverse(int[] arr0, int[] arr1, int i) {int temp = arr0[i];arr0[i] = arr1[i];arr1[i] = temp;
}

最后来看下整体的 code。

import java.io.*;public class Main {public static int MAXN = 100001;public static int[] arr = new int[MAXN];public static int[] sum = new int[MAXN << 2];public static int[] len0 = new int[MAXN << 2];public static int[] pre0 = new int[MAXN << 2];public static int[] suf0 = new int[MAXN << 2];public static int[] len1 = new int[MAXN << 2];public static int[] pre1 = new int[MAXN << 2];public static int[] suf1 = new int[MAXN << 2];public static int[] change = new int[MAXN << 2];public static boolean[] update = new boolean[MAXN << 2];public static boolean[] reverse = new boolean[MAXN << 2];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int m = (int) in.nval;for (int i = 1; i <= n; i++) {in.nextToken();arr[i] = (int) in.nval;}build(1, n, 1);for (int i = 1, op, jobl, jobr; i <= m; i++) {in.nextToken();op = (int) in.nval;in.nextToken();jobl = (int) in.nval + 1;in.nextToken();jobr = (int) in.nval + 1;if (op == 0) {update(jobl, jobr, 0, 1, n, 1);} else if (op == 1) {update(jobl, jobr, 1, 1, n, 1);} else if (op == 2) {reverse(jobl, jobr, 1, n, 1);} else if (op == 3) {out.println(querySum(jobl, jobr, 1, n, 1));} else {out.println(queryLongest(jobl, jobr, 1, n, 1)[0]);}}out.flush();out.close();br.close();}private static int[] queryLongest(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return new int[]{len1[i], pre1[i], suf1[i]};}int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);if (jobr <= mid) {return queryLongest(jobl, jobr, l, mid, i << 1);}if (jobl > mid) {return queryLongest(jobl, jobr, mid + 1, r, i << 1 | 1);}int[] l3 = queryLongest(jobl, jobr, l, mid, i << 1);int[] r3 = queryLongest(jobl, jobr, mid + 1, r, i << 1 | 1);int lenMax = Math.max(l3[0], Math.max(r3[0], l3[2] + r3[1]));int preMax = l3[0] < mid - Math.max(jobl, l) + 1 ? l3[1] : l3[1] + r3[1];int sufMax = r3[0] < Math.min(jobr, r) - mid ? r3[2] : l3[2] + r3[2];return new int[]{lenMax, preMax, sufMax};}private static int querySum(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);int res = 0;if (jobl <= mid) {res += querySum(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {res += querySum(jobl, jobr, mid + 1, r, i << 1 | 1);}return res;}private static void reverse(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazyReverse(i, r - l + 1);} else {int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);if (jobl <= mid) {reverse(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {reverse(jobl, jobr, mid + 1, r, i << 1 | 1);}up(i, mid - l + 1, r - mid);}}private static void update(int jobl, int jobr, int jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazyUpdate(i, jobv, r - l + 1);} else {int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);if (jobl <= mid) {update(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {update(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i, mid - l + 1, r - mid);}}private static void build(int l, int r, int i) {if (l == r) {sum[i] = arr[l];pre0[i] = len0[i] = suf0[i] = arr[l] == 0 ? 1 : 0;pre1[i] = len1[i] = suf1[i] = arr[l] == 0 ? 0 : 1;} else {int mid = l + ((r - l) >> 1);build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i, mid - l + 1, r - mid);}reverse[i] = false;update[i] = false;}private static void up(int i, int ln, int rn) {int l = i << 1;int r = i << 1 | 1;sum[i] = sum[i << 1] + sum[i << 1 | 1];len0[i] = Math.max(Math.max(len0[l], len0[r]), suf0[l] + pre0[r]);pre0[i] = pre0[l] < ln ? pre0[l] : pre0[l] + pre0[r];suf0[i] = suf0[r] < rn ? suf0[r] : suf0[l] + suf0[r];len1[i] = Math.max(Math.max(len1[l], len1[r]), suf1[l] + pre1[r]);pre1[i] = pre1[l] < ln ? pre1[l] : pre1[l] + pre1[r];suf1[i] = suf1[r] < rn ? suf1[r] : suf1[l] + suf1[r];}private static void down(int i, int ln, int rn) {// 由于懒更新会把懒重置给覆盖掉, 所以先处理懒更新的逻辑if (update[i]) {lazyUpdate(i << 1, change[i], ln);lazyUpdate(i << 1 | 1, change[i], rn);update[i] = false;}// 如果有 reverse 的再处理 reverse, 免得这个 reverse 被上面的 update 给覆盖掉if (reverse[i]) {lazyReverse(i << 1, ln);lazyReverse(i << 1 | 1, rn);reverse[i] = false;}}private static void lazyReverse(int i, int cnt) {sum[i] = cnt - sum[i];reverse(len0, len1, i);reverse(pre0, pre1, i);reverse(suf0, suf1, i);reverse[i] = !reverse[i];}private static void reverse(int[] arr0, int[] arr1, int i) {int temp = arr0[i];arr0[i] = arr1[i];arr1[i] = temp;}// 懒更新会把懒反转都给重置掉, 因为懒更新会把这个范围的所有数字都修改成 1 或者 0，修改之后 reverse 跟没 reverse 是一样的private static void lazyUpdate(int i, int v, int cnt) {sum[i] = v * cnt;len0[i] = pre0[i] = suf0[i] = v == 0 ? cnt : 0;len1[i] = pre1[i] = suf1[i] = v == 1 ? cnt : 0;update[i] = true;change[i] = v;// 重置 reverse 操作reverse[i] = false;}
}

4. 洛谷 P6492 [COCI 2010/2011 #6] STEP

P6492 [COCI 2010/2011 #6] STEP

题目描述

给定一个长度为 $n$ 的字符序列 $a$，初始时序列中全部都是字符 L。

有 $q$ 次修改，每次给定一个 $x$，若 $a_x$ 为 L，则将 $a_x$ 修改成 R，否则将 $a_x$ 修改成 L。

对于一个只含字符 L，R 的字符串 $s$，若其中不存在连续的 L 和 R，则称 $s$ 满足要求。

每次修改后，请输出当前序列 $a$ 中最长的满足要求的连续子串的长度。

输入格式

第一行有两个整数，分别表示序列的长度 $n$ 和修改操作的次数 $q$。

接下来 $q$ 行，每行一个整数，表示本次修改的位置 $x$。

输出格式

对于每次修改操作，输出一行一个整数表示修改 $a$ 中最长的满足要求的子串的长度。

输入输出样例 #1

输入 #1

6 2
2
4

输出 #1

3
5

输入输出样例 #2

输入 #2

6 5
4
1
1
2
6

输出 #2

3
3
3
5
6

说明/提示

数据规模与约定

对于全部的测试点，保证 $1\le n,q\le 2\times 10^5$，$1\le x\le n$。

思路：

这道题跟上面维护最长连续 1 的最长长度差不多，只是这里换成了维护 LRLR… 交替子串的最长长度，还是一样定义三个数组 pre、len、suf 来存储 最长前缀、最长长度、最长后缀。

思路跟上面第一小节介绍的是差不多的，这里求父结点的 pre、suf、len 值可以通过下面的方法来求。

private static void up(int l, int r, int i) {len[i] = Math.max(len[i << 1], len[i << 1 | 1]);pre[i] = pre[i << 1];suf[i] = suf[i << 1 | 1];int mid = l + ((r - l) >> 1);int ln = mid - l + 1;int rn = r - mid;if (arr[mid] != arr[mid + 1]) {len[i] = Math.max(len[i], suf[i << 1] + pre[i << 1 | 1]);if (pre[i] == ln) {pre[i] += pre[i << 1 | 1];}if (suf[i] == rn) {suf[i] += suf[i << 1];}}
}

还是一样，这里求出中点，然后判断下 arr[mid] != arr[mid + 1]，如果不相同说明左节点的后缀和右节点的前缀能连到一起，这种情况下才更新 len[i] = Math.max(len[i], suf[i << 1] + pre[i << 1 | 1])，pre 和 suf 也是一样的，当 arr[mid] != arr[mid + 1] 才考虑如果 pre[i] == len 的情况下要不要跟右边的拼在一起，比如下面的情况就拼不起来。

这种情况下由于 mid 和 mid + 1 都是 R，那么父结点的 pre 就不用拼接了，这是因为 pre 和 suf 和 len 交替子串最少都是 1，不像上面的最长连续 1 可以为 0，下面再来看下 code。

import java.io.*;public class Main {public static int MAXN = 200001;public static int[] arr = new int[MAXN];public static int[] len = new int[MAXN << 2];public static int[] pre = new int[MAXN << 2];public static int[] suf = new int[MAXN << 2];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int q = (int) in.nval;build(1, n, 1);for (int i = 1; i <= q; i++) {in.nextToken();int index = (int) in.nval;reverse(index, 1, n, 1);out.println(len[1]);}out.flush();out.close();br.close();}private static void reverse(int jobi, int l, int r, int i) {if(l == r){arr[jobi] ^= 1;} else {int mid = l + ((r - l) >> 1);if (jobi <= mid) {reverse(jobi, l, mid, i << 1);} else {reverse(jobi, mid + 1, r, i << 1 | 1);}up(l, r, i);}}private static void build(int l, int r, int i) {if (l == r) {len[i] = pre[i] = suf[i] = 1;} else {int mid = l + ((r - l) >> 1);build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(l, r, i);}}private static void up(int l, int r, int i) {len[i] = Math.max(len[i << 1], len[i << 1 | 1]);pre[i] = pre[i << 1];suf[i] = suf[i << 1 | 1];int mid = l + ((r - l) >> 1);int ln = mid - l + 1;int rn = r - mid;if (arr[mid] != arr[mid + 1]) {len[i] = Math.max(len[i], suf[i << 1] + pre[i << 1 | 1]);if (pre[i] == ln) {pre[i] += pre[i << 1 | 1];}if (suf[i] == rn) {suf[i] += suf[i << 1];}}}}

5. 洛谷 P1503 鬼子进村

P1503 鬼子进村

题目背景

小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。

题目描述

县城里有 $n$ 个用地道相连的房子，第 $i$ 个只与第 $i-1$ 和第 $i+1$ 个相连。这时有 $m$ 个消息依次传来：

1. 若消息为 D x：鬼子将 $x$ 号房子摧毁了，地道被堵上。

2. 若消息为 R：村民们将鬼子上一个摧毁的房子修复了。

3. 若消息为 Q x：有一名士兵被围堵在 $x$ 号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，有如题目所说的三种信息共 $m$ 条。

输出格式

对于每一个被围堵的士兵，输出该士兵能够到达的房子数。

输入输出样例 #1

输入 #1

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

输出 #1

1
0
2
4

说明/提示

$1\le n,m\le 5\times 10^4$。

若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。

思路：

首先一开始有 n 个房子连成一排，然后每个房子两边都有地道，意思就是如果当前下标为 1，并且旁边的 i - 1 和 i + 1 也是 1，就可以把这个 i - 1，i，i + 1 看成一个整体。

有几个操作，首先是 D x，这个操作意思是将 x 下标的值标为 0，然后是 R，R 是把上一次设置为 0 的房子重新设置为 1，最后是 Q x，就是查询包含整个房子在内的最长连续 1 的长度。

那这么看就还是一样需要维护最长连续 1 的长度了，不过有点特殊的是这里我们使用 pre 和 suf 数组就可以了，因为要求的是包括 x 在内的最长连续 1 的长度，而不是某个范围的最长连续 1 的长度，比如下面的情况。

由于求出来的连续 1 的长度不是最长连续子串长度，所以不能像上面几个题目那样求，那么这个要如何处理，还是一样遍历，这里我们从中点开始入手，下面原数组下标我画成了从 0 开始，线段树还是从 1 开始算的。

直接从 mid 开始判断，如果在 (mid - suf[i << 1]，mid] 这个范围，那么直接返回 suf[i << 1] + pre[i << 1 | 1]，这是因为如果在这个范围内，那么说明这个范围全部都是 1，而且包含了我们要求的 x，也就是从 x 出发最少都能到 mid - suf[i << 1] + 1 的位置，因此直接返回 suf[i << 1] + pre[i << 1 | 1]，为什么是 + 1，看上面图就可以了，mid 在左节点的最后一个位置，所以假设（上面图左节点最后一个数字换成 1）现在 mid = 4，然后 suf[i << 1] = 1，这时候 4 - 1 = 3，如果是包含了 mid - suf[i << 1]，那么假设这时候 x = 3，这种情况下由于下标 3 是 0，是不可以跟后面的连成一片的，这种情况下返回 suf[i << 1] + pre[i << 1 | 1] 就有问题了，因此左端点不能要，右边也是同理，然后看下 query 的 code，可以自己推导下就知道了。

private static int query(int x, int l, int r, int i) {if (l == r) {return pre[i];}int mid = l + ((r - l) >> 1);if (x <= mid) {// 如果 x 在 (mid - suf[i << 1, mid] 范围if (x > mid - suf[i << 1]) {// 返回左节点的后缀 + 右节点的前缀return suf[i << 1] + pre[i << 1 | 1];} else {// 这里就继续到前面去找return query(x, l, mid, i << 1);}} else {// 如果 x 在 [mid, mid + pre[i << 1 | 1]] 范围if(x <= mid + pre[i << 1 | 1]){// 返回左节点的后缀 + 右节点的前缀return suf[i << 1] + pre[i << 1 | 1];} else {// 否则就继续到右边二分查找return query(x, mid + 1, r, i << 1 | 1);}}
}

然后再来看下如何将上一次摧毁的房子恢复，这种情况下可以使用栈结构来完成，每一次调用 D x 就把 x 入栈，然后 stackSize++，然后调用 R 就把 --stackSize 下标的值弹出来恢复，下面看下整体 code。

import java.io.*;public class Main {public static int MAXN = 50001;public static int[] pre = new int[MAXN << 2];public static int[] suf = new int[MAXN << 2];public static int[] stack = new int[MAXN];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() != StreamTokenizer.TT_EOF) {int n = (int) in.nval;in.nextToken();int m = (int) in.nval;build(1, n, 1);String op;int stackSize = 0;for (int i = 1, x; i <= m; i++) {in.nextToken();op = in.sval;if (op.equals("D")) {in.nextToken();x = (int) in.nval;// 将 x 下标的值更新为 0update(x, 0, 1, n, 1);// 入栈stack[stackSize++] = x;} else if (op.equals("R")) {// 弹出下标值更新为 1update(stack[--stackSize], 1, 1, n, 1);} else {in.nextToken();x = (int) in.nval;// 查询包括 x 在内的最长连续 1 out.println(query(x, 1, n, 1));}}}out.flush();out.close();br.close();}private static int query(int x, int l, int r, int i) {if (l == r) {return pre[i];}int mid = l + ((r - l) >> 1);if (x <= mid) {// 如果 x 在 (mid - suf[i << 1, mid] 范围if (x > mid - suf[i << 1]) {// 返回左节点的后缀 + 右节点的前缀return suf[i << 1] + pre[i << 1 | 1];} else {// 这里就继续到前面去找return query(x, l, mid, i << 1);}} else {// 如果 x 在 [mid, mid + pre[i << 1 | 1]] 范围if(x <= mid + pre[i << 1 | 1]){// 返回左节点的后缀 + 右节点的前缀return suf[i << 1] + pre[i << 1 | 1];} else {// 否则就继续到右边二分查找return query(x, mid + 1, r, i << 1 | 1);}}}private static void update(int x, int jobv, int l, int r, int i) {if (l == r) {pre[i] = jobv;suf[i] = jobv;} else {int mid = l + ((r - l) >> 1);if (x <= mid) {update(x, jobv, l, mid, i << 1);} else {update(x, jobv, mid + 1, r, i << 1 | 1);}up(l, r, i);}}private static void build(int l, int r, int i) {if (l == r) {pre[i] = suf[i] = 1;} else {int mid = l + ((r - l) >> 1);build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(l, r, i);}}private static void up(int l, int r, int i) {pre[i] = pre[i << 1];suf[i] = suf[i << 1 | 1];int mid = l + ((r - l) >> 1);if (pre[i << 1] == mid - l + 1) {pre[i] += pre[i << 1 | 1];}if (suf[i << 1 | 1] == r - mid) {suf[i] += suf[i << 1];}}
}

6. P2894 [USACO08FEB] Hotel G

P2894 [USACO08FEB] Hotel G

题目描述

对一家有 $n$ 个房间（编号为 $1\sim n$，开始都为空房）的宾馆维护以下操作：

• 查询房间：你需要在 $1,2,\dots ,n$ 房间中找到长度为 $x$ 的连续空房。若找得到，在这 $x$ 个空房间中住上人。
• 退房：房间号 $x\sim x+y-1$ 退房，即让房间为空。

输入格式

第一行输入 $n,m$，$n$ 代表有 $n$ 个房间 $(1\le n\le 50,000)$，编号为 $1\sim n$，开始都为空房，$m$ 表示以下有 $m$ 行操作 $(1\le m<50,000)$，以下每行先输入一个数 $i$，表示一种操作：

若 $i$ 为 $1$，表示查询房间，再输入一个数 $x$。

若 $i$ 为 $2$，表示退房，再输入两个数 $x,y$。

输出格式

对每个输入 $1$，输出连续 $x$ 个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为 $x$ 的连续空房，输出 $0$。

输入输出样例 #1

输入 #1

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

输出 #1

1
4
7
0
5

思路：

这道题主要就是范围更新维护连续最长 1，因此需要三个数组 len、pre、suf，然后范围更新需要两个数组 update、change。

操作 2 意思就是把 [x，x + y - 1] 范围下标设置为 0，操作 1 意思是判断整个数组上有没有长度 >= x 的子数组，如果有多个就返回最左边的子数组的最左的编号 i，并且从整个编号开始将 [i，i + x - 1] 范围修改为 1，表示入住了。

这道题和上面第 5 小节的题目差不多，首先判断数组上有没有长度 >= x 的子数组，这个直接通过 len[1] 判断就行，然后就是最核心的 query 方法，如何查询出满足 >= x 的最左区域的最左边的值。

private static int query(int x, int l, int r, int i) {if (l == r) {return l;}int mid = l + ((r - l) >> 1);down(l, r, i);// 如果左节点上面有符合的区域if (len[i << 1] >= x) {// 往左边去遍历return query(x, l, mid, i << 1);}// 如果左边没有, 那么看看中间拼起来能不能满足if (suf[i << 1] + pre[i << 1 | 1] >= x) {// 如果可以满足就直接返回中间这个区域的左端点return mid - suf[i << 1] + 1;}// 再去右边去找return query(x, mid + 1, r, i << 1 | 1);
}

由于要找到最左的区域，所以一进来判断就是先判断左边的节点有没有符合条件的区域，再判断中间拼起来的区域能不能满足条件，如果都没有再去右边找，好了，下面看下全部的 code。

import java.io.*;public class Main {public static int MAXN = 50001;public static int[] len = new int[MAXN << 2];public static int[] pre = new int[MAXN << 2];public static int[] suf = new int[MAXN << 2];public static boolean[] update = new boolean[MAXN << 2];public static int[] change = new int[MAXN << 2];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int m = (int) in.nval;build(1, n, 1);for (int i = 1; i <= m; i++) {in.nextToken();int op = (int) in.nval;if (op == 1) {in.nextToken();int x = (int) in.nval;int idx = 0;if (len[1] < x) {out.println(idx);} else {// 到这里肯定能找到一个区域满足长度 >= x，所以查询到的idx = query(x, 1, n, 1);update(1, idx, idx + x - 1, 1, n, 1);out.println(idx);}} else {in.nextToken();int x = (int) in.nval;in.nextToken();int y = (int) in.nval;// 不能超过数组长度 update(0, x, Math.min(x + y - 1, n), 1, n, 1);}}out.flush();out.close();br.close();}private static int query(int x, int l, int r, int i) {if (l == r) {return l;}int mid = l + ((r - l) >> 1);down(l, r, i);// 如果左节点上面有符合的区域if (len[i << 1] >= x) {// 往左边去遍历return query(x, l, mid, i << 1);}// 如果左边没有, 那么看看中间拼起来能不能满足if (suf[i << 1] + pre[i << 1 | 1] >= x) {// 如果可以满足就直接返回中间这个区域的左端点return mid - suf[i << 1] + 1;}// 再去右边去找return query(x, mid + 1, r, i << 1 | 1);}private static void update(int jobv, int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazyUpdate(jobv, i, r - l + 1);} else {down(l, r, i);int mid = l + ((r - l) >> 1);if (jobl <= mid) {update(jobv, jobl, jobr, l, mid, i << 1);}if (jobr > mid) {update(jobv, jobl, jobr, mid + 1, r, i << 1 | 1);}up(l, r, i);}}private static void down(int l, int r, int i) {if (update[i]) {int mid = l + ((r - l) >> 1);lazyUpdate(change[i], i << 1, mid - l + 1);lazyUpdate(change[i], i << 1 | 1, r - mid);change[i] = 0;update[i] = false;}}private static void lazyUpdate(int jobv, int i, int ln) {change[i] = jobv;update[i] = true;pre[i] = suf[i] = len[i] = jobv == 0 ? ln : 0;}private static void build(int l, int r, int i) {if (l == r) {len[i] = pre[i] = suf[i] = 1;} else {int mid = l + ((r - l) >> 1);build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(l, r, i);}update[i] = false;change[i] = 0;}private static void up(int l, int r, int i) {len[i] = Math.max(len[i << 1], Math.max(len[i << 1 | 1], suf[i << 1] + pre[i << 1 | 1]));pre[i] = pre[i << 1];suf[i] = suf[i << 1 | 1];int mid = l + ((r - l) >> 1);if (pre[i] == mid - l + 1) {pre[i] += pre[i << 1 | 1];}if (suf[i] == r - mid) {suf[i] += suf[i << 1];}}}

如有错误，欢迎指出！！！