当前位置:网站首页>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
边栏推荐
- Sorting out the problems encountered in MySQL built by pycharm connecting virtual machines
- Selenium's method of getting attribute values in DOM
- Oracle checkpoint queue - Analysis of the principle of instance crash recovery
- 场景化面试:关于分布式锁的十问十答
- MMAP learning
- 华为快游戏调用登录接口失败,返回错误码 -1
- Summary of data analysis steps
- EasyExcel的讀寫操作
- selenium 查找b或p标签的内容
- Parker驱动器维修COMPAX控制器维修CPX0200H
猜你喜欢
EasyExcel的读写操作
Huawei game multimedia service calls the method of shielding the voice of the specified player, and the error code 3010 is returned
MySQL InnoDB Architecture Principle
MMAP学习
Deeply convinced plan X - network protocol basic DNS
力扣------经营摩天轮的最大利润
华为游戏多媒体调用切换房间方法出现异常Internal system error. Reason:90000017
Introduction of ArcGIS grid resampling method
Kingbasees v8r3 cluster maintenance case -- online addition of standby database management node
Defect detection - Halcon surface scratch detection
随机推荐
让开发效率飞速提升的跨端方案
Selenium finds the contents of B or P Tags
GCC9.5离线安装
Some common processing problems of structural equation model Amos software
Zhang Lijun: penetrating uncertainty depends on four "invariants"
Golang(1)|从环境准备到快速上手
leetcode:1755. Sum of subsequences closest to the target value
2022-07-03-CKA-粉丝反馈最新情况
Net small and medium-sized enterprise project development framework series (one)
Get JS of the previous day (timestamp conversion)
Making global exception handling classes with aspect
Comprehensive optimization of event R & D workflow | Erda version 2.2 comes as "7"
ESP32
EasyExcel的讀寫操作
854. 相似度为 K 的字符串 BFS
Robot framework setting variables
An exception occurred in Huawei game multimedia calling the room switching method internal system error Reason:90000017
datagrid直接编辑保存“设计缺陷”
Oracle检查点队列–实例崩溃恢复原理剖析
秋招将临 如何准备算法面试、回答算法面试题