Kevin_K edited 6 年，1 月前
百度百科如是说道:线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。
为什么线段树对区间的处理有奇效呢?
我认为:这个区间应该更近一步理解为连续的区间(有不连续的区间吗?算了,不管了),线段树牺牲了一定的空间,使得树的每一个节点都对应了一个连续的区间,而且整个大区间的任意一个连续非空子区间都有一个节点与之对应,加之线段树的子节点一定是其父节点的子区间(也就是说一个节点的改变只可能改变它的”祖先”节点),这使得线段树对区间的统一处理能力非常强.而懒惰标记的使用进一步加强了线段树的效率!
1.t数组一般代表线段树数组.
2.MAXN:N(输入规模)的最大值.
3.base线段树叶子节点的基(就是下标最小的叶子节点的下标值)
4.前缀i-与输入有关(但不是与输入有关就一定有i-).
5.build函数,递归建树函数.
6.init函数,初始化函数.
7.cuttingRoot/cuttingLeaf,带懒惰标记的线段树题中必用的(?)向上/下更新的函数.
8.cuttingTree函数,更新线段树的函数.
9.find查询函数,由于返回答案.
10.killTheBoringProblem,辅助函数.(本文中用于计算整数二进制中一的个数)
11.flag数组,懒惰标记数组.
注:我会在这个重制版中尽量增加一些注解,但由于离写的时候有些时候了,所以难免有些错误.
和Ec1076#染气球很像?(不好意思,一点都不像,第一次写报告的时候脑抽了…)
由于是区间处理,所以线段树是要带懒惰标记的,T=30暗示了我们用int数的每个二进制位去映射区间内是否含有某种颜色.
这里有个坑点,由于我基于强迫症打的是满二叉树,所以init时要讲究一下范围.
还有以后一定要注意:数组范围一定要开足!
#include <stdio.h>
#include <algorithm>
const int MAXN = 1E5;
int t[MAXN * 4], flag[MAXN * 4], n, c, o, base, ix, iy, iz;
char s[8];//用string会炸?!所以用了C字符串.
void build(int e) {
if (e >= base) {
t[e] = n + base > e ? 1 : 0;
return;
}
build(e * 2 + 1);
build(e * 2 + 2);
t[e] = t[e * 2 + 1] | t[e * 2 + 2];
}
void init(int e) {
base = 1;
while (base < e) {
base *= 2;
}
base--;
build(0);
}
void cuttingRoot(int e) {
t[e] = t[e * 2 + 1] | t[e * 2 + 2];
}
void cuttingLeaf(int e) {
if (flag[e]) {
t[e * 2 + 1] = t[e * 2 + 2] = flag[e * 2 + 1] = flag[e * 2 + 2] = flag[e];
flag[e] = 0;
}
}
void cuttingTree(int p, int q, int l, int r, int e, int z) {
if (p > r || q < l) {
return;
}
if (p <= l && q >= r) {
t[e] = flag[e] = 1 << (z - 1);
return;
}
cuttingLeaf(e);
cuttingTree(p, q, l, (l + r) / 2, e * 2 + 1, z);
cuttingTree(p, q, (l + r) / 2 + 1, r, e * 2 + 2, z);
cuttingRoot(e);
}
int find(int p, int q, int l, int r, int e) {
if (p > r || q < l) {
return 0;
}
if (p <= l && r <= q) {
return t[e];
}
cuttingLeaf(e);
return find(p, q, l, (l + r) / 2, e * 2 + 1) | find(p, q, (l + r) / 2 + 1, r, e * 2 + 2);
}
int killTheBoringProblem(int e) {
return e ? e % 2 + killTheBoringProblem(e >> 1) : 0;
}
int main() {
scanf("%d%d%d", &n, &c, &o);//o是操作数.
init(n);
while (o--) {
scanf("%s%d%d", &s, &ix, &iy);
ix--;
iy--;
if (ix > iy) {
std::swap(ix, iy);//巨坑!天坑!!坑哭了!!!
}
if (s[0] - 'C') {
printf("%d\n", killTheBoringProblem(find(ix, iy, 0, base, 0)));
}
else {
scanf("%d", &iz);
cuttingTree(ix, iy, 0, base, 0, iz);
}
}
return 0;
}
最开始以为简单模拟能过,于是意料之内的TLE了,所以只能愉快的使用线段树了…
有一个性质是:最后加入的人的位置是确定的,所以只要从后往前填.(准确的说是前面的人无法影响后面来的人,但后面来的人可以影响前面的人,所以从后往前处理)
麻烦的地方是填了以后那个位置就没了,除去的位置不能填,怎么样将剩下的可以填的位置和一些位置禁用的(编号有效,但处理插入位置时却不能算)的位置处理好成为了核心矛盾.但线段树的威力就体现出来了,可以填就用1,不可以填就用0,这样找到结束下标最小的和为插入位置大小的从0开始的子段就可以找到答案了.(好像写的非常绕…抱歉)
#include <stdio.h>
const int MAXN = 200000;
int x[MAXN], y[MAXN], res[MAXN], t[MAXN * 4 - 1], base, n;//x,y存输入,因为要倒着处理...res存答案.
void build(int e) {
if (e >= base) {
t[e] = 1;
}
else {
build(e * 2 + 1);
build(e * 2 + 2);
t[e] = t[e * 2 + 1] + t[e * 2 + 2];
}
}
void init(int e) {
base = 1;
while (base < e) {
base *= 2;
}
base--;
build(0);
}
void cuttingTree(int e) {
if (!e) {
return;
}
t[(e - 1) / 2] = t[(e - 1) / 2 * 2 + 1] + t[(e - 1) / 2 * 2 + 2];
return cuttingTree((e - 1) / 2);
}
int find(int e, int sum) {
if (e >= base) {
return e - base;
}
if (t[2 * e + 1] >= sum) {
return find(2 * e + 1, sum);
}
return find(2 * e + 2, sum - t[2 * e + 1]);
}
int main() {
while (scanf("%d", &n) != EOF) {
for (int i = 1; i <= n; i++) {
scanf("%d%d", x + n - i, y + n - i);
x[n - i]++;
}
init(n);
for (int i = 0; i < n; i++) {
int v = find(0, x[i]);
res[v] = y[i];
t[base + v] = 0;
cuttingTree(base + v);
}
for (int i = 0; i < n; i++) {
printf("%d%c", res[i], i + 1 - n ? ' ' : '\n');
}
}
return 0;
}
线段树模板题…一个节点存(本题线段树的用两个数组来表示)当节点表示范围的头到尾的对应的点的向量的横纵坐标即可.因为向量只与起点和终点有关,而两个向量相加其实就是横坐标和纵坐标相加.(在笛卡尔坐标系下)所以转了一个角度只要改变最小包含转角的区间和它的”祖先”区间即可.
#include <cstdio>
#include <cmath>
const double PI = 3.141592653589;//自定义π的值.
const int SOT = (1 << 15) - 1;//size of tree的缩写,树的大小.
const int MAXN = 10000;//数据规模.
const int MAXC = 10000;//操作数.
int n, c, len[MAXN], s[MAXC], a[MAXC];//len记录长度,s,a记录输入.很玄学的是我尝试边输入边处理,结果TLE了???
double vx[SOT], vy[SOT], ang[SOT], prv[MAXN];//字面意思.
void init(int x, int l, int r) {
ang[x] = vx[x] = 0;
if (r - l - 1) {
init(x * 2 + 1, l, (l + r) / 2);
init(x * 2 + 2, (l + r) / 2, r);
vy[x] = vy[x * 2 + 1] + vy[x * 2 + 2];
}
else {
vy[x] = len[l];
}
}
void cuttingTree(int x, double y, int v, int l, int r) {
if (x > l && x < r) {
int chl = v * 2 + 1, chr = v * 2 + 2, mid = (l + r) / 2;
cuttingTree(x, y, chl, l, mid);
cuttingTree(x, y, chr, mid, r);
if (x <= mid) {
ang[v] += y;
}
double p = sin(ang[v]), q = cos(ang[v]);
vx[v] = vx[chl] + q * vx[chr] - p * vy[chr];//坐标系内改变向量所需公式.
vy[v] = vy[chl] + p * vx[chr] + q * vy[chr];//同上.
}
}
int main() {
while (scanf("%d%d", &n, &c) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%d", len + i);
}
for (int i = 0; i < c; i++) {
scanf("%d%d", s + i, a + i);
}
init(0, 0, n);
for (int i = 1; i < n; i++) {
prv[i] = PI;
}
for (int i = 0; i < c; i++) {
int x = s[i];
double y = a[i] / 180.0 * PI;
cuttingTree(x, y - prv[x], 0, 0, n);
prv[x] = y;
printf("%.2lf %.2lf\n", vx[0], vy[0]);
}
printf("\n");
}
return 0;
}
本题分析与前面那道需要使用懒惰标记的题相似的部分通通省略.
0.为什么选择线段树?因为这一讲是线段树!
1.怎么解决细分后连接的线段一分二的情况?
记录左右最长的空房长度!
2.怎么选择方向?
记录每个区间最长的空房长度.
3.最长空房怎么求?
DP父节点的最长长度等于子节点的最长长度的最大值或左儿子的右最长连续空房数加右儿子左边最长空房数.
4.为什么要懒惰(标记)?
因为是区间修改.
5.tree结构体里剩下的东西是什么?
我本来以为够了,但后来发现实现太困难,于是就疯狂牺牲空间…
6.为什么这个思路既视感很强?
不然呢?
#include <stdio.h>
const int MAXN = 50000;
int n, m, op, base, x, y;//op是操作模式.
struct tree {
int l, r, sl, sr, st, flag, len;
//l,r区间的左右端点,sl,sr,st是左,右最长空房和区间最长空房,flag懒惰标记类型,len区间长度.
} t[MAXN * 4];
int max(int l, int r) {
return l > r ? l : r;
}
void build(int e) {
t[e].flag = 0;
if (e >= base) {
t[e].len = t[e].sl = t[e].sr = t[e].st = base + n > e ? 1 : 0;
t[e].l = t[e].r = e - base;
}
else {
build(2 * e + 1);
build(2 * e + 2);
t[e].len = t[e].sl = t[e].sr = t[e].st = t[2 * e + 1].st + t[2 * e + 2].st;
t[e].l = t[e * 2 + 1].l;
t[e].r = t[e * 2 + 2].r;
}
}
void init(int e) {
base = 1;
while (base < e) {
base *= 2;
}
base--;
build(0);
}
void cuttingRoot(int l, int r, int e) {
t[e].sl = t[e * 2 + 1].sl;
t[e].sr = t[e * 2 + 2].sr;
int mid = (r + l) / 2;
if (t[e].sl == mid - l + 1) {
t[e].sl += t[e * 2 + 2].sl;
}
if (t[e].sr == r - mid) {
t[e].sr += t[e * 2 + 1].sr;
}
t[e].st = max(max(t[e * 2 + 1].st, t[e * 2 + 2].st), t[e * 2 + 1].sr + t[e * 2 + 2].sl);
}
void cuttingLeaf(int e) {
if (t[e].flag) {
t[e * 2 + 1].flag = t[e * 2 + 2].flag = t[e].flag;
if (t[e].flag == 1) {
t[e * 2 + 2].sl = t[e * 2 + 2].sr
= t[e * 2 + 2].st = t[e * 2 + 1].sl
= t[e * 2 + 1].sr = t[e * 2 + 1].st = 0;
}
else {
t[e * 2 + 2].sl = t[e * 2 + 2].sr
= t[e * 2 + 2].st = t[e * 2 + 1].sl = t[e * 2 + 1].sr
= t[e * 2 + 1].st = t[e * 2 + 1].len;
}
t[e].flag = 0;
}
}
int find(int l, int r, int e, int c) {
if (l == r) {
return l;
}
int mid = (l + r) / 2;
cuttingLeaf(e);
if (t[e * 2 + 1].st >= c) {
return find(l, mid, 2 * e + 1, c);
}
else if (t[e * 2 + 1].sr + t[e * 2 + 2].sl >= c) {
return mid - t[e * 2 + 1].sr + 1;
}
else {
return find(mid + 1, r, 2 * e + 2, c);
}
}
void cuttingTree(int l, int r, int e, int c) {
if (t[e].l == l && t[e].r == r) {
t[e].flag = c;
if (c == 1) {
t[e].sl = t[e].sr = t[e].st = 0;
}
else {
t[e].sl = t[e].sr = t[e].st = t[e].len;
}
return;
}
cuttingLeaf(e);
int mid = (t[e].l + t[e].r) / 2;
if (mid >= r) {
cuttingTree(l, r, 2 * e + 1, c);
}
else if (mid < l) {
cuttingTree(l, r, 2 * e + 2, c);
}
else {
cuttingTree(l, mid, 2 * e + 1, c);
cuttingTree(mid + 1, r, 2 * e + 2, c);
}
cuttingRoot(t[e].l, t[e].r, e);
}
int main() {
scanf("%d%d", &n, &m);
init(n);
for (int i = 0; i < m; i++) {
scanf("%d", &op);
if (op - 1) {
scanf("%d%d", &x, &y);
x--;
cuttingTree(x, y + x - 1, 0, -1);
}
else {
scanf("%d", &x);
if (t[0].st < x) {
printf("0\n");
continue;
}
y = find(0, base, 0, x);
printf("%d\n", y + 1);
cuttingTree(y, y + x - 1, 0, 1);
}
}
return 0;
}