线段树的区间更新，线段树的区间合并，面积并与周长并
前言
这线段树让人头大_(:з」∠)_
- 扫描线 —— 面积并
https://blog.csdn.net/u012860063/article/details/43163949
https://blog.csdn.net/qq_18661257/article/details/47622677
https://blog.csdn.net/qq_18661257/article/details/47658191 - 扫描线 —— 周长并
http://www.cnblogs.com/scau20110726/archive/2013/04/13/3018687.html
一些疑难点
- 在扫描线中，为何用左闭右开区间？
个人认为是为了能计算连续线段长度。比方说，现在有两段[1,2],[2,4]，其在线段树中是不能表示的，因为2这一点共点了，而线段树同层的区间端点都是分隔开来的，但是如果用[1,2)和[2,4)，那就可以在线段树中表示了，当然开区间线段树不能表示，所以转换为[1,1]和[2,3]，然后在计算长度时取 r - l + 1即可。
线段树的区间修改 - HihoCoder 1078
思路
区间更新的教程 + 模板题
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = 1e5 + 15;
int sum[N << 2], lzytag[N << 2];
int a[N];
void pushUp(int rt){ sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
void pushDown(int rt, int rag){
if(lzytag[rt]){
lzytag[rt << 1] = lzytag[rt << 1 | 1] = lzytag[rt];
sum[rt << 1] = lzytag[rt] * (rag - (rag >> 1));
sum[rt << 1 | 1] = lzytag[rt] * (rag >> 1);
lzytag[rt] = 0;
}
}
void build(int l, int r, int rt){
lzytag[rt] = 0;
if(l == r){
sum[rt] = a[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt);
}
void update(int ql, int qr, int val, int l, int r, int rt){
if(ql <= l && r <= qr){
sum[rt] = val*(r - l + 1);
lzytag[rt] = val;
return;
}
pushDown(rt, r - l + 1);
int m = (l + r) >> 1;
if(ql <= m) update(ql, qr, val, lson);
if(qr > m) update(ql, qr, val, rson);
pushUp(rt);
}
int query(int ql, int qr, int l, int r, int rt){
if(ql <= l && r <= qr){
return sum[rt];
}
pushDown(rt, r - l + 1);
int ans = 0;
int m = (l + r) >> 1;
if(ql <= m) ans += query(ql, qr, lson);
if(qr > m) ans += query(ql, qr, rson);
return ans;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); }
build(1, n, 1);
int q;
scanf("%d", &q);
while(q--){
int op, l, r, val;
scanf("%d%d%d", &op, &l, &r);
if(op == 1){
scanf("%d", &val);
update(l, r, val, 1, n, 1);
}else{
printf("%d\n", query(l, r, 1, n, 1));
}
}
}
Mayor’s posters - POJ 2528
思路
线段树 + 离散化 + 区间更新
数据的范围给的很大，但是数据量不大，所以需要考虑用离散化的方式把数据存起来，具体做法是开一个数组存放数据，而不是直接用下标表示数据
这里特别注意，对于这种离散化，需要在各点之间插入其他的点。比如：（1,10），（1,4），（7,10），这个样例中如果离散化后不插入其他的点，则答案会是2，因为离散后的坐标为1（1）,2（4）,3（7）,4（10），更改第二段第三段区间，修当于修改（1,2）和（3,4），于是5,6两点不见了，最后的答案就会是2。如果插入其他的点，使得变为（1,2,4,5,7,8,10），就不会出现这样的情况，能够算出答案是3。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
int sum[N << 2], lzytag[N << 2];
int li[N], ri[N];
int xx[N];
set<int> st;
void pushDown(int rt){
if(lzytag[rt]){
lzytag[rt << 1] = lzytag[rt << 1 | 1] = lzytag[rt];
sum[rt << 1] = sum[rt << 1 | 1] = lzytag[rt];
lzytag[rt] = 0;
}
}
void build(int l, int r, int rt){
lzytag[rt] = 0;
if(l == r){
sum[rt] = 0;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
}
void update(int ql, int qr, int val, int l, int r, int rt){
if(ql <= l && r <= qr){
sum[rt] = val;
lzytag[rt] = val;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if(ql <= m) update(ql, qr, val, lson);
if(qr > m) update(ql, qr, val, rson);
}
void solve(int l, int r, int rt){
if(l == r){
st.insert(sum[rt]); //用set存答案，自带去重功能（就是耗时有点高）
return;
}
pushDown(rt);
int m = (l + r) >> 1;
solve(lson);
solve(rson);
}
int main(){
int t;
scanf("%d", &t);
while(t--){
st.clear();
int n;
int maxnum = -inf;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d%d", &li[i], &ri[i]);
maxnum = max(maxnum, max(li[i], ri[i]));
xx[2 * i - 1] = li[i]; //相当于Hash
xx[2 * i] = ri[i];
}
int tot = 2 * n;
// 下面这段注释取消才是正解，但是POJ会WA
// for(int i = 1; i <= 2 * n; i++){
// if(xx[i] != maxnum) xx[++tot] = xx[i] + 1;
// }
sort(xx + 1, xx + tot + 1);
tot = unique(xx + 1, xx + tot + 1) - xx - 1; //去重
build(1, tot, 1);
for(int i = 1; i <= n; i++){
int l = lower_bound(xx + 1, xx + tot + 1, li[i]) - xx; //二分查找Hash后的值
int r = lower_bound(xx + 1, xx + tot + 1, ri[i]) - xx;
update(l, r, i, 1, tot, 1);
}
solve(1, tot, 1);
printf("%d\n", (int)st.size());
}
}
Hotel - POJ 3667
思路
区间合并
线段树用于维护空房间的数量的最大值，并且在pushUp时需要维护空房间数量的最大值，最后query时优先访问左子树并更新
具体做法为：开lsum，rsum和msum数组，分别记录从左端点开始的最大值，右端点开始的最大值和该区段内的最大值，再通过递推更新，详细见代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = 5e4 + 15;
int msum[N << 2], lsum[N << 2], rsum[N << 2];
int lzytag[N << 2];
void pushUp(int rt, int rag){
//根据左右子树根据分别从左右端点出发的最大连续值
lsum[rt] = lsum[rt << 1];
rsum[rt] = rsum[rt << 1 | 1];
//可能还能够继续延伸
if(lsum[rt] == rag - (rag >> 1)) lsum[rt] += lsum[rt << 1 | 1];
if(rsum[rt] == (rag >> 1)) rsum[rt] += rsum[rt << 1];
//在左右子树最大值和自身中部分中取最大值
msum[rt] = max(rsum[rt << 1] + lsum[rt << 1 | 1], max(msum[rt << 1], msum[rt << 1 | 1]));
}
void pushDown(int rt, int rag){
if(lzytag[rt] != -1){
lzytag[rt << 1] = lzytag[rt << 1 | 1] = lzytag[rt];
if(lzytag[rt] == 0){ //全部更新为不可用（即空房间为0）
msum[rt << 1] = lsum[rt << 1] = rsum[rt << 1] = 0;
msum[rt << 1 | 1] = lsum[rt << 1 | 1] = rsum[rt << 1 | 1] = 0;
}else{ //更新空房间数量
msum[rt << 1] = lsum[rt << 1] = rsum[rt << 1] = rag - (rag >> 1);
msum[rt << 1 | 1] = lsum[rt << 1 | 1] = rsum[rt << 1 | 1] = (rag >> 1);
}
lzytag[rt] = -1;
}
}
void build(int l, int r, int rt){
lzytag[rt] = -1;
if(l == r){
msum[rt] = lsum[rt] = rsum[rt] = 1;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt, r - l + 1);
}
void update(int ql, int qr, int val, int l, int r, int rt){
if(ql <= l && r <= qr){
lsum[rt] = rsum[rt] = msum[rt] = val*(r - l + 1);
lzytag[rt] = val;
return;
}
pushDown(rt, r - l + 1);
int m = (l + r) >> 1;
if(ql <= m) update(ql, qr, val, lson);
if(qr > m) update(ql, qr, val, rson);
pushUp(rt, r - l + 1);
}
int query(int val, int l, int r, int rt){
if(l == r){
return l;
}
pushDown(rt, r - l + 1);
int m = (l + r) >> 1;
if(msum[rt << 1] >= val) return query(val, lson);
else if(rsum[rt << 1] + lsum[rt << 1 | 1] >= val) return m - rsum[rt << 1] + 1;
else return query(val, rson);
}
int main(){
int n, q;
while(~scanf("%d%d", &n, &q)){
build(1, n, 1);
while(q--){
int op, l, val;
scanf("%d", &op);
if(op == 1){
scanf("%d", &val);
if(msum[1] < val) puts("0");
else{
int p = query(val, 1, n, 1);
update(p, p + val - 1, 0, 1, n, 1); //0表示不可用
printf("%d\n", p);
}
}else{
scanf("%d%d", &l, &val);
update(l, l + val - 1, 1, 1, n, 1); //1表示可用
}
}
}
}
Atlantis - HDU 1542
思路
面积并模板题
（真的是模板题？？？）
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = 405;
struct segment{ //记录横边
double l, r, h; //记录改变的左边界、右边界和高
int s; //记录该边是上（-1）还是下（1）
segment() {}
segment(double pl, double pr, double ph, int ps): l(pl), r(pr), h(ph), s(ps) {}
bool operator < (const segment& b) const{
return h < b.h;
}
};
segment ss[N << 2];
int cnt[N << 2];
double xx[N], sum[N << 2];
inline void init(){
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(sum));
}
void pushUp(int rt, int l, int r){
if(cnt[rt]) sum[rt] = xx[r + 1] - xx[l]; //因为左闭右开，所以是 （r + 1) - l
else if(l == r) sum[rt] = 0; //无覆盖且l == r，自然sum为0
else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; //向上更新有效长度
}
void update(int ql, int qr, int val, int l, int r, int rt){
if(ql <= l && r <= qr){
cnt[rt] += val;
pushUp(rt, l, r);
return;
}
int m = (l + r) >> 1;
if(ql <= m) update(ql, qr, val, lson);
if(m < qr) update(ql, qr, val, rson);
pushUp(rt, l, r);
}
int main(){
int n;
int csn = 1;
while(scanf("%d", &n) && n){
init();
double ans = 0;
int tot = 0;
while(n--){
double x1, x2, y1, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
ss[tot] = segment(x1, x2, y1, -1);
xx[tot++] = x1;
ss[tot] = segment(x1, x2, y2, 1);
xx[tot++] = x2;
}
sort(ss, ss + tot);
sort(xx, xx + tot);
int k = unique(xx, xx + tot) - xx;
ss[tot] = ss[tot - 1];
for(int i = 0; i < tot - 1; i++){
int l = lower_bound(xx, xx + k, ss[i].l) - xx;
int r = lower_bound(xx, xx + k, ss[i].r) - xx - 1; //因为左闭右开，故减1
if(l <= r) update(l, r, ss[i].s, 0, k - 1, 1);
ans += sum[1] * (ss[i + 1].h - ss[i].h);
}
printf("Test case #%d\n", csn++);
printf("Total explored area: %.2f\n\n", ans);
}
}
Picture - HDU 1828
思路
周长并模板题
（真的是模板题？？？？？Excuse Me？？）
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = 2e4 + 15;
const int inf = 0x3f3f3f3f;
struct segment{
int l, r, h, s;
segment() {}
segment(int pl, int pr, int ph, int ps): l(pl), r(pr), h(ph), s(ps) {}
bool operator < (const segment& b) const{
if(h != b.h) return h < b.h;
else return s > b.s;
}
};
//cnt记录覆盖次数，len记录线段长度，numseg记录竖线数量，
//lbd、rbd记录是否竖线在左右端点
segment ss[N << 2];
int cnt[N << 2], len[N << 2], numseg[N << 2];
bool lbd[N << 2], rbd[N << 2];
inline int mabs(int x){ return x < 0 ? -x : x; }
inline void init(){
memset(cnt, 0, sizeof(cnt));
memset(len, 0, sizeof(len));
memset(numseg, 0, sizeof(numseg));
memset(lbd, 0, sizeof(lbd));
memset(rbd, 0, sizeof(rbd));
}
void pushUp(int rt, int l, int r){
if(cnt[rt]){ //被覆盖
len[rt] = r - l + 1; //因为用左闭右闭代表左闭右开，所以是r - l + 1
lbd[rt] = rbd[rt] = 1; //竖线存在于左右两端
numseg[rt] = 2;
}else if(l == r){ //没有覆盖，则都清0
len[rt] = numseg[rt] = 0;
lbd[rt] = rbd[rt] = 0;
}else{ //向上更新部分
lbd[rt] = lbd[rt << 1];
rbd[rt] = rbd[rt << 1 | 1];
len[rt] = len[rt << 1] + len[rt << 1 | 1];
numseg[rt] = numseg[rt << 1] + numseg[rt << 1 | 1];
//如果左子树的右线和右子树的左线同时存在，则说明在内部，numseg减去2
if(rbd[rt << 1] && lbd[rt << 1 | 1]) numseg[rt] -= 2;
}
}
void update(int ql, int qr, int val, int l, int r, int rt){
if(ql <= l && r <= qr){
cnt[rt] += val;
pushUp(rt, l, r);
return;
}
int m = (l + r) >> 1;
if(ql <= m) update(ql, qr, val, lson);
if(m < qr) update(ql, qr, val, rson);
pushUp(rt, l, r);
}
int main(){
int n;
while(~scanf("%d", &n)){
init();
int tot = 0;
while(n--){
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &y2, &x2, &y1);
ss[tot++] = segment(x1, x2, y1, -1);
ss[tot++] = segment(x1, x2, y2, 1);
}
sort(ss, ss + tot);
ss[tot] = ss[tot - 1];
int ans = 0, pre = 0;
for(int i = 0; i < tot; i++){
if(ss[i].l < ss[i].r) update(ss[i].l, ss[i].r - 1, ss[i].s, -10000, 10000 - 1, 1);
//竖线数量 * 横线之间的距离（高度）为本次覆盖的竖线
ans += numseg[1] * (ss[i + 1].h - ss[i].h);
//上一次覆盖横线与本次的差值为本次新增的覆盖横线
ans += abs(len[1] - pre);
pre = len[1];
}
printf("%d\n", ans);
}
}
