noip模拟59(待补)

A. 柱状图

B. 应急棍

C. 擒敌拳

考场上测试点分治切了,单调队列 \(+\) 斜率优化.

每次枚举队列里的所有元素就行了.

正解是李超线段树.

C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define ull unsigned ll
	#define lf double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		int ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=2e5+21;

namespace DEQUE{
	struct Deque{
		ll l,r; ll q[N<<2];
		inline bool empty(){ return l>r; }
		inline ll size(){ return r-l+1; }
		inline ll front(){ return q[l]; }
		inline ll back(){ return q[r]; }
		inline void pop_front(){ l++; }
		inline void pop_back(){ r--; }
		inline void push_front(ll x){ q[--l]=x; }
		inline void push_back(ll x){ q[++r]=x; }
	} que;
} using namespace DEQUE;

ll m,n,maxh,ans,flag;
ll H[N];
struct I { ll h,id,lc; } p[N];
inline void Work1(){
	ll now;
	for(int i=1;i<=n;i++){
		maxh=max(maxh,p[i].h),p[i].lc=i;
		if(que.empty()) que.push_back(i),ans=max(ans,p[i].h);
		else{
			if(p[que.back()].h<p[i].h) que.push_back(i);
			else{
				while(que.size() and p[que.back()].h>=p[i].h){
					now=que.back(),que.pop_back();
					p[i].lc=min(p[now].lc,p[i].lc);
				}
				que.push_back(i);
			}
			for(int j=que.l;j<=que.r;j++){
				ans=max(ans,(i-p[que.q[j]].lc+1)*p[que.q[j]].h);
			}
		}
		printf("%lld ",max(ans,maxh));
	}	
}
inline ll caly(ll x){ return x*H[x]-H[x]; }
inline lf getxl(ll a,ll b){ return 1.0*(caly(a)-caly(b))/(H[a]-H[b]); }
inline void Work2(){
	for(int i=1;i<=n;i++) H[i]=p[i].h;
	que.push_back(1); ll res=0; printf("%lld ",H[1]);
	for(int i=2;i<=n;i++){
		while(que.l<que.r and getxl(que.q[que.l+1],que.front())<=i) que.pop_front();
		res=max(H[i],H[que.front()]*i-caly(que.front()));
		while(que.l<que.r and getxl(i,que.back())<=getxl(que.back(),que.q[que.r-1])) que.pop_back();
		que.push_back(i);
		printf("%lld ",res);
	}
}
signed main(){
	FILE(b);
	n=read(),que.l=n+1,que.r=n;flag=1;
	for(int i=1;i<=n;i++) p[i].h=read(),flag&=(p[i].h>=p[i-1].h);
	if(flag) Work2();
	else Work1();
	
	exit(0);
}

D. 边数

上一篇:布局中的盒模型与 display


下一篇:正睿 CSP 七连测 day3