P3506 [POI2010]MOT-Monotonicity 2

题目

P3506 [POI2010]MOT-Monotonicity 2

第一次切掉没题解的题\(qwq\)

做法

首先确定\(a_i\)的位置后显然就能确定\(a_{i+1}\)的位置，建一棵权值线段树，维护\(<,=,>\)三种情况

考虑确定\(a_{i}\)的位置

在\([min,a_{i}-1]\)中找\(<\)的最大值
在\([a_{i}+1,max]\)中找\(>\)的最大值
找\([a_{i},a_{i}]\)的\(=\)的值(其实不用线段树，开个数组就能维护)
比较三个值，假定最大值为\(val\)，则更新\([a_{i},a_{i}]\)中\(s[(val-1)\%k+1]\)的值（想一想为什么只更新一个符号的值就能保证正确性？）

这题的难点解决了，至于输出方案，如果你做多了这样的题自然能想到开个数组存每次的状态，然后再开个数组存前驱

代码写得比较乱，重载这些大家自己加吧

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

typedef int LL;

const LL maxn=1500009;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0'&&c<='9')

	    x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x*f;

}

struct node{

	LL mx,mxi,tot;

};

struct Tree{

	node t[4];

	LL son[2];

}tree[maxn];

LL nod;

node Query(LL now,LL l,LL r,LL lt,LL rt,LL opt){

	if(!now||lt>rt)

	    return (node){0,0,0};

	if(lt<=l&&rt>=r)

	    return tree[now].t[opt];

	node ans=(node){0,0,0};

	LL mid=(l+r)>>1;

	if(lt<=mid)

		ans=Query(tree[now].son[0],l,mid,lt,rt,opt);

	if(rt>mid){

		node tmp=Query(tree[now].son[1],mid+1,r,lt,rt,opt);

	    if(ans.mx<tmp.mx)

		    ans=tmp;

	}

	return ans;

}

inline void Update(LL now,LL opt){

	LL son0(tree[now].son[0]),son1(tree[now].son[1]);

	if(tree[son0].t[opt].mx>tree[son1].t[opt].mx)

		tree[now].t[opt]=tree[son0].t[opt];

	else

		tree[now].t[opt]=tree[son1].t[opt];

}

inline void Change(LL &now,LL l,LL r,LL opt,LL goal,LL val,LL tot){

	if(!now){

		now=++nod;

		if(l==r)

	        for(LL i=1;i<=3;++i)

		        tree[now].t[i]=(node){0,l,0};

	}

	if(l==r){

		if(tree[now].t[opt].mx<val)

		    tree[now].t[opt].mx=val,

			tree[now].t[opt].tot=tot;

		return;

	}

	LL mid=(l+r)>>1;

	if(goal<=mid)

	    Change(tree[now].son[0],l,mid,opt,goal,val,tot);

	else

	    Change(tree[now].son[1],mid+1,r,opt,goal,val,tot);

	Update(now,opt);

}

LL n,k,root,ans,last,_min,_max;

LL pre[maxn],a[maxn],c[maxn],ch[maxn],w[maxn];

void Write(LL now){

	if(!now)

	    return;

	Write(pre[now]);

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

}

struct LS{

	LL id,val;

}b[maxn];

inline bool cmp1(LS x,LS y){

	return x.val<y.val;

}

int main(){

	n=Read(),k=Read();

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

	    b[i]=(LS){i,Read()},

		c[i]=b[i].val;

	sort(b+1,b+1+n,cmp1);

	LL num(0);

	for(LL i=1,last=-1;i<=n;++i){

		if(last!=b[i].val)

		    last=b[i].val,

			++num;

		a[b[i].id]=num;

	}

	_min=1,_max=num;

	for(LL i=1;i<=k;++i){

	    char c;

	    scanf(" %c",&c);

	    if(c=='<')

	        ch[i]=1;

	    else if(c=='>')

	        ch[i]=3;

	    else

	        ch[i]=2;

	}

	LL tot(0),last;

	for(LL i=1;i<=n;++i){

		node ans1=Query(root,_min,_max, _min,a[i]-1,1),

		     ans2=Query(root,_min,_max, a[i],a[i]  ,2),

		     ans3=Query(root,_min,_max, a[i]+1,_max,3);

		++ans1.mx,++ans2.mx,++ans3.mx;

		if(ans1.mx<ans2.mx) ans1=ans2;

		if(ans1.mx<ans3.mx) ans1=ans3;

		LL sum(ans1.mx);

		w[++tot]=c[i],

		pre[tot]=ans1.tot,

		Change(root,_min,_max,ch[(sum-1)%k+1],a[i],sum,tot);

		if(sum>ans)

		    ans=sum,

		    last=tot;

	}

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

	Write(last);

	return 0;

}/*

20 5

2 4 3 1 3 5 3 8 9 2 1 20 3 5 9 1 2 4 5 3

< > = < >

11

2 4 3 3 5 3 9 1 1 4 3

*/

巴特西

P3506 [POI2010]MOT-Monotonicity 2

题目

做法

最新文章

热门文章