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;
}
上一篇: 简单的四色问题