[POI2010]MOT-Monotonicity 2

洛谷题目链接

动态规划$+$线段树

题目链接（洛谷）

首先，先要明确一点，当我们填了第$i$位时，自然下一位的符号也就出来了

那么我们可以分情况讨论：

$1、$当下一位是$>$时：我们可以建一棵权值线段树，维护区间最大值，查询时在$[1,val[i]-1]$中查询最大值来转移

$2、$当下一位是$=$时：我们也可以在线段树里多维护一个值（当然直接开个数组都行，可我懒得写$qwq$），查询就是单点查询了（当然我是不会再去写一个函数的$qwq$）

$3、$当下一位是$<$时：我们还是在线段树里多维护一个值，查询就在$[val[i]+1,maxn]$中查询就$ok$了

上面的工作做完后就要开始毁天灭地的输出方案了！！

真毒瘤

调了我好久，又爆空间的，整个人都不好了。。。

我们就像以往的$dp$一样记录路径，开数组存着，最后倒序输出就好（说得轻巧）

代码（本蒟蒻不太会打离散，但是不开$long long$居然没有$MLE$）：

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 500001

#define M 1000001

#define ll int

using namespace std;

struct Node

{

	ll v;

	int id;

};

struct Tree

{

	Node num[4];

}tr[M<<2];

int n,m,maxn,tot;

int val[N],opt[N],w[N],pre[N];

Node ans;

Node f[N];

Node max(Node a,Node b)

{

	return a.v>b.v?a:b;

}

void Pushup(int rt,int op)

{

	tr[rt].num[op]=max(tr[rt<<1].num[op],tr[rt<<1|1].num[op]);

}

void Update(int rt,int l,int r,int pos,Node c,int op)

{

	if(l==r)

	{

		tr[rt].num[op]=max(tr[rt].num[op],c);

		return;

	}

	int mid=l+((r-l)>>1);

	if(pos<=mid)

		Update(rt<<1,l,mid,pos,c,op);

	else

		Update(rt<<1|1,mid+1,r,pos,c,op);

	Pushup(rt,op);

}

Node Search(int rt,int l,int r,int L,int R,int op)

{

	if(L>R)

		return (Node){0,0};

	if(L<=l&&r<=R)

		return tr[rt].num[op];

	Node ret;ret.v=0;

	int mid=l+((r-l)>>1);

	if(L<=mid)

		ret=max(ret,Search(rt<<1,l,mid,L,R,op));

	if(mid<R)

		ret=max(ret,Search(rt<<1|1,mid+1,r,L,R,op));

	return ret;

}

void Print(int now)

{

	if(!now)

		return;

	Print(pre[now]);

	printf("%d ",w[now]);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)

		scanf("%d",&val[i]),maxn=max(maxn,val[i]);

	for(int i=1;i<=m;++i)

	{

		char in;

		scanf(" %c",&in);

		opt[i]=in=='<'?1:in=='='?2:3;

	}

//	for(int i=1;i<=m;++i)

//		printf("%d ",opt[i]);

	for(int i=1;i<=n;++i)

	{

		Node ans1=Search(1,1,maxn,1,val[i]-1,1);

		Node ans2=Search(1,1,maxn,val[i],val[i],2);

		Node ans3=Search(1,1,maxn,val[i]+1,maxn,3);

		Node now=max(ans1,max(ans2,ans3));

		now.v+=1;

		w[++tot]=val[i];

		pre[tot]=now.id;

		Update(1,1,maxn,val[i],(Node){now.v,tot},opt[(now.v-1)%m+1]);

		if(ans.v<now.v)

			ans.v=now.v,ans.id=tot;

	}

	printf("%d\n",ans);

	Print(ans.id);

	return 0;

}

巴特西

[POI2010]MOT-Monotonicity 2

最新文章

热门文章