欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Hdu4391_Paint The Wall(线段树+剪枝)

程序员文章站 2022-05-20 22:51:15
...

题意:

刷墙, 以开始 有 n个节点,每个节点有一种颜色 ,m 次询问
2种操作:
如果 a=1 :将 l到 r 刷为 z 颜色
如果 a=2 :询问 l 到 r 有 多少个 和 z 相同的 节点

思路:

刚开始没有剪枝,线段树每个节点就存当前区间的颜色,如果当前区间的颜色都一样,都存颜色,否则存为-1(杂色),查询的时候从上到下统计信息。但是这样做太慢了,直接超时。
当查询一中颜色c的时候,我们想,如果这个区间最大的颜色都要比c小或者最小的颜色都比c大,那么这个区间是一定查询不出c的,直接跳过,可以大大提升效率,所以每个区间维护一个最大颜色和最小颜色max_color, min_color。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson l, mid, root<<1
#define rson mid+1, r, root<<1|1
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
const int maxn = 100000+5;

struct Node{
	int color, max_color, min_color;
}Tree[maxn<<2];

void push_up(int rt){
	if(Tree[rt<<1].color == Tree[rt<<1|1].color) Tree[rt].color = Tree[rt<<1].color;
	else Tree[rt].color = -1;
	Tree[rt].max_color = max(Tree[rt<<1].max_color, Tree[rt<<1|1].max_color);
	Tree[rt].min_color = min(Tree[rt<<1].min_color, Tree[rt<<1|1].min_color);
}
void push_down(int rt){
	if(Tree[rt].color == -1) return;
	Tree[rt<<1].color = Tree[rt<<1|1].color = Tree[rt].color;
	Tree[rt<<1].max_color = Tree[rt<<1|1].max_color = Tree[rt].color;
	Tree[rt<<1].min_color = Tree[rt<<1|1].min_color = Tree[rt].color;
}
void Stree_build(int l, int r, int root){
	if(l == r){
		scanf("%d", &Tree[root].color);
		Tree[root].max_color = Tree[root].min_color = Tree[root].color;
		return;
	}
	int mid = (l+r) >> 1;
	Stree_build(lson);
	Stree_build(rson);
	push_up(root);
}
void update(int la, int rb, int l, int r, int root, int val){
	if(la > r||rb < l) return;
	if(la <= l&&rb >= r){
		Tree[root].color = val;
		Tree[root].max_color = Tree[root].min_color = val;
		return;
	}
	push_down(root);
	int mid = (l+r) >> 1;
	if(la <= mid) update(la, rb, lson, val);
	if(rb > mid) update(la, rb, rson, val);
	push_up(root);
}
int Query(int la, int rb, int l, int r, int root, int val){
	if(la > r||rb < l||val < Tree[root].min_color||val > Tree[root].max_color) return 0;
	if(la <= l&&rb >= r){
		if(Tree[root].color == val) return r-l+1;
	}
	if(l == r) return 0;
	int ans = 0;
	push_down(root);
	int mid = (l+r) >> 1;
	if(la <= mid) ans+= Query(la, rb, lson, val);
	if(rb > mid) ans+= Query(la, rb, rson, val);
	return ans;
}

int main()
{
	//freopen("in.txt","r",stdin);
	int n, m;
	int op, l, r, c;
	while(scanf("%d%d",&n,&m) == 2){
		Stree_build(1, n, 1);
		while(m--){
			scanf("%d%d%d%d", &op,&l,&r,&c);
			++l;++r;
			if(op == 1) 
				update(l, r, 1, n, 1, c);
			else
				printf("%d\n", Query(l, r, 1, n, 1, c));
		}
	}

	return 0;
}


相关标签: 剪枝