yukicoder No.284 門松と魔法(2)

Programming yukicoder

発想は良問.実装が大変.

問題:数列が与えられる,部分列Bであって,B[i]!=B[i+2] かつ (B[i]<B[i+1]>B[i+2] または B[i]>B[i+1]<B[i+2]) を任意のiに対して満たすようなものの長さの最大値を求めよ.

まずはじめB[i]!=B[i+2]を完全に見落としてたためO(N^2)DPから自然に生えるsegtreeを書いて提出したらWAだったので,問題文を読むと違うことがわかった.

このsegtreeでは最後がbで終わるような列 というのの最大値をsegで持っていたけど,最後から二番目aの情報も持って置かなければいけないことがわかる.でも,条件は,今xを更新しようとしてるとするとx!=a なので,aとしてはでかい方からたかだか2個しか持たなくて良い.
なので,seg[b]に,(mx,a)の組(aは異なる)を2つ持っておけばできる.(mergeはちょっと面倒だけど)

ただ,これを持とうとするとちゃんとqueryの際にどっから最大値が来たか,というのを求めないといけないので,idも持っておく.
しかも更新のためには2番目の最大値も求めなければいけないが,これは冷静に考えるともう一度1番目のとこを除いてクエリを投げれば良い.

実装がしんどかった(2番目がまだないとか,一箇所しか候補がないなら2番目はなしとか,細かい部分が大変).

はじめoperator+でmapを使ってたらTLEしたので,bubble sortにしたら通った.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

struct D{
	int segid[2],id[2],mx[2];			//id[i] -> segid[i] -> nxt
	D(){
		segid[0]=segid[1]=-1;
		id[0]=id[1]=-1;
		mx[0]=mx[1]=-1;
	}
	D(int x){
		segid[0]=x;
		segid[1]=-1;
		id[0]=-1;
		id[1]=-1;
		mx[0]=1;
		mx[1]=-1;
	}
	D(int a,int b,int c,int d,int e,int f){
		id[0]=a,segid[0]=b,mx[0]=c,id[1]=d,segid[1]=e,mx[1]=f;
	}
	const static D e;
/*	D operator+(const D& r) const {
		typedef pair<int,int> P;
		typedef pair<P,int> PP;
		map<int,P> mp;
		rep(i,2) if(mx[i]>=0) chmax(mp[id[i]],P(mx[i],segid[i]));
		rep(i,2) if(r.mx[i]>=0) chmax(mp[r.id[i]],P(r.mx[i],r.segid[i]));
		vector<PP> vp;
		for(auto it:mp) vp.pb(PP(it.sc,it.fs));
		sort(all(vp),greater<PP>());
		int K=vp.size();
		D ret;
		rep(i,min(2,K)) ret.id[i]=vp[i].sc,ret.mx[i]=vp[i].fs.fs,ret.segid[i]=vp[i].fs.sc;
		return ret;
	}*/
	D operator+(const D& r) const {
		int tid[4],tsegid[4],tmx[4],K=0;
		rep(i,2) if(mx[i]>=0) tid[K]=id[i],tsegid[K]=segid[i],tmx[K]=mx[i],K++;
		rep(i,2) if(r.mx[i]>=0) tid[K]=r.id[i],tsegid[K]=r.segid[i],tmx[K]=r.mx[i],K++;
		rep(i,K-1) rep(j,K-1-i) if(tmx[j]<tmx[j+1]) swap(tmx[j],tmx[j+1]),swap(tsegid[j],tsegid[j+1]),swap(tid[j],tid[j+1]);

		int I=0;
		D ret;
		rep(i,K){
			bool ok=1;
			rep(j,i){
				if(tid[j]==tid[i]){
					ok=0;
					break;
				}
			}
			if(!ok) continue;
			ret.id[I]=tid[i],ret.segid[I]=tsegid[i],ret.mx[I]=tmx[i],I++;
			if(I==2) break;
		}
		return ret;
	}
	void inc(){
		rep(i,2) if(mx[i]>=0) mx[i]++;
	}
	friend ostream& operator<<(ostream& o,const D& d){
		o<<"d=   mx="<<d.mx[0]<<" at ("<<d.id[0]<<","<<d.segid[0]<<")"<<endl;
		o<<"     mx="<<d.mx[1]<<" at ("<<d.id[1]<<","<<d.segid[1]<<")"<<endl;
		return o;
	}
};
const D D::e = D();

template<class D>
struct segtree{
	static const int N=1<<17;

	D e=D::e;
	vector<D> seg;
	segtree():seg(N*2,e){}
	void update(int k,D val){
		k+=N;
		seg[k]=val;
		k/=2;
		while(k){
			seg[k]=seg[k*2]+seg[k*2+1];
			k/=2;
		}
	}
	D calc(int a,int b,int l=0,int r=N,int k=1){
		if(b<=a||b<=l||r<=a) return e;
		if(a<=l&&r<=b) return seg[k];
		return calc(a,b,l,(l+r)/2,k*2)+calc(a,b,(l+r)/2,r,k*2+1);
	}
};
segtree<D> up,down;


int N;
int x[100000];
vector<int> xs;
int main(){
	cin>>N;
	rep(i,N){
		scanf("%d",x+i);
		xs.pb(x[i]);
	}
	sort(all(xs));
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	int K=xs.size();
	rep(i,N) x[i]=lower_bound(all(xs),x[i])-xs.begin();
	rep(i,N){
//		printf("i=%d\n",i);
		int X=x[i];
		D dval,uval;
		{//go up
			D dmx=down.calc(0,X);
			int mx=-2,arg;
			rep(j,2){
				if(dmx.id[j]!=X){
					mx=dmx.mx[j];
					arg=dmx.segid[j];
					break;
				}
			}
			if(mx>=0){
				D dmx2 = down.calc(0,arg) + down.calc(arg+1,X);
				int mx2=-2,arg2;
				rep(j,2){
					if(dmx2.id[j]!=X){
						mx2=dmx2.mx[j];
						arg2=dmx2.segid[j];
						break;
					}
				}
				dval = D(arg,X,mx,arg2,X,mx2);
			}else{
				dval = D(arg,X,mx,-1,-1,-1);
			}
			dval.inc();
			dval = dval + D(X);
		}

		{//go down
			D umx=up.calc(X+1,K);
			int mx=-2,arg;
			rep(j,2){
				if(umx.id[j]!=X){
					mx=umx.mx[j];
					arg=umx.segid[j];
					break;
				}
			}
			if(mx>=0){
				D umx2 = up.calc(X+1,arg) + up.calc(arg+1,K);
				int mx2=-2,arg2;
				rep(j,2){
					if(umx2.id[j]!=X){
						mx2=umx2.mx[j];
						arg2=umx2.segid[j];
						break;
					}
				}
				uval = D(arg,X,mx,arg2,X,mx2);
			}else{
				uval = D(arg,X,mx,-1,-1,-1);
			}
			uval.inc();
			uval = uval + D(X);
		}
		// cout<<"dval"<<endl<<dval<<endl;
		// cout<<"uval"<<endl<<uval<<endl;
		up.update(X,dval);
		down.update(X,uval);
	}
	int ans=max(up.calc(0,K).mx[0],down.calc(0,K).mx[0]);
	if(ans<=2) ans=0;
	cout<<ans<<endl;
}