yukicoder : No.1975 Zigzag Sequence

これは割とすんなり。
https://yukicoder.me/problems/no/1975

問題

N要素の整数列Aが与えられる。
Aの空でない部分列Bは(2^N-1)通りある。
この時、Bのジグザグ度の総和を求めよ。

Bのジグザグ度とは、B[i-1]＜B[i]＞B[i+1]またはB[i-1]＞B[i]＜B[i+1]となるiの個数である。

解法

A[B[i-1]]＜A[B[i]]＞A[B[i+1]]の関係にあるB[i-1]、B[i]、B[i+1]の選び方を数え上げることを考える。
(A[B[i-1]]＞A[B[i]]＜A[B[i+1]]も同様に求める)

B[i-1]・B[i]・B[i+1]が決まると、B[i-2]以前及びB[i+2]以降の取り方は2^(B[i-1]+(N-1-B[i+1]))通りとなる。
そこで、BITを2つ用意し、A[n]の小さい順に、2^nの総和及び2^(N-1-n)の総和を取るBITを用いて、B[i]を総当たりしながらB[i-1]以前及びB[i+1]以降の取り方の総和を掛け合わせよう。

int N;
int A[101010];

ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

template<class V, int ME> class BIT_mod {
public:
	V bit[1<<ME];
	BIT_mod(){ZERO(bit);};
	V operator()(int e) { if(e<0) return 0; ll s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	void add(int e,V v) { e++; while(e<=1<<ME) { (bit[e-1]+=v)%=mo; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}}
};
BIT_mod<ll,20> L,R;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<int,vector<int>> M[2];
	FOR(i,N) {
		cin>>A[i];
		M[0][A[i]].push_back(i);
		M[1][-A[i]].push_back(i);
	}
	
	ll ret=0;
	FOR(i,2) {
		ZERO(L.bit);
		ZERO(R.bit);
		FORR2(a,b,M[i]) {
			FORR(x,b) {
				(ret+=L(x)*(R(N)-R(x)+mo))%=mo;
			}
			FORR(x,b) {
				L.add(x,modpow(2,x));
				R.add(x,modpow(2,N-1-x));
			}
		}
		
	}
	cout<<ret<<endl;
	
}

まとめ

これが門松列だったら少し難しくなるかな。