FZU 2136 取糖果-阿里云开发者社区

开发者社区> 陈国林> 正文

FZU 2136 取糖果

简介: 点击打开链接 题意:中文题.... 思路:对于每个数,我们可以求出以当前这个点为最大值能够向左右两边扩展的范围,假设每个数的左边和右边扩展到l[i] , r[i]的位置。
+关注继续查看

点击打开链接

题意:中文题....

思路:对于每个数,我们可以求出以当前这个点为最大值能够向左右两边扩展的范围,假设每个数的左边和右边扩展到l[i] , r[i]的位置。接下来我们只要枚举这n个数,然后枚举1~这个数的区间长度,并更新ans数组即可。这边为了控制时间复杂度我们可以采用线段树的成段更新

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define lson(x) (x<<1)
#define rson(x) (lson(x)|1)
#define mid(x,y) ((x+y)>>1)
const int INF = 0x3f3f3f3f;
const int MAXN = 100010;

struct Node{
    int left;
	int right;
	int mark;//延时标记
	int num;
};
Node node[4*MAXN];
int n , num[MAXN];
int l[MAXN] , r[MAXN];

// 向下更新
void push_down(int pos){
	if(node[pos].mark != INF){//如果可以继续往下更新
		node[lson(pos)].mark = min(node[lson(pos)].mark , node[pos].mark);
		node[rson(pos)].mark = min(node[rson(pos)].mark , node[pos].mark);

		node[lson(pos)].num = min(node[pos].mark , node[lson(pos)].num);
		node[rson(pos)].num = min(node[pos].mark , node[rson(pos)].num);
		node[pos].mark = INF;
	}
}

void build(int left , int right , int pos){
	node[pos].left = left;
	node[pos].right = right;
	node[pos].mark = INF;
	node[pos].num = INF;
	if(left == right){
		scanf("%d" , &num[left]);
		return;
	}
	int mid = mid(left , right);
	build(left , mid , lson(pos));
	build(mid+1 , right , rson(pos));
}

void update(int left , int right , int val , int pos){
	if(left <= node[pos].left && right >= node[pos].right){
		node[pos].mark = min(node[pos].mark , val);
		node[pos].num = min(node[pos].num , node[pos].mark);
		return;
	}
	push_down(pos);// 向下更新

	int mid = mid(node[pos].left , node[pos].right);
	if(right <= mid)
		update(left , right , val , lson(pos));
	else if(left > mid)
		update(left , right , val , rson(pos));
	else{
		update(left , mid , val , lson(pos));
		update(mid+1 , right , val , rson(pos));
	}
}

int query(int index , int pos){
    if(node[pos].left == node[pos].right)
		return node[pos].num;
	int mid = mid(node[pos].left , node[pos].right);
	push_down(pos);// 向下更新

	if(index <= mid)
		return query(index , lson(pos));
	else
		return query(index , rson(pos));
}

void solve(){
	// get left and right
	for(int i = 1 ; i <= n ; i++){
		int j;
		// get left
		for(j = i-1 ; j >= 1 ; j--)
			if(num[j] > num[i])
				break;
		l[i] = j+1;
		// get right
		for(j = i+1 ; j <= n ; j++)
			if(num[j] > num[i])
				break;
		r[i] = j-1;
	}
	// update
	for(int i = 1 ; i <= n ; i++)
		update(1 , r[i]-l[i]+1 , num[i] , 1);
	for(int i = 1 ; i <= n ; i++)
		printf("%d\n" , query(i , 1));
}


int main(){
    int cas;
	scanf("%d" , &cas);
	while(cas--){
		scanf("%d" , &n);
		build(1 , n , 1);
		solve();
	}
	return 0;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
HSF/Dubbo序列化时的LocalDateTime, Instant的性能问题
### 来源 在对Dubbo新版本做性能压测时,无意中发现对用例中某个TO(Transfer Object)类的一属性字段稍作修改,由Date变成LocalDateTime,结果是吞吐量由近5w变成了2w,RT由9ms升指90ms。
2331 0
计算机图形学遇上深度学习
今日,TensorFlow 宣布推出 TensorFlow Graphics,该工具结合计算机图形系统和计算机视觉系统,可利用大量无标注数据,解决复杂 3D 视觉任务的数据标注难题,助力自监督训练。
2285 0
独家揭秘:阿里小程序的一云多端!看这篇就够了!
阿里巴巴小程序一云多端的整体战略,以及阿里小程序后续为开发者提供的云服务(云应用、云开发等)、开发者工具链(IDE、插件、SDK等)、跨端框架能力说明。同时结合繁星计划后续提供给开发者的扶持和ISV的权益体系做一个整体的介绍。
27361 0
CDN的HTTPS配置及故障排除
相较于HTTP协议来说,HTTPS协议在网络链路中传输更具有安全可靠性,因为它通过SSL证书在链路中间对我们七层的网络包做了加密,进而防止了一些恶意的内容劫持。针对于这种场景,阿里云CDN也提供了相关的功能,可以支持客户端到CDN L1节点的HTTPS的协议。
1574 0
GDB 调试 Mysql 实战(一)源码编译安装
下载源码 git clone https://github.com/mysql/mysql-server.git cd mysql-server git checkout 5.7 编译安装 安装依赖 yum install -y cmake make gcc gcc-c++ ncurses-dev...
979 0
PostgreSQL 锁
锁的类型 /* NoLock is not a lock mode, but a flag value meaning "don't get a lock" */ #define NoLock 0 #define AccessS...
1138 0
+关注
陈国林
曾任职于阿里巴巴,现就职于美图,专业搬砖100年~
723
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载