首页 > 其他分享 >P8037 [COCI2015-2016#7] Prokletnik 题解

P8037 [COCI2015-2016#7] Prokletnik 题解

时间:2025-01-07 12:54:59浏览次数:1  
标签:ch 端点 题解 COCI2015 cnt1 plen 2016 最大值 单调

题意

定义一个区间 $l,r$ 为好的当且仅当最小值为 $a_l$ 且最大值为 $a_r$最大值为 $a_l$ 且最小值为 $a_r$。

我们先考虑最小值为 $a_l$ 且最大值为 $a_r$ 的,另一个我们翻转过来在搞一遍就好了。

先考虑将询问离线按 $r$ 排序,容易发现,对于每个右端点 $r$ 对应的合法左端点是一段单调递增的数,若我们将 $r$ 从小到大跑,最后一次给左端点 $l$ 赋值的右端点 $r$ 一定是最优的,这很显然,因为固定了 $l$,$r$ 越大,长度越大。

然后由于对应的合法左端点是一段单调递增的数,可以用单调栈存,考虑开两个线段树分别维护单调栈里的和不在单调栈里的,这里注意,由于 $r$ 前面可能有比 $a_r$ 大的数,所以要二分判单调栈内第一个合法位置在哪。

由于每个数最多进栈出栈一次,所以时间是可以保证的,线段树则需要能满足单点覆盖和区间加,区间求最大值

最后求答案,直接二分栈里第一个下标大于等于 $q_l$ 的数,同时求不在单调栈里的 $q_l$ 到 $q_r$ 的最大值就行。

然后在反着做一遍就完了,代码有部分注释方便理解。

code

#include<bits/stdc++.h>
#define mid ((L+R)>>1)
#define ls (p<<1)
#define rs ((p<<1)+1) 
using namespace std;
namespace IO
{
	template<typename T>
	void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
	template<typename T,typename... Args>
	void read(T &_x,Args&...others){Read(_x);Read(others...);}
	const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
	#define pc(x) buf[plen++]=x
	#define flush(); fwrite(buf,1,plen,stdout),plen=0;
	template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 1e6+10;
int n,q,a[N],lg[N],st[N][22],ans[N],fg[N<<2],bj[N<<2],cnt,t[N],cnt1,l,r,m1d,sum,o,o1;
struct w
{
	int l,r,id;
}b[N];
struct w1
{
	int mx;
}c[N<<2][2];
inline bool cmp(w x,w y){return x.r < y.r;}
void build(int p,int L,int R,int id)
{
	fg[p] = bj[p] = 0;
	if(L == R)
	{
		if(id == 0) c[p][id].mx = -l+1;//由于是求区间长度,提前减去左端点就好了 
		return;
	}
	build(ls,L,mid,id),build(rs,mid+1,R,id); 
	c[p][id].mx = max(c[ls][id].mx,c[rs][id].mx);
}
inline void push_up1(int p,int id,int L,int R)
{
	if(id == 1) c[ls][id].mx = -t[L]+1,c[rs][id].mx = -t[R]+1;
	else c[ls][id].mx = -L+1,c[rs][id].mx = -R+1;
	bj[ls] = bj[rs] = 0;
	fg[ls] = fg[rs] = 1;
	fg[p] = 0;
}
inline void push_up(int p,int id)
{
	c[ls][id].mx += bj[p],c[rs][id].mx += bj[p];
	bj[ls] += bj[p],bj[rs] += bj[p];
	bj[p] = 0;
}
void change(int p,int l,int r,int k,int id,int L,int R)
{
	if(l <= L && R <= r)
	{
		if(k == -1) 
		{
			if(id == 1) c[p][id].mx = -t[L]+1,bj[p] = 0,fg[p] = 1;//注意这是栈里的数,赋的不一样 
			else c[p][id].mx = -L+1,bj[p] = 0,fg[p] = 1;//clear 
		}
		else 
		{
			if(id == 1) c[p][id].mx += k,bj[p] += k;
			else c[p][id].mx = max(c[p][id].mx,k);
		}
		return;
	} 
	if(fg[p] && id == 1) push_up1(p,id,L,mid+1);
	if(bj[p] && id == 1) push_up(p,id);
	if(l <= mid) change(ls,l,r,k,id,L,mid);
	if(mid < r) change(rs,l,r,k,id,mid+1,R);
	c[p][id].mx = max(c[ls][id].mx,c[rs][id].mx);
}
void query(int p,int l,int r,int id,int L,int R)
{
	if(l <= L && R <= r)
	{
		sum = max(sum,c[p][id].mx);
		return;
	}
	if(fg[p] && id == 1) push_up1(p,id,L,mid+1);
	if(bj[p] && id == 1) push_up(p,id);
	if(l <= mid) query(ls,l,r,id,L,mid);
	if(mid < r) query(rs,l,r,id,mid+1,R);
}
signed main()
{
	read(n); build(1,1,n,0),build(1,1,n,1);
	for(int i = 2;i <= n;i++) lg[i] = lg[i/2]+1;
	for(int i = 1;i <= n;i++) read(a[i]),st[i][0] = a[i];
	read(q);
	for(int i = 1;i <= q;i++) read(b[i].l),read(b[i].r),b[i].id = i;
	sort(b+1,b+1+q,cmp);
	for(int i = 1;i <= lg[n];i++)
		for(int j = 1;j+(1<<i)-1 <= n;j++)
			st[j][i] = max(st[j][i-1],st[j+(1<<(i-1))][i-1]);//st表求出最大值 
	cnt = 1;
	for(int i = 1;i <= n;i++)
	{
		while(cnt1 && a[t[cnt1]] > a[i]) 
		{
			sum = 0; query(1,cnt1,cnt1,1,1,n);
			change(1,t[cnt1],t[cnt1],sum,0,1,n);//清空后赋值 
			cnt1--;
		}
		t[++cnt1] = i;
		int k = lg[i-1];
		l = 1,r = cnt1,o = cnt1;
		while(l <= r)//二分出合法位置 
		{
			m1d = (l+r)/2;
			int k = lg[i-t[m1d]+1];
			o1 = max(st[t[m1d]][k],st[i-(1<<k)+1][k]);//如果这一段最大值=a_r,这可行 
			if(o1 != a[i]) l = m1d+1;
			else r = m1d-1,o = m1d;
		}
		change(1,o,cnt1,-1,1,1,n);//清空,应为要给新的右端点了 
		change(1,o,cnt1,i,1,1,n);
		while(cnt <= q && b[cnt].r == i)//处理右端点为i的询问 
		{
			sum = 0; query(1,b[cnt].l,b[cnt].r,0,1,n);//先求出栈外的 
			l = 1,r = cnt1,o = 0;
			while(l <= r)//二分出合法位置 
			{
				m1d = (l+r)/2;
				if(b[cnt].l <= t[m1d]) o = m1d,r = m1d-1;
				else l = m1d+1;
			}
			if(o) query(1,o,cnt1,1,1,n);
			ans[b[cnt].id] = sum; cnt++;
		}
	}
	//从大到小
	for(int i = 1;i <= lg[n];i++)//下半部分思路同上,就左端点变成最大了
		for(int j = 1;j+(1<<i)-1 <= n;j++)
			st[j][i] = min(st[j][i-1],st[j+(1<<(i-1))][i-1]); 
	build(1,1,n,0),build(1,1,n,1); cnt1 = 0,cnt = 1;
	for(int i = 1;i <= n;i++)
	{
		while(cnt1 && a[t[cnt1]] < a[i]) 
		{
			sum = 0; query(1,cnt1,cnt1,1,1,n);
			change(1,t[cnt1],t[cnt1],sum,0,1,n);//清空后赋值 
			cnt1--;
		}
		t[++cnt1] = i;
		int k = lg[i-1];
		l = 1,r = cnt1,o = cnt1;
		while(l <= r)
		{
			m1d = (l+r)/2;
			int k = lg[i-t[m1d]+1];
			o1 = min(st[t[m1d]][k],st[i-(1<<k)+1][k]);
			if(o1 != a[i]) l = m1d+1;
			else r = m1d-1,o = m1d;
		}
		change(1,o,cnt1,-1,1,1,n);
		change(1,o,cnt1,i,1,1,n);
		while(cnt <= q && b[cnt].r == i)
		{
			sum = 0; query(1,b[cnt].l,b[cnt].r,0,1,n);
			l = 1,r = cnt1,o = 0;
			while(l <= r)
			{
				m1d = (l+r)/2;
				if(b[cnt].l <= t[m1d]) o = m1d,r = m1d-1;
				else l = m1d+1;
			}
			if(o) query(1,o,cnt1,1,1,n);
			ans[b[cnt].id] = max(ans[b[cnt].id],sum); cnt++;
		}
	} 
	for(int i = 1;i <= q;i++) print(ans[i]),pc('\n');
	flush();
	return 0;
}

标签:ch,端点,题解,COCI2015,cnt1,plen,2016,最大值,单调
From: https://www.cnblogs.com/kkxacj/p/18657426

相关文章

  • P5417 [CTSC2016] 萨菲克斯·阿瑞
    P5417[CTSC2016]萨菲克斯·阿瑞题意有\(m\)种字符,每种字符有\(c_i\)个,你要选择一些字符组成长度为\(n\)的字符串。问所有合法字符串共有多少种不同的后缀数组。思路吐槽:一定是由于我的理解能力有很大问题,所以我真的觉得容斥的部分很难理解。想了好久才明白。这里给出......
  • E. Beautiful Array(题解)
    原题链接:https://codeforces.com/problemset/problem/1986/E思路:排序,取模,思维关于操作:ai=ai+k;若要使a1+m1*k==a2+m2*k;则当a1,a2满足a1%k==a2%k,a1,a2可以满足a1+m1*k==a2+m2*k;并在需要(|a1-a2|)/k次操作。将a数组取模后,用vector分别储存,a1和a2相差越小,需要的次数越......
  • 题解:CF2043C Sums on Segments
    题意给你一个长度为\(n\)的数组\(a\),满足\(a\)中有且仅有一个不为\(1\)也不为\(-1\)的数(以下简称特殊的值),剩余的数都是\(1\)或\(-1\)。求所有可能的子区间的和的值(下文简称答案)。从小到大一次输出每一个值,每个值只输出一遍。题解首先,我们发现,如果把那个特殊的值考......
  • 题解:CF2057B Gorilla and the Exam
    CF2057BGorillaandtheExam思路不难发现其实每次操作就是把数组\(a\)内所有值为\(y\)的数都删除掉(\(y\)为数组\(a\)中的莫一个值)。所以我们需要把尽可能多的数都变成原来数组里出现次数最多的数(从出现数量最少的开始,这样能使得消失的数值种类最大化)。首先想到使用数组......
  • 题解:P11507 [ROIR 2017 Day 1] 计算器
    P11507[ROIR2017Day1]计算器思路简单的动态规划。\(dp_{i,j,k}\)表示使用了\(i\)次按钮A,\(j\)次按钮B和\(k\)次按钮C。转移式:\[\begin{cases}dp_{i+1,j,k}=\min(dp_{i+1,j,k},\lfloordp_{i,j,k}\div2\rfloor);\\dp_{i,j+1,k}=\min(dp_{i,j+1,k},\lfloo......
  • QOJ964. Excluded Min 题解
    QOJ原题链接简要题意设\(S\)为一个可重非负整数集合,假设\(x\)为\(S\)中的一个出现次数\(\ge2\)的元素,你可以将\(x\)改成\(x+1\)或\(x-1\)。定义\(f(S)\)表示对\(S\)进行上述操作任意次所能达到的最大\(\operatorname{mex}\)。给定一个长度为\(n\)的......
  • [POJ3237] 树的维护 题解
    一眼树链剖分或\(LCT\),由于在学后者所以就写了。取反操作相当于把\(min,max\)取反后交换,所以要维护\(min,max,val\)。时间复杂度\(O(m\logn)\)。#include<bits/stdc++.h>#definefa(x)lct[x].fa#definefl(x)lct[x].fl#definemx(x)lct[x].mx#definemn(x)lct[x]......
  • JSP程序设计2016花店在线销售管理系统(源码)
    项目包含:源码、讲解视频、说明文档,部署录像运行环境:推荐jdk1.8开发工具:Eclipse、MyEclipe以及idea(推荐)操作系统:windows108G内存以上(其他windows)浏览器:GoogleChrome(推荐)、Edge、360浏览器;数据库:MySQL5.7;数据库可视化工具:NavicatPremium推荐)以及其他Navicat版本......
  • 复旦大学2024--2025学年第一学期(24级)高等代数I期末考试第七大题解答
    七、(10分) 设$V$是数域$\mathbb{K}$上的$n$维线性空间,$\varphi,\psi$是$V$上的幂等线性变换, 满足$\varphi\psi=\psi$且$\mathrm{Ker}\varphi$是$\psi$-不变子空间.证明:(1)$\mathrm{r}(\psi)\leq\mathrm{r}(\varphi)$;(2)若$\mathrm{r}(\psi)=\mathrm{......
  • 复旦大学2024--2025学年第一学期(24级)高等代数I期末考试第八大题解答
    八、(10分) 设$A,B$为$n$阶实矩阵,满足$A^2+B^2=AB$且$AB-BA$为非异阵, 求证:$n$是3的倍数且$|BA-AB|>0$.证明 设$\omega=-\dfrac{1}{2}+\dfrac{\sqrt{3}}{2}\mathrm{i}$,则$\omega^2=\overline{\omega}=-\dfrac{1}{2}-\dfrac{\sqrt{3}}{2}\mathrm{i}$,于......