未知出處

題意：

定義一個無窮長的數(shù)列，滿足以下性質(zhì)：
$1.X_{2n}=-{X_{n}}$

$2.X_{2n}=(-1)^{(n+1)}*X_{n}$

$3.X_{2n-1}=(-1)^{(n+1)}*X_n$

1e5個詢問，求：
$1.X_k$

$2.S_k$即前綴和

（大概是這樣）

?

畫一畫遞推式的圖，或者觀察2n，n可以看到轉(zhuǎn)移類似一個二叉樹。

第一個點要特判

樹高logn

左右兒子有不同的邊權(quán)

可以類似二進制差分，一路走到$X_k$即可求出第一問

?

第二問，

發(fā)現(xiàn)是一個連續(xù)的子樹塊

往1點走，發(fā)現(xiàn)可以把兩邊的子樹分別算上，而且都是完全二叉樹！

可以dp[deep][0/1][0/1]表示深度為deep的完全二叉樹的根節(jié)點權(quán)值-1/+1,奇偶性0/1時，子樹的和（這個是固定的）

?

logn走一下即可。

特判1點

?

轉(zhuǎn)載于:https://www.cnblogs.com/Miracevin/p/10202547.html

總結(jié)

以上是生活随笔為你收集整理的ywy_c_asm题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。