当前位置:网站首页>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
边栏推荐
- HYSBZ 2243 染色 (树链拆分)
- one hundred and twenty-three thousand four hundred and fifty-six
- Learning notes of statistical learning methods -- Chapter 1 Introduction to statistical learning methods
- Xlrd common operations
- Huawei fast game failed to call the login interface, and returned error code -1
- Efficiency difference between row first and column first traversal of mat data types in opencv
- poj 3237 Tree(树链拆分)
- Interviewer: will concurrent programming practice meet? (detailed explanation of thread control operation)
- SecureCRT使用提示
- MATLAB | App Designer·我用MATLAB制作了一款LATEX公式实时编辑器
猜你喜欢
MySQL deep paging optimization with tens of millions of data, and online failure is rejected!
R language learning notes
Evolution of zhenai microservice underlying framework from open source component encapsulation to self-development
华为游戏多媒体服务调用屏蔽指定玩家语音方法,返回错误码3010
Teach yourself to train pytorch model to Caffe (2)
校招期间 准备面试算法岗位 该怎么做?
让开发效率飞速提升的跨端方案
Opérations de lecture et d'écriture pour easyexcel
华为联机对战如何提升玩家匹配成功几率
Matlab | app designer · I used Matlab to make a real-time editor of latex formula
随机推荐
Scenario interview: ten questions and ten answers about distributed locks
Analysis and test of ModbusRTU communication protocol
The primary key is set after the table is created, but auto increment is not set
Gcc9.5 offline installation
2.2.5 basic sentences of R language drawing
Deployment of Jenkins under win7
2022-07-03-cka- latest feedback from fans
SQL knowledge leak detection
大约SQL现场“这包括”与“包括在”字符串的写法
Detailed explanation of memset() function usage
int GetMonth( ) const throw( );后面的throw( )什么意思?
校招期间 准备面试算法岗位 该怎么做?
Efficiency difference between row first and column first traversal of mat data types in opencv
Three components of openpyxl
leetcode:1755. Sum of subsequences closest to the target value
xlrd常见操作
Chap2 steps into the palace of R language
Oracle checkpoint queue - Analysis of the principle of instance crash recovery
Implementing Lmax disruptor queue from scratch (IV) principle analysis of multithreaded producer multiproducersequencer
有些事情让感情无处安放