DAY？+2

T1:水

T2:记录不符合情况的序列，可以看到前一个至少是后一个的两倍，所以长度最长是log，于是每次不符合的情况的就可以通过dp[j]*g[i-j]转移，其中i-j<=logm，再套容斥就行了

T3:先染色，没操作的为白，操作了为黑，则对于每一个操作，白的都比它小，黑的都比它大，则不符合的情况是一个点旁边都是白或黑，每次操作，相当于把一条环断开，易知当长度n为奇数，数量为n！，为偶数，无解，于是就可以dp啦

dp[n]=sigma (i=1~n-1) dp[i]*dp[n-i]

### T4 很多做法，反正可以线段树维护扫描线