[TIOJ] 1941. 直升機抓寶 (Helicopter)
題目連結: https://tioj.infor.org/problems/1941 這題應該可以輕鬆想到$O(N^2)$的DP方式，同時也會發現那樣子太慢。 仔細觀察DP的表格後，發現他是一個單調的表格，也就是由左至右遞增，同時由下至上遞增，接著研究一下每個轉移對DP表格的貢獻，發現他必定會將他自己那個區間的DP值+1，而後面則為了要維護單調的性質，會再跟他取max。 那這類題目，其實我們可以維護每一段的DP值，每次加入一個新的轉移來源後，也代表加入了一個斷點，但是同時也有可能把自身後面的斷點吃光光。 所以複雜度會是$O(N log N)$，因為每個斷點只會出現跟消失一次，而單次新增跟刪除了複雜度都是$O(log N)$ #include <bits/stdc++.h>
using namespace std;
class BIT{
private:
int n;
vector<int> arr;
inline int lowbit(int x){return x&(-x);}
void modify(int p, int x){
for(;p;p-=lowbit(p)) arr[p] += x;
}
public:
void init(int n_){
n = n_; arr.clear();
arr.resize(n);
}
void modify(int l, int r, int v){
modify(l, -v);
modify(r, v);
}
int query(int x){
int ret = 0;
for(;x<n;x+=lowbit(x)) ret += arr[x];
...