1樓：Wells
啊.....這個直接裸的權值線段樹就沒了吧分塊也蠻輕鬆的也好寫....建立權值線段樹，樹的節點放dp的值，然後對於第i個點找ai-c～ai+c的最大值以後得到這個點的dp值，作為第ai的值插進去_(:
з」∠)_然後一直做到n並一路與dp值取最大就好了吧，分塊的話也差不多只是每次到sqrtn建乙個塊....
2樓：工藤士多啤梨
考慮用線段樹離散化所有a[i]，a[i]-c，a[i]+c，以數字大小為下標，以dp值建立一顆維護最大值的線段樹，這樣實際上求dp[i]時候就只要query(負無窮，a[i]-c)和(a[i]+c，正無窮)的最大dp值，再單點更新dp值就行，複雜度是nlogn，如果題主還不放心可以搞個lazy(當時我們隊就是這樣過的)。
最後不得不說，校賽題太高了orz
3樓：rsa
這題的好處是，查詢的區間是乙個字尾，所以可以動態維護字尾 的DP值集合 。
按 值維護乙個序列 ， 其中 ，一開始所有 ，查詢滿足 的 最大值就是查詢 ，求出 之後更新 為 即可。用線段樹維護序列 即可在 時間內完成DP。
4樓：MjLee
分塊比較好寫線段樹比較快
query(1,1,n,x)代表詢問x
線段樹記錄區間最大值
然後根據區間的最大值選擇往左走還是右走
5樓：
線段樹好像比較難寫，不如嘗試分塊？
分塊就給記錄每個塊內的最大值就好，如果這塊的最大值大於了定值，就暴力掃這個塊就行。
原題的話，也不用這麼麻煩。
你用乙個權值線段樹來維護區間最大值，單點更新就好了。
query(1,l,r)表示查詢區間[l,r]的最大值，update(1,pos,val)表示更新pos的位置為a[i]
dp[i]表示以i結尾的最長長度，那麼dp[i]=max(dp[i],query(1,1,a[i]-c)+1,query(1,a[i]+c,max_val)+1)
然後再更新update(1,a[i],dp[i])就好了。
其實就是最長上公升子串行的變種。
一條線段上存在構成它的「第乙個點」和「最後乙個點」嗎
Leif 通常定義線段是閉集，如果把它看成直線的一部分，它的邊界也就是兩個端點是屬於它的。這兩個端點與其他任何點都不同，因為在它們的任意鄰域都包含這個線段以外的點 不考慮稀奇古怪的拓撲 但 第乙個 最後乙個 這種口語化的表達沒有嚴格定義，沒法給出答案。如果都用自然語言表達，隨手畫個線段，我可以把左端...
如何用數學軟體畫乙個 聖誕樹 ？
曹洪洋 這裡有用SAS畫的聖誕樹，翻譯成了Mathematica版的Clear ifs prob A init max FoldList 2.init,RandomChoice prob A,max L B Map List,100.10 5 pts ifs prob,A,init,max Abso...
Python requests如何將第乙個請求得到的 cookie 通過 POST 提交給第二個請求？
Y xx 使用with，使用session進行請求，並保證是在該with的域下。def login print 正在請求登入頁面.login page url 登入頁面的的url login html s.get login page url print 正在解析 post key get post...