当前位置:网站首页>HDU 4391 paint the wall segment tree (water
HDU 4391 paint the wall segment tree (water
2022-07-05 21:44:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
Serie A Champion :
given n A long line .m operation
Here are the colors of the dots
following m A kind of manipulation :
1 l r col dyeing
2 l r col Ask interval col Chromatic dots
== Pass operation + Optimization of the maximum and minimum number of colors in the interval , It feels very unscientific ...
== I feel like I can get rid of this writing .. Anyway, it's unscientific
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define L(x) tree[x].l
#define R(x) tree[x].r
#define Len(x) tree[x].len
#define Lazy(x) tree[x].lazy
#define M(x) tree[x].minn
#define W(x) tree[x].maxx
#define Lson(x) (x<<1)
#define Rson(x) (x<<1|1)
const int N = 100010;
struct node{
int l, r, len, lazy, minn, maxx;
}tree[N<<2];
int col[N];
void push_up(int id){
if(Lazy(Lson(id)) == Lazy(Rson(id)))
Lazy(id) = Lazy(Lson(id));
else Lazy(id) = -1;
M(id) = min(M(Lson(id)), M(Rson(id)));
W(id) = max(W(Lson(id)), W(Rson(id)));
}
void push_down(int id){
if(Lazy(id) != -1){
Lazy(Lson(id)) = Lazy(Rson(id)) = Lazy(id);
M(Lson(id)) = W(Lson(id)) = Lazy(id);
M(Rson(id)) = W(Rson(id)) = Lazy(id);
}
}
void build(int l, int r, int id){
L(id) = l; R(id) = r;
Len(id) = r-l+1;
Lazy(id) = -1;
if(l == r){
Lazy(id) = col[l];
W(id) = M(id) = col[l];
return ;
}
int mid = (l+r)>>1;
build(l, mid, Lson(id));
build(mid+1, r, Rson(id));
push_up(id);
}
void updata(int l, int r,int val, int id){
if(l == L(id) && R(id) == r){
Lazy(id) = val;
W(id) = M(id) = val;
return ;
}
push_down(id);
int mid = (L(id) + R(id)) >>1;
if(mid < l)
updata(l, r, val, Rson(id));
else if(r <= mid)
updata(l, r, val, Lson(id));
else {
updata(l, mid, val, Lson(id));
updata(mid+1, r, val, Rson(id));
}
push_up(id);
}
int query(int l, int r, int col, int id){
if(!(M(id)<=col && col<=W(id))) return 0;
if(Lazy(id)!=-1){
if(Lazy(id) == col)
return r-l+1;
else return 0;
}
push_down(id);
int mid = (L(id) + R(id)) >>1;
if(mid < l)
return query(l, r, col, Rson(id));
else if(r <= mid)
return query(l, r, col, Lson(id));
else
return query(l, mid, col, Lson(id)) + query(mid+1, r, col, Rson(id));
}
int n, que;
int main() {
while (cin>>n>>que) {
for(int i = 1; i <= n; i++)scanf("%d", &col[i]);
build(1, n, 1);
while(que--){
int type, l, r, color;
scanf("%d %d %d %d", &type, &l, &r, &color);
l++; r++;
if(type == 1)
updata(l, r, color, 1);
else
printf("%d\n", query(l, r, color, 1));
}
}
return 0;
}
/*
5 12
1 2 3 4 0
2 1 3 3
1 1 3 1
2 1 3 3
2 0 3 1
2 3 4 1
1 0 4 0
2 0 4 0
2 0 4 2000000000
1 0 0 1
1 4 4 2
2 0 4 1
2 0 4 2
*/
Copyright notice : This article is an original blog article . Blog , Without consent , Shall not be reproduced .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117563.html Link to the original text :https://javaforall.cn
边栏推荐
- 从零开始实现lmax-Disruptor队列(四)多线程生产者MultiProducerSequencer原理解析
- Sitge joined the opengauss open source community to jointly promote the ecological development of the database industry
- 华为云ModelArts文本分类–外卖评论
- KingbaseES V8R3集群维护案例之---在线添加备库管理节点
- 2.2.3 output of documents
- Kingbasees v8r3 cluster maintenance case -- online addition of standby database management node
- 办公遇到的问题--
- ESP32
- 2022-07-03-CKA-粉丝反馈最新情况
- Summary of data analysis steps
猜你喜欢
張麗俊:穿透不確定性要靠四個“不變”
华为云ModelArts文本分类–外卖评论
Efficiency difference between row first and column first traversal of mat data types in opencv
matlab绘制hsv色轮图
MySQL InnoDB Architecture Principle
Emotional analysis of wechat chat records on Valentine's day based on Text Mining
深信服X计划-网络协议基础 DNS
2.2.5 basic sentences of R language drawing
华为游戏多媒体调用切换房间方法出现异常Internal system error. Reason:90000017
华为游戏多媒体服务调用屏蔽指定玩家语音方法,返回错误码3010
随机推荐
Experienced inductance manufacturers tell you what makes the inductance noisy. Inductance noise is a common inductance fault. If the used inductance makes noise, you don't have to worry. You just need
ICMP 介绍
SQL common syntax records
1.2 download and installation of the help software rstudio
阿里云有奖体验:用PolarDB-X搭建一个高可用系统
The primary key is set after the table is created, but auto increment is not set
selenium 获取dom内验证码图片
Comprehensive optimization of event R & D workflow | Erda version 2.2 comes as "7"
Deployment of Jenkins under win7
力扣------经营摩天轮的最大利润
校招期间 准备面试算法岗位 该怎么做?
深信服X计划-网络协议基础 DNS
Introduction of ArcGIS grid resampling method
2022-07-03-cka- latest feedback from fans
场景化面试:关于分布式锁的十问十答
Selenium finds the contents of B or P Tags
EasyExcel的读写操作
EasyExcel的讀寫操作
poj 3237 Tree(樹鏈拆分)
Efficiency difference between row first and column first traversal of mat data types in opencv