当前位置:网站首页>HDU 4391 Paint The Wall 段树(水
HDU 4391 Paint The Wall 段树(水
2022-07-05 21:39:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
意甲冠军:
特定n多头排列。m操作
以下是各点的颜色
以下m一种操纵:
1 l r col 染色
2 l r col 问间隔col色点
== 通的操作+区间内最大最小颜色数的优化,感觉非常不科学。。。
==感觉能够卡掉这样的写法。。反正就是不科学嘛
#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
*/
版权声明:本文博客原创文章。博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117563.html原文链接:https://javaforall.cn
边栏推荐
- EN 438-7 laminated sheet products for building covering decoration - CE certification
- 让开发效率飞速提升的跨端方案
- 思特奇加入openGauss开源社区,共同推动数据库产业生态发展
- Dictionary tree simple introductory question (actually blue question?)
- Three components of openpyxl
- regular expression
- Teach yourself to train pytorch model to Caffe (III)
- oracle 控制文件的多路复用
- 使用Aspect制作全局异常处理类
- Sorting out the problems encountered in MySQL built by pycharm connecting virtual machines
猜你喜欢
2.2 basic grammar of R language
JMeter installation under win7
Teach yourself to train pytorch model to Caffe (I)
2.2.3 output of documents
Sorting out the problems encountered in MySQL built by pycharm connecting virtual machines
冯唐“春风十里不如你”数字藏品,7月8日登录希壤!
让开发效率飞速提升的跨端方案
EasyExcel的讀寫操作
Xlrd common operations
matlab绘制hsv色轮图
随机推荐
Parker驱动器维修COMPAX控制器维修CPX0200H
Pointer parameter passing vs reference parameter passing vs value parameter passing
Ethereum ETH的奖励机制
Deep merge object deep copy of vant source code parsing
ArcGIS栅格重采样方法介绍
Four components of logger
股票开户选择哪家证券公司比较好哪家平台更安全
EBS Oracle 11g 克隆步骤(单节点)
[case] Application of positioning - Taobao rotation map
Gcc9.5 offline installation
[daily training -- Tencent select 50] 89 Gray code (only after seeing the solution of the problem)
Comprehensive optimization of event R & D workflow | Erda version 2.2 comes as "7"
MySQL InnoDB Architecture Principle
Selenium finds the contents of B or P Tags
Zhang Lijun: penetrating uncertainty depends on four "invariants"
Robot operation mechanism
postgres 建立连接并删除记录
Wood board ISO 5660-1 heat release rate mapping test
Sitge joined the opengauss open source community to jointly promote the ecological development of the database industry
有些事情让感情无处安放