• 基础线段树

    一、单点修改，区间查询

    （一）查询某区间内最大值：acwing最大数

    如果是静态问题，可以用RMQ（倍增）来写。
    单点修改可以不用懒标记，尽量不用，麻烦。
    线段树里的每一个点都是一个结构体，具体存什么根据题目而定：

    1. 问的是什么就存什么，比如【区间查询】问的就是某个区间的某种属性，就要存区间的左右端点位置和这个属性；
    2. 辅助信息，看一下当前属性能不能由两个子区间的属性算出来，如果不能就需要辅助信息

    递归建树，比如节点i的两个子区间分别是2i和2i+1，只有叶子节点被真实赋值：

    1. 从i=1开始建树
    2. 如果l=r，也就是叶子节点，就赋值，否则递归
    3. 维护，一般需要，偶尔建的树为空就不需要

    维护有两种，用子区间维护父亲区间（从下往上维护），用父亲区间维护子区间（从上往下维护）：

    1. 从下往上，pushup。找的时候从上往下找，找到底（叶子节点）并修改，修改完回溯，回溯的时候更新父节点的信息
    2. 从上往下，pushdown。把父节点的修改，更新到儿子节点上。

    单点修改：和建树一样用递归，从根节点1开始找要查询的叶子节点的位置，找到就修改，pushup更新父节点的信息。
    区间最值查询：一样用递归从1开始找，找到多个在区间内的树枝，对它们的属性求max。

    #include
#define ll long long
using namespace std;
struct Node {
	int l, r;
	int v;
} tr[200010 * 4];
ll n,m,p,last,t;
char op;
void build(int u, int l, int r) {
	tr[u].l=l,tr[u].r=r;
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1, l, mid);
	build(u<<1|1, mid+1, r);
}
int query(int u, int l, int r) {	//找所有完全包含的树枝 
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].v;
	int mid=(tr[u].l+tr[u].r)>>1;
	int v=0;
	if(l<=mid) v=query(u<<1, l, r);
	if(r>mid) v=max(v, query(u<<1|1, l, r));	//找到的各部分再求最大 
	return v;
}
void modify(int u) {	//找n+1这个叶子节点 
	if(tr[u].l==tr[u].r&&tr[u].l==n) tr[u].v=(last+t)%p;
	else {
		int mid=(tr[u].l+tr[u].r)>>1;
		if(n<=mid) modify(u<<1);
		else modify(u<<1|1);
		tr[u].v = max(tr[u<<1].v, tr[u<<1|1].v);	//修改后从下往上维护 
	}
}
int main() {
	scanf("%lld%lld",&m,&p);
	build(1,1,m);
	for(int i=1; i<=m; i++) {
		getchar();
		scanf("%c%lld",&op,&t);
		if(op=='A') {
			n++;
			modify(1);	//修改n+1 
		} else {
			last = query(1, n-t+1, n);	//[n-t+1, n]内最值 
			printf("%lld\n",last);
		}
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    （二）查询某区间内最大连续子段和：acwing你能回答这些问题吗

    结构体里如果只存左右端点和当前区间的最大连续子段和：当前区间的属性不能由左右两个子区间的属性得到。所以考虑如何用左右两个子区间的属性得到当前区间的属性：

    1. 左右区间的属性：lmax和rmax
    2. 跨两个区间的属性，左区间的后缀、右区间的前缀：l和r

    别忘了考虑新加的属性能不能直接求：

    1. 左右区间的最大连续子段和：可以直接根据左右子区间得到
    2. 包含左区间最后一个数的最大连续子段和、包含右区间第一个数的最大连续子段和。

    例如，对于当前区间，它的最大前缀和：它的左子区间的最大前缀和、它的左子区间和和它的右子区间的最大前缀和。它的最大后缀和同理。

    所以还有加上一个属性：区间和。
    所以要存：

    1. 区间左右端点位置：l和r
    2. 区间内的最大连续子段和：max
    3. 区间的最大连续前缀和、区间的最大连续后缀和：lx和rx
    4. 区间和：s

    修改和建树差不多，区别在于建树是修改所有叶子区间，而修改只需修改一个叶子区间
    查询，有两种思路。
    \quad 一是y总的四种情况，l \quad 二其实也是分四种情况，l 显然，y总的版本更快。

    #include
using namespace std;
struct T {
	int l,r,s,lx,rx,max;
};
T t[2000010];
int n,m,a[500010];
void build(int p, int l, int r) {	//建树 
	t[p].l=l,t[p].r=r;
	if(l==r) {
		t[p].s=t[p].lx=t[p].rx=t[p].max=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	//pushup
	t[p].s=t[p<<1].s+t[p<<1|1].s;
	t[p].lx=max(t[p<<1].lx,t[p<<1].s+t[p<<1|1].lx);
	t[p].rx=max(t[p<<1|1].rx,t[p<<1|1].s+t[p<<1].rx);
	t[p].max=max(max(t[p<<1].max,t[p<<1|1].max),t[p<<1].rx+t[p<<1|1].lx);
}
T ask(int p, int l, int r) {	//查询 
	if(l<=t[p].l&&t[p].r<=r) return t[p];
	T a,b,ans;
	a.s=a.lx=a.rx=a.max=b.s=b.lx=b.rx=b.max=-0x3f3f3f3f;
	ans.s=0;
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) {
		a=ask(p<<1,l,r);
		ans.s+=a.s;
	} 
	if(r>mid) {
		b=ask(p<<1|1,l,r);
		ans.s+=b.s;
}
	ans.max=max(max(a.max,b.max),a.rx+b.lx);
	ans.lx=max(a.lx,a.s+b.lx);
	ans.rx=max(b.rx,b.s+a.rx);
	if(l>mid) ans.lx=max(ans.lx,b.lx);
	if(r<=mid) ans.rx=max(ans.rx,a.rx);
	return ans;
}
void change(int p, int x, int w) {	//单点修改 
	if(t[p].l==t[p].r) {
		t[p].s=t[p].lx=t[p].rx=t[p].max=w;
		return ;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(x<=mid) change(p<<1,x,w);
	else change(p<<1|1,x,w);
	t[p].s=t[p<<1].s+t[p<<1|1].s;
	t[p].lx=max(t[p<<1].lx,t[p<<1].s+t[p<<1|1].lx);
	t[p].rx=max(t[p<<1|1].rx,t[p<<1|1].s+t[p<<1].rx);
	t[p].max=max(max(t[p<<1].max,t[p<<1|1].max),t[p<<1].rx+t[p<<1|1].lx);
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1; i<=m; i++) {
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(x==1) {
			if(y>z) swap(y,z);
			cout<<ask(1,y,z).max<<endl;
		} else {
			change(1,y,z);
		}
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    二、区间修改，区间查询

    （一）给某区间加上一个数，查询某区间内所有数的最大公约数：acwing区间最大公约数

    \quad 懒标记难写，而对于区间加上一个数，刚好可以用差分把它转化成单点修改，就不用写懒标记了。
    \quad 常考的信息就那么几种，这题考最大公约数，就存最大公约数。
    \quad 刚好，父区间的最大公约数等于两个子区间的最大公约数的最大公约数。
    \quad 如果只有查询操作的话就够了，而对于修改操作，修改完的与之前的最大公约数没什么关系，不好弄。
    \quad 先考虑单点修改，搜到底改掉，再往上更新即可，可见单点修改很容易。
    利用差分，把区间修改转化成单点修改：
    \quad x和y的最大公约数等于x和y-x的最大公约数，所以a1、a2、a3、…、an的最大公约数等于a1、a2-a1、a3-a2、…、an-an-1的最大公约数（证明：前者最大公约数为d，d是后者每一项的约数，所以前者最大公约数小于后者，反之亦然）。
    \quad 线段树维护的叶子节点存差分的值，也就是前一项减后一项，区间加一个数对差分序列的影响只有第L项和第R+1项：

    1. 得到差分序列b，b[i]=a[i]-a[i-1]
    2. 用差分序列建树
    3. 对于[L,R]加一个数，转化成两次单点修改，把b[L]加上该数，把b[R+1]减去该数。
    4. 查询[L,R]，先求[1,L]的和sum[L]，再求a[L]与b[L+1]…b[R]的最大公约数。

    注意：查询不能简单的ask(1,L,R)，它等于gcd(a[L]-a[L-1], a[L+1]-a[L], …, a[R]-a[R-1])，而我们要的是gcd(a[L], a[L+1]-a[L], …, a[R]-a[R-1])，第一项不同，要增加辅助属性sum来求a[L]。这个sum维护的是差分序列的区间[L,R]的和。
    \quad 注意爆int。

    #include
#define ll long long
using namespace std;
struct T{
	ll l,r;
	ll x,s;
};
T tr[500010*4];
ll n,m,a[500010],b[500010],l,r,d;
char op;
//void gcd(ll a,ll b) {
//	return b ? gcd(b,a%b) : a;
//}
void pushup(T &u,T &l,T &r) {
	u.s=l.s+r.s;
	u.x=__gcd(l.x,r.x);
}
void build(ll u,ll l,ll r) {
	tr[u].l=l,tr[u].r=r;
	if(l==r) {
		tr[u].s=b[l];
		tr[u].x=b[l];
	} else {
		ll mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
void modify(ll u,ll x,ll w) {
	if(tr[u].l==tr[u].r) tr[u].x+=w, tr[u].s+=w;
	else {
		ll mid=(tr[u].l+tr[u].r)>>1;
		if(x<=mid) modify(u<<1,x,w);
		else modify(u<<1|1,x,w);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
T ask(ll u,ll l,ll r) {
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u];
	else {
		ll mid=(tr[u].l+tr[u].r)>>1;
		if(r<=mid) return ask(u<<1,l,r);
		else if(mid<l) return ask(u<<1|1,l,r);
		else {
			T a,b,ans;
			a=ask(u<<1,l,r);
			b=ask(u<<1|1,l,r);
			pushup(ans,a,b);
			return ans;
		}
	}
}
int main() {
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
		b[i]=a[i]-a[i-1];
	}
	build(1,1,n);
	for(int i=1; i<=m; i++) {
		char c=getchar();
		while(c!='\n') {
			c=getchar();
//			printf("%d",int(c));
		}
		scanf("%c%lld%lld",&op,&l,&r);
		if(op=='C') {
			scanf("%lld",&d);
			modify(1,l,d);
			if(r+1<=n) modify(1,r+1,-d);
		} else {
			ll ans1=ask(1,1,l).s,ans2;
			if(r+1<=n) ans2=ask(1,l+1,r).x;
			else ans2=ans1;
			printf("%lld\n",abs(__gcd(ans1, ans2)));
		}
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    （二）给某区间加上一个数，查询某区间内所有数的和：acwing一个简单的整数问题2

    结构体存sum和add，
    add是懒标记：给当前节点的所有儿子，不包括自己，加上的数值。
    sum：考虑当前节点及子节点上的所有标记（不包括所有祖先节点上的标记），当前区间和是多少。
    既有区间整体加，又有区间整体变成一个数，就只能写懒标记了。另外，已经写了三道题了，其实发现想好思路（结构体存什么与pushup和pushdown）之后，线段树就是填5个函数，直接上就行。

    #include
#define ll long long
using namespace std;
struct T {
	ll l,r;
	ll s,add;
};
T tr[100010*4];
ll n,m,a[100010];
char op;
void pushup(T &u,T &l,T &r) {
	u.s=l.s+r.s;
}
void pushdown(T &u,T &l,T &r) {
	if(u.add) {	//首先判断当前节点上有没有标记
		//如果根节点有标记, 我们就要操作它, 最后一定要清空
		l.add+=u.add, r.add+=u.add;	//左右的add加上根节点的add
		l.s+=(l.r-l.l+1)*u.add;	//左边的sum加上区间长度*根节点的add
		r.s+=(r.r-r.l+1)*u.add;	//右边同理
		u.add=0;	//清空
	}
}
void build(ll u,ll l,ll r) {
	tr[u].l=l,tr[u].r=r;
	if(l==r) {
		tr[u].s=a[l];
		tr[u].add=0;
	} else {
		ll mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
void modify(ll u,ll l,ll r,ll d) {
	if(l<=tr[u].l&&tr[u].r<=r) {
		tr[u].s+=(tr[u].r-tr[u].l+1)*d;
		tr[u].add+=d;
	} else {	//如果当前区间太大, 一定要递归, 则递归前一定要pushdown 
		pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
		ll mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,d);	//如果[l,r]和左边有交集 
		if(mid<r) modify(u<<1|1,l,r,d);	//如果和右边有交集 
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    （三）给某区间加或乘一个数，查询某区间的和：acwing维护序列

    结构体存sum、add、mul，后两个是懒标记。
    优先级问题：add和mul表示先加再乘还是先乘再加。
    \quad 如果表示先加再乘(x+add)×mul，那么再遇到一个加的就不好处理；
    \quad 如果表示先乘再加x×mul+add，那么遇到一个乘，就分别给mul和add乘上即可；那么遇到一个加，就给add加上即可。
    \quad 所以add和mul表示先乘再加，这样更好维护。初始add=0，mul=1。
    不如不管是乘还是加，都用一个函数，传两个参数×c+d，为空也传：
    (x×mul+add)×c+d=x×mul×c+add×c+d
    把mul变成mul×c，把add变成add×c+d。

    #include
#define ll long long
using namespace std;
struct T {
	ll l,r;
	ll s,add,mul;
};
T tr[100010*4];
ll n,m,p,a[100010];
void pushup(T &u,T &l,T &r) {
	u.s=(l.s+r.s)%p;
}
void eval(T &x,ll add,ll mul) {
	x.mul=x.mul*mul%p;
	x.add=(x.add*mul%p+add)%p;
	x.s=(x.s*mul%p + (x.r-x.l+1)*add%p)%p;
}
void pushdown(T &u,T &l,T &r) {	//下传时先乘再加
	eval(l,u.add,u.mul);
	eval(r,u.add,u.mul);
	u.mul=1;
	u.add=0;
}
void build(ll u,ll l,ll r) {
	tr[u]= {l,r,0,0,1};
	if(l==r) {
		tr[u].s=a[l];
	} else {
		ll mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
void modify(ll u,ll l,ll r,ll add,ll mul) {
	if(l<=tr[u].l&&tr[u].r<=r) {
		eval(tr[u],add,mul);	//找到叶子就修改 
	} else {
		pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
		ll mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,add,mul);
		if(mid<r) modify(u<<1|1,l,r,add,mul);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
ll ask(ll u,ll l,ll r) {
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].s;
	else {
		pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
		ll mid=(tr[u].l+tr[u].r)>>1, sum=0;
		if(l<=mid) sum=ask(u<<1,l,r);
		if(mid<r) sum=(sum+ask(u<<1|1,l,r))%p;
		return sum%p;
	}
}
int main() {
	scanf("%lld%lld",&n,&p);
	for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%lld",&m);
	for(int i=1; i<=m; i++) {
		ll op,l,r,d;
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1) {	//乘 
			scanf("%lld",&d);
			modify(1,l,r,0,d);
		} else if(op==2) {	//加 
			scanf("%lld",&d);
			modify(1,l,r,d,1);
		}else {
			printf("%lld\n",ask(1,l,r));
		}
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75

    三、扫描线优化的线段树

    （一）acwing亚特兰蒂斯

    给出n个矩形，求它们的总面积，矩形重叠只算一次。
    只是用到了扫描线的思想：

    1. 积分的思想，把整个图形切成非常多的细长条
    2. 高度相同的一段连续距离切成一个长条

    于是每个长条的面积就等于宽度乘长度，宽度和长度都很容易得到
    图1
    把所有矩形的起始的横坐标排序，把纵坐标做成线段树，一个矩形有四个纵坐2个竖边，做成两个线段，靠近原点的设置权值为+1，远离的设为-1，于是通过权值可以知道当前区间被几个矩形覆盖。
    于是可以把它看成两个操作：

    1. 将某个区间[L,R]加1
    2. 整个区间中，长度大于0的总长度是多少

    结构体存：

    1. l,r
    2. cnt有几个矩形，也就是权值
    3. len当前区间被覆盖部分的总长度，但是不考虑所有的祖先节点的cnt>0的节点

    扫描线的性质：

    1. 只考虑根节点的信息，也就是查询的时候总是询问整个区间，查询区间总是包含当前区间所以不会递归，也就不需要pushdown
    2. 所有的操作均是成对出现的，也就是一个矩形有两条边，修改的时候如果在某区间加上一个数，也会减去该数，不会递归到多余的节点，也不会影响父节点的正确性，也就不需要pushdown。

    更具体的，比如某时刻要增加一个矩形：
    \quad 情况一：cnt>0，表示该区间已经被覆盖，我们查询的时候查到cnt>0就不会继续递归。那么不论新加的区间是否覆盖都不影响答案，在递归到更深层修改时也就不需要pushup和pushdown。
    \quad 情况二：cnt=0，如果说cnt是懒标记的话，它现在是0，pushup和pushdown都没有意义。
    所以不会用到pushdown，总结就是：

    1. 查询的时候只查根节点，根节点的长度是pushup维护好的。
    2. 修改的时候如果当前区间被完全包含，cnt加上要加的数就行，不被完全包含就继续递归。修改的时候pushup还是需要的：如果cnt=0，父节点长度就是两个儿子的总和。

    注意数据n=10000，即最多有20000个纵坐标。而坐标可以是小数，需要离散化。线段树的叶子节点存的不是y1、y2、y3这样的坐标点，而是[y1,y2]、[y2-y3]这样的区间，20000个坐标离散化后最多有19999个区间。

    #include
using namespace std;
struct seg{
	double x,y1,y2;
	int l;
	bool operator < (const seg &t) const {
		return x<t.x;
	}
};
seg s[20010];
struct T{
	int l,r;
	int cnt;
	double len;
};
T tr[80010];
vector<double> y;	//离散化纵坐标 
int find(double x) {	//排序去重后, vector对应的下标顺序即离散化后的值 
	return lower_bound(y.begin(), y.end(), x) - y.begin();
}
void pushup(T &u,T &l,T &r) {
	if(u.cnt>0) u.len=y[u.r+1]-y[u.l];	//cnt>0, 覆盖的长度就是当前区间的长度, 区间变成点+1 
	else if(u.l!=u.r) {	//cnt=0, 且不是叶节点, 再用两个子区间算 
		u.len=l.len+r.len;
	} else {	//cnt=0, 且是叶节点, 清空 
		u.len=0;
	}
}
void build(int u,int l,int r) {
	tr[u]={l,r,0,0};
	if(l!=r) {
		int mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		//建树为空, 不用pushup 
	}
}
void modify(int u,int l,int r,int k) {
	if(l<=tr[u].l&&tr[u].r<=r) {
		tr[u].cnt+=k;
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	} else {
		int mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,k);	//左边有交集就递归左边 
		if(mid<r) modify(u<<1|1,l,r,k);	//右边同理 
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
int main() {
	int n,T=1;
	while(scanf("%d",&n),n) {
		y.clear();
		for(int i=0,j=0; i<n; i++) {
			double x1,y1,x2,y2;
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			s[j++]={x1,y1,y2,1};
			s[j++]={x2,y1,y2,-1};
			y.push_back(y1);
			y.push_back(y2);
		}
		//离散化 
		sort(y.begin(),y.end());
		y.erase(unique(y.begin(),y.end()) ,y.end());	//去重 
		
		build(1,0,y.size()-2);	//从0开始-1, 区间比点少1个再-1 
		
		double res=0;
		sort(s,s+n*2);	//对2n个横坐标排序 
		for(int i=0; i<n*2; i++) {	//依次读入横坐标 
			if(i>0) res += tr[1].len*(s[i].x-s[i-1].x);	//只查询根节点 
			modify(1, find(s[i].y1), find(s[i].y2)-1, s[i].l);	//点转化成区间-1 
		}
		printf("Test case #%d\n",T++);
		printf("Total explored area: %.2lf\n\n",res);
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77

    （二）luogu窗口的星星

    \quad 给出窗口的长和宽（窗口平行于坐标轴），和星星们的坐标和亮度，问窗口的亮度最大值。
    \quad 首先想贪心：
    \quad 对于一个星星a[1]，当它在窗口的四个角时刚好被框住。由于星星不动，窗口动，我们以窗口的左下角坐标点A[1]代表窗口，则窗口A[1]的移动范围刚好为一个矩形B[1]，形状刚好等于窗口。
    \quad 对于两个星星a[1]和a[2]，想要同时框住它们，就要选择B[1]和B[2]的重合部分。
    \quad 想同时框住更多星星，就要使窗口包含尽可能多的B的重合部分。
    把所有的星星与窗口的关系转化成B之后，画出来的图就跟上面的亚特兰蒂斯很像，于是想到扫描线线段树：

    1. 由于用窗口的左下角的坐标点代表窗口，画出来的B可能不完全在第一象限，所以改为用窗口右上角的点来代表。
    2. 注意题目说边框上的不算在内，但是不能直接把窗口的长宽减2。
      举个例子，原本2×2的窗口，减2后变成一个点，但是实际上它最多可以框住4个点。所以是长宽减1，然后把框往下和往左移动0.5。但其实在图上的相对位置没有移动，所以长宽减1就行。
      但是要注意相同坐标的宽和高，总是优先加：对于横坐标的宽，只用在重载运算符的时候多加一个判断；对于高，更便捷的是只减0.5，然后把对应的整型改成double，但一定要找全，可以用图2的示例。
      图2
    3. 把问题转化为：平面上有若干个矩形，每个矩形都带有一个亮度属性，求一个坐标上的亮度总和的最大值。
    4. 离散化，然后扫描线，只是变成求max
    #include
#define ll long long 
using namespace std;
struct seg{
	ll x;
	double y1,y2;
	int pd;
	bool operator < (const seg &t) const {
		if(x==t.x) return pd>t.pd;	//边界要有 
		else return x<t.x;
	}
};
seg s[20010];
struct T{
	int l,r;
	ll max,add;
};
T tr[80010];
int n,w;
double h;
vector<double> ys;	//离散化纵坐标 
int find(double y) {
	return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}
void pushup(T &u,T &l,T &r) {
	u.max=max(l.max,r.max);
}
void pushdown(T &u,T &l,T &r) {
	l.add+=u.add;
	l.max+=u.add;
	r.add+=u.add;
	r.max+=u.add;
	u.add=0;
}
void build(int u,int l,int r) {
	tr[u]={l,r,0,0};
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void modify(int u,int l,int r,int k) {
	if(l<=tr[u].l&&tr[u].r<=r) {
		tr[u].add+=k;
		tr[u].max+=k;
		k=k;
	} else {
		pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
		int mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,k);
		if(mid<r) modify(u<<1|1,l,r,k);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		ys.clear();
		scanf("%d%d%lf",&n,&w,&h);
		w--;
		h=h-0.5;
		for(int i=0,j=0; i<n; i++) {
			int x,l;
			double y;
			scanf("%d%lf%d",&x,&y,&l);
			s[j++]={x,y,y+h,l};
			s[j++]={x+w,y,y+h,-l};
			ys.push_back(y);
			ys.push_back(y+h);
		}
		sort(ys.begin(),ys.end());
		ys.erase(unique(ys.begin(),ys.end()) ,ys.end());
//		puts("");for(int i=0; i
		build(1,0,ys.size()-2);	//样例是4个点, 对应3个区间
		
		ll ans=0;
		sort(s,s+n*2);
		for(int i=0; i<n*2; i++) {
			modify(1, find(s[i].y1), find(s[i].y2)-1, s[i].pd);
			ans=max(ans,tr[1].max);
//			printf("%d : %d %d\n",i,find(s[i].y1),find(s[i].y2));
//			for(int j=1; j<=8; j++) printf("%d : %d,%d : %d\n",j,tr[j].l,tr[j].r,tr[j].max);
//			puts("");
		}
		printf("%lld\n",ans);
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    四、练习题：

    $\quad$1、【模板】线段树 1——洛谷
    $\quad$2、【模板】线段树 2——洛谷
    $\quad$3、[TJOI2018]数学计算——洛谷
    $\quad$4、[SCOI2007] 降雨量——洛谷
    降雨量是线段树+模拟，WA了大概是线段树和模拟没有配合好，单纯的线段树部分或模拟的部分都不难。
    $\quad$5、楼房重建——洛谷
    $\quad$6、XOR的艺术——洛谷
    就，楼房重建要说一下：
    \quad 首先你得想到它是个线段树，因为它是动态的，数据范围10W也是刚好。
    \quad 至少我的第一反应不是线段树，是二分斜率，因为只需要一个斜率属性就能确定视线，nlogn也很完美。但是接下来如果逐一确定每栋楼是否能看到，就是n×n×logn了。分析一下，这样的二分不行，是因为视线不止一条。以房顶代表楼房，能看到多少楼房就有多少视线，且这些视线的斜率是越来越大的。
    \quad 那么考虑修改时二分：使其中一栋楼房增高从而遮住上面的视线，那么它的斜率就要比上面的视线的斜率大，二分找出下一个楼房，中间的楼房删掉；使一栋楼房降低从而暴露出更多楼房，其中哪些楼房会被看到，也是取决于视线的斜率，比前一栋楼大就能被看到。这同样需要枚举，会超时，不行。
    \quad 不想枚举，想预先处理好每栋楼的最长上升。那么，对于每个修改，分别维护以每栋楼为起点的最长上升序列，但是不好维护。比如下降一栋楼，那么它的左边所有的最长上升序列都有可能变。
    \quad 看了题解才知道是线段树，维护最长上升序列的长度：

    \quad 维护一个序列，在线单点修改，求出每一时刻各段的前缀最大值数目。
    \quad 使用线段树动态维护每个区间的最大值、最长上升子序列。
    \quad 二分到目标点，修改目标点的mx；很显然的，每个单点的cnt（最长上升子序列）都是1；
    \quad 然后递归回溯处理，更新mx；每个区间的左区间一定会为答案产生贡献，而右区间能为答案产生贡献的点必须大于左区间最大点，所以调用count( )，然后更新cnt。
    \quad count：统计区间[ l , r ]内最小值大于k的最长上升子序列。

    就是说，存连续上升的长度ans和区间最大斜率k。单点修改，修改它的斜率。回溯时，父节点的斜率取左右儿子的最大值，父节点的长度取左儿子的长度加右儿子二分得到的的长度。二分，在右儿子里递归找大于k的叶子节点，注意边找边累加答案长度，找到叶子节点再累加个1。

    #include
#define mp make_pair
using namespace std;
struct T {
	int l,r,ml,y,pd;
};
T tr[50010*4*2];
int n,m;
vector<pair<int,pair<int,int> > > ys;
void pushup(T &u,T &l,T &r) {
	if(l.ml>r.ml) {
		u.ml=l.ml;
		u.y=l.y;
	} else if(l.ml==r.ml) {
		if(l.ml==0&&r.ml==0) {
			u.pd=1;
//			printf("ERROR\n");
		} else if(l.ml==0) {
			u.ml=r.ml;
			u.y=r.y;
		} else if(r.l==0) {
			u.ml=l.ml;
			u.y=l.y;
		} else {
			u.ml=l.ml;
			u.y=l.y;
		}
	} else {
		u.ml=r.ml;
		u.y=r.y;
	}
	u.pd=max(l.pd,r.pd);
}
void build(int u,int l,int r) {
	tr[u]= {l,r,0,0,0};
	if(l==r) {
		//年份离散化后, 对应的自然数顺序, 就是l==r, 通过l反过来寻找年份
		tr[u].y=ys[l].first;
		tr[u].ml=ys[l].second.first;
		tr[u].pd=ys[l].second.second;
	} else {
		int mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
T ask(int u,int l,int r) {
	if(l<=tr[u].l&&tr[u].r<=r) {
		return tr[u];
	} else {
		T a= {0,0,0,0,0},b= {0,0,0,0,0},ans= {0,0,0,0,0};
		int mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) a=ask(u<<1,l,r);
		if(mid<r) b=ask(u<<1|1,l,r);

		pushup(ans,a,b);
		return ans;
	}
}
int main() {
//	freopen("in3.in","r",stdin);
//	freopen("me.out","w",stdout);
	scanf("%d",&n);
	for(int i=0,j=0; i<n; i++) {
		int y,r;
		scanf("%d%d",&y,&r);
		if(i==0) {
			ys.push_back({y-1,{0,1}});//不存在
			ys.push_back({y,{r,0}});
		} else if(y-1==ys[ys.size()-1].first) {
			ys.push_back({y,{r,0}});
		} else {
			ys.push_back({y-1,{0,1}});//不存在
			ys.push_back({y,{r,0}});
		}
	}
	ys.push_back({1147483647,{0,1}});//不存在
	build(1,0,ys.size()-1);
	scanf("%d",&m);
	for(int i=1; i<=m; i++) {
		int l,r,a,b;
		scanf("%d%d",&l,&r);
//		if(i==511) cout<
		a=l,b=r;
		l=lower_bound(ys.begin(), ys.end(), mp(l, mp(0, 0))) -ys.begin();
		r=lower_bound(ys.begin(), ys.end(), mp(r, mp(0, 0))) -ys.begin();
		T maxx1=ask(1,l,r);
		T maxx2=ask(1,l+1,r);
//		printf("%d %d %d %d\n",ys[l].second.second,ys[r].second.second,maxx1.ml,maxx2.ml);
		if((ys[l].second.second==0&&maxx1.y!=a) ||	//左存在, 且不是最大, 错
		   (ys[r].second.second==0&&maxx2.y!=b) ||	//右存在, 且不是次大, 错
		   (ys[l].second.second==0&&ys[r].second.second==1&&maxx1.ml==maxx2.ml)) {	//特判 
			printf("false\n");
		} else if(maxx1.pd==1) {
			printf("maybe\n");
		} else {
			printf("true\n");
		}
	}

	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103

    以前我是怎么写线段树的，不是很清楚了，代码也没有留下来。现在我用的是y总的模板，写题时可以直接套的傻瓜式的模板，的确很好用。
    y总说线段树好写，但是不好debug。的确，细节上的错误难以debug。至于线段树是否好写，就像上面这些线段树模板就挺好写的。
    有的题会糅合其它算法和结构，要加各种各样的功能。思路对不对，细节对不对，好像都要看运气。
    所幸，在普通的比赛中，签到题都A不了，不用去担心不存在的难题。

  • 相关阅读:
    控制台中查看莫格命令的详细信息
    11个常见的分类特征的编码技术
    【LeetCode】12. 整数转罗马数字
    Java面试题及答案（2021年Java面试题大全带答案）
    提交Spark作业遇到的NoSuchMethodError问题
    Hi3516DV500部署paddle版型分析模型记录
    CSS动画 animation VS transition
    2022秋线上作业-第6次-第13-15周（排序、查找判断题）
    第2关：BeautifulSoup解析网页
    语音人工智能的简单介绍
  • 原文地址：https://blog.csdn.net/m0_62021646/article/details/126536603