麦田守望者

NC54357. 麦田守望者

描述

柏拉图有一天问老师苏格拉底是什么是爱情，苏格拉底叫他到麦田走一次，在途中要摘一株最大最好的麦穗，但只可以摘一次，也不能回头。柏拉图觉得很容易，充满信心地出去，谁知过了半天他仍没有回去。最后，他垂头丧气地出现在老师跟前诉说空手而回的原因：“很难得看见一株不错的，却不知道是不是最好的，因为只可以摘一株，只好放弃，再往前走看看有没有更好的。到发现已经走到尽头时，才发觉手上一株麦穗也没有。”
  这时，苏格拉底告诉他：“这就是爱情！”
   事实上，这个问题有一种最优策略。假设麦穗总数为N，经过前 $\lfloor \cfrac{N}{e} \rfloor (e\approx 2.7182818)$ 个麦穗时记录最大值Max，之后如果遇到比Max更大的就摘下来，否则就摘最后一个。这样摘到最大的麦穗的概率最大。（证明留作习题）
   Reverie是一个麦田守望者，她看到很多人困惑于该怎样摘麦穗，于是想写一个程序来解决这个问题，你能帮帮她么？
   具体的，麦田里有 $n(1 \leq n\leq 500000)$ 个麦穗从左到右排列，位置为1到n，每个麦穗都有一个权值 $A_i(1\leq A_i\leq 10^9)$ 。
   有 $q(1 \leq q\leq 500000)$ 次操作，操作分为两种:
   1 x v 表示把位置 $x(1 \leq x \leq n)$ 的麦穗权值改为 $v(1 \leq v \leq 10^9)$ 。
   2 l r 询问区间 $[l,r](1 \leq l\leq r\leq n)$ 的选择。
   对于一个询问区间[l,r]，分界点记为 $m=l+\lfloor \cfrac{r-l+1}{e} \rfloor$ ，首先你需要找出区间[l,m]的最大值Max，然后从左到右扫描区间[m+1,r]，输出第一个大于Max的值，如果没有值比Max更大，输出 $A_r$ 。特别的，如果l=r，直接输出 $A_l$ 即可。

输入描述

第一行两个正整数n, q，分别表示麦穗的总数和操作的个数。
之后一行n个正整数，表示麦穗的权值。
接下来q行, 每行三个正整数表示一次操作。

输出描述

对每个询问，一行内输出一个整数代表答案。

示例1

输入:

输出:

3
5

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 660ms, 内存消耗: 10852K, 提交时间: 2020-03-08 11:56:38

#include <bits/stdc++.h>
#define Lson left,mid,pos<<1
#define Rson mid+1,right,pos<<1|1
using namespace std;
const int N = 5E5+3;
const double e = 2.7182818;
int a[N],Max[N<<2];
int build(int left,int right,int pos) {
	if(left==right) return Max[pos] = a[left];
	int mid = (left+right)/2;
	return Max[pos] = max(build(Lson),build(Rson)); 
}
int modify(int left,int right,int pos,int x,int val) {
	if(left>x||right<x) return Max[pos];
	if(left==right) return a[left] = Max[pos] = val;
	int mid = (left+right)/2;
	return Max[pos] = max(modify(Lson,x,val),modify(Rson,x,val));
}
int query(int left,int right,int pos,int qL,int qR)
{
	if(qL>right||qR<left) return -1000000000;	
	if(qL<=left&&right<=qR) return Max[pos];
	int mid = (left+right)/2;
	return max(query(Lson,qL,qR),query(Rson,qL,qR));
}
int Query(int left,int right,int pos,int qL,int qR,int v)
{
	if(left>qR||right<qL||Max[pos]<=v) return 10000000; //不在所求的范围之内 
	if(left==right) return left;
	int mid = (left+right)/2;
	if(qL<=left&&right<=qR)
	{
		if(Max[pos<<1]>v) return Query(left,mid,pos<<1,qL,qR,v);
		else return Query(mid+1,right,pos<<1|1,qL,qR,v);
	}
	int idL = Query(left,mid,pos<<1,qL,qR,v);
	int idR = Query(mid+1,right,pos<<1|1,qL,qR,v);
	return min(idL,idR);
}
int main()
{
	int n,q,x,v,l,r,op,m,Lmax,Rmax,id;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	build(1,n,1);
	while(q--)
	{ 
		scanf("%d",&op);
		if(op==1) {
			scanf("%d%d",&x,&v);
			modify(1,n,1,x,v);
		} else {
			scanf("%d%d",&l,&r);
			if(l==r) {
				printf("%d\n",a[r]);continue;
			} m = l+floor(1.0*(r-l+1)/e);
			Lmax = query(1,n,1,l,m);
			Rmax = query(1,n,1,m+1,r);
			if(Rmax<=Lmax) id = r;
			else id = Query(1,n,1,m+1,r,Lmax);
			printf("%d\n",a[id]);
		}
	}	
	
	
	return 0;
}