[TIOJ 1899][IOI 2014] Holiday

原題連結
這道題我一開始以為可以用枚舉和dp去寫，但是複雜度怎麼壓都壓不下來......最後是聽了大神同學的提示才發現我枚舉錯東西了.....枚舉天數去做合併大概是沒救的......
實際的作法是這樣的：
WLOG,我們知道答案的形式一定是從起點(st)往左走到某點(L)再往右走到某點(R)，並且若確定了L和R，那麼我們可以直接計算出對應的答案，方法是將L~R上所有點的權值丟進max_heap裡並拿出前(可用觀賞天數)大的那些元素加總

於是便有了樸素作法：

枚舉所有L,R，對於每組L,R我們可以在(max(n,k)*lgn)的時間內計算答案，總時間O(n^3lgn)，相當悽慘。

我們的目標是要將算法優化至n=100000時仍可以通過的等級。
先對於我們計算答案的方式做一些分析，有點經驗的人不難發現，這是一個「區間前k大總和」的問題，可以利用持久化權值線段樹或是離線BIT配合區間總和查詢去實做，時間複雜度變為預處理O(nlogc)，查詢O(lgc)(離散化後 lgc->lgn)

這樣我們有了一個O(n^2lgc)的作法，顯然還不夠。如果不能跳脫要枚舉所有L,R的窘境，時間複雜度就無法降低。

接下來的思考比較吃經驗。我們將起點左邊開始往左走遇到的點叫做L_0,L_1.....，向右走遇到的點叫做R_0,R_1......。
令L_i的最優決策點編號為f(L_i)。(對於L_i，在所有的R中(L_i,R_f(L_i))所計算出的答案是最大的)
則我們有以下結論： 對於i>j，有 f(L_i)<f(L_j)，也就是我們L往左枚舉的同時，相對應的決策點R也會往左移動。
套用遞迴框架solve(L,R,optL,optR)代表當前處理左半邊[L,R]區間，最優決策點落於右半邊的[optL,optR]區間，每層遞迴我們計算中點M=(L+R)/2;並且找出他對應的最優決策點optM，紀錄答案後再遞迴呼叫solve(L,M-1,optL,optM),solve(M+1,R,optM,optR)
容易知道最多有logn層遞迴，每層時間為O(n)，時間複雜度從枚舉O(n^2)變為O(nlgn)

最後我們獲得了一個時間複雜度O(nlgnlgc)，空間複雜度O(nlgc)的作法(離散化後 lgc->lgn)
時間上已經足以通過測資，但是空間需要常數級的優化才能通過原題的限制(64MB)，如果持久化的寫法稍有不佳就可能會MLE.....

//#define TIOJ
#ifdef TIOJ
#include "lib1899.h"
#else
#include "holiday.h"
#endif

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int maxn=100000+5;
const int maxnode=2000000;
const int INF=(1LL<<60);
struct Node
{
    int lc,rc,size;
    LL Sum;
    Node() {Sum=size=lc=rc=0;}
};
vector<int> disc;
int root[maxn],pmem;
Node mem[maxnode];
int newnode(Node& last)
{
    Node& now=mem[pmem];
    now.lc=last.lc,now.rc=last.rc;
    now.Sum=last.Sum,now.size=last.size;
    return pmem++;
}
void pull(Node& now)
{
    now.Sum=mem[now.lc].Sum+mem[now.rc].Sum;
    now.size=mem[now.lc].size+mem[now.rc].size;
}
void insert(int last,int& cur,int L,int R,LL num)
{  
    cur=newnode(mem[last]);
    Node& now=mem[cur];
    if(L==R) {now.Sum+=disc[num],now.size++;return;}
    LL M=(L+R)>>1;
    if(num<=M) insert(mem[last].lc,now.lc,L,M,num);
    else insert(mem[last].rc,now.rc,M+1,R,num);
    pull(now);
}
LL query(int lt,int rt,LL L,LL R,LL k)
{
    if(L==R) return (LL)disc[L] * min( k ,(LL) mem[rt].size - mem[lt].size );
    LL M=(L+R)>>1,rsize= mem[mem[rt].rc].size - mem[mem[lt].rc].size,rsum=mem[mem[rt].rc].Sum-mem[mem[lt].rc].Sum;
    if(rsize >=k) return query(mem[lt].rc,mem[rt].rc,M+1,R,k);
    return query(mem[lt].lc,mem[rt].lc,L,M,k-rsize)+rsum;
}
inline void buildSeg(int n,int attraction[])
{
    root[0]=0;pmem=1;
    for(LL i=1;i<=n;i++)
        insert(root[i-1],root[i],0,disc.size()-1,lower_bound(disc.begin(),disc.end(),attraction[i-1])-disc.begin());
}
LL solve(int start,int day,int L,int R,int optL,int optR)
{
    LL M=(L+R)>>1,optM=optL,ret=-INF;
    for(int i=optL;i<=optR;i++)
    {
        LL now=query(root[M],root[i+1],0,disc.size()-1, day - (start-M + i-M) );
        if(now>ret) ret=now,optM=i;
    }
    if(L<=M-1) ret=max(ret,solve(start,day,L,M-1,optL,optM));
    if(M+1<=R) ret=max(ret,solve(start,day,M+1,R,optM,optR));
    return ret;
}
LL findMaxAttraction(int n,int start,int day,int attraction[])
{
    disc.clear();
    for(int i=0;i<n;i++) disc.push_back(attraction[i]);
    sort(disc.begin(),disc.end());
    disc.resize(unique(disc.begin(),disc.end())-disc.begin());

    buildSeg(n,attraction);
    LL ans =solve(start,day,0,start,start,n-1);
    
    start=n-start-1;reverse(attraction,attraction+n); 
    buildSeg(n,attraction);
    ans=max(ans,solve(start,day,0,start,start,n-1));    
    return ans;

}