魔のkyo的BLOG

// 预处理字符串s，得到所有s任意后缀即s[i:]和s[j:]的所有最长公共前缀
class LCP {
    vector<vector<int>> dp;
public:
    LCP(const string& s) {
        dp.resize(s.size()+1, vector<int>(s.size()+1));
        for(int j=s.size()-1;j>=0;j--) {
            for(int i=j;i>=0;i--) {
                dp[i][j]=(s[i]==s[j]?dp[i+1][j+1]+1:0);
            }
        }
    }

    int operator()(int i, int j) const {
        return dp[min(i,j)][max(i,j)];
    }
};

class Solution {
public:
    int deleteString(string s) {
        int n = s.size();
        // 用dp[i] 表示删除s[i:]的最大操作次数
        // 删除一个长度为j的前缀之后得到的是一个子问题：s[i+j:]的最大操作次数
        // 能删除s[i:i+j]的前提是s[i:i+j]==s[i+j:i+j+j]
        vector<int> dp(n, 1);
        for(int i=n-2;i>=0;i--) {
            for(int j=1;j<=(n-i)/2;j++) {
                if(memcmp(&s[i], &s[i+j], j) == 0) { // s[i:i+j]==s[i+j:i+j+j]
                    dp[i] = max(dp[i], 1+dp[i+j]);
                }
            }
        }
        return dp[0];
    }
};

class Solution {
public:
    int deleteString(string s) {
        int n = s.size();
        // 用dp[i] 表示删除s[i:]的最大操作次数
        // 删除一个长度为j的前缀之后得到的是一个子问题：s[i+j:]的最大操作次数
        // 能删除s[i:i+j]的前提是s[i:i+j]==s[i+j:i+j+j]
        LCP lcp(s);
        vector<int> dp(n, 1);
        for(int i=n-2;i>=0;i--) {
            for(int j=1;j<=(n-i)/2;j++) {
                if(lcp(i, i+j)>= j) { // s[i:i+j]==s[i+j:i+j+j]
                    dp[i] = max(dp[i], 1+dp[i+j]);
                }
            }
        }
        return dp[0];
    }
};

//一个节点的初始大小
const int NODESIZE=160; //如果数据大小最大为n，取在sqrt(n)/2会比较好，对于10w的数据这个大小应该比较优
//加上缓冲区一个节点应该占用NODESIZE*2的空间
//任何一个节点大小不会>=NODESIZE*2，任何两个相邻的节点大小不会<=NODESIZE

template<typename T>
class BlockList{
public:
    struct BLNode{
        T data[NODESIZE<<1];
        int size;//该结点中已经使用的大小
        BLNode* next;
        BLNode():size(0),next(NULL){}
    };
    BLNode* _head;
    BLNode* _tail;
    int _size; //整个表中的元素数

    void split(BLNode* p){
        BLNode* q = new BLNode();
        q->next = p->next;
        p->next = q;
        memcpy(q->data, p->data+NODESIZE, sizeof(T)*(p->size-NODESIZE));
        q->size = p->size-NODESIZE;
        p->size = NODESIZE;
        if(_tail == p) _tail = q;
    }

    void join(BLNode* p, BLNode* q) {
        memcpy(p->data+p->size, q->data, sizeof(T)*q->size );
        p->size += q->size;
        p->next = q->next;
        if(_tail == q) _tail = p;
        delete q;
    }
public:
    BlockList(int size=0, const T& val=T()):_size(size) {
        _head = _tail = new BLNode();
        if(size != 0) {
            while(size>NODESIZE){
                std::fill(_tail->data, _tail->data+NODESIZE, val);
                size -= NODESIZE;
                _tail->size = NODESIZE;
                if(!_tail->next) {
                    _tail->next = new BLNode();
                }
                _tail = _tail->next;
            }
            std::fill(_tail->data, _tail->data+size, val);
            _tail->size = size;
        }
    }
    int size(){return _size;}
    
    //通过下标随机访问，复杂度O(sqrt(size))
    T& operator [] (int i){
        assert(0<=i && i<_size);
        BLNode* p = _head;
        while(i>=p->size){
            i -= p->size;
            p = p->next;
        }
        return p->data[i];
    }

    //在尾部追加数据
    void push_back(const T& d) {
        _size++;
        _tail->data[_tail->size++] = d;
        if(_tail->size==(NODESIZE<<1)){
            split(_tail);
        }
    }
    
    //在下标i处插入数据d，原数据依次后移
    void insert(int i, const T& d){
        assert(0<=i && i<=_size);
        _size++;
        BLNode* p=_head;
        while(i>p->size){
            i -= p->size;
            p = p->next;
        }
        for(int j=p->size-1; j>=i; j--){
            p->data[j+1]=p->data[j];
        }
        p->data[i]=d;
        p->size++;
        if(p->size==(NODESIZE<<1)){
            split(p);
        }
    }

    //删除在下标i处的数据，后续数据依次前移
    void erase(int i){
        assert(0<=i && i<_size);
        _size--;
        BLNode* p=_head;
        while(i>=p->size){
            i -= p->size;
            p = p->next;
        }
        for(int j=i;j<p->size-1;j++){
            p->data[j]=p->data[j+1];
        }
        p->size--;
        BLNode* q = p->next;
        if(q && p->size+q->size<=NODESIZE){
            join(p, q);
        }
    }
};

typedef long long ll;

template<typename T>
class ChthollyTree {
private:
    struct ChthollyNode {
        ll l, r;
        mutable T w;
        ChthollyNode(ll l, ll r=0, const T& w=T()): l(l),r(r),w(w) {}
        bool operator < (const ChthollyNode& n) const {
            return l < n.l;
        }
    };
    set<ChthollyNode> s;
public:
    ChthollyTree(ll n=1e9+2, const T& v=T()) { s.insert(ChthollyNode(-1, n, v)); }

    auto split(ll pos) {
        auto itr = s.lower_bound(pos);
        if (itr != s.end() && itr->l == pos) return itr;
        --itr;
        auto l = itr->l;
        auto r = itr->r;
        auto w = itr->w;
        s.erase(itr);
        s.insert(ChthollyNode(l, pos, w));
        return s.insert(ChthollyNode(pos, r, w)).first;
    }

    void update(ll l, ll r, function<void(ChthollyNode&)> f) {
        auto right = split(r), left = split(l);
        for(auto itr = left; itr != right; itr++) {
            f(const_cast<ChthollyNode&>(*itr));
        }
    }

    void assign(ll l, ll r, const T& w) {
        auto right = split(r), left = split(l);
        s.erase(left, right);
        s.insert(ChthollyNode(l, r, w));
    }

    void visit(ll l, ll r, function<void(const ChthollyNode&)> f) {
        auto left = s.lower_bound(l);
        if (left == s.end() || left->l != l) --left;
        auto right = s.lower_bound(r);
        for(auto itr = left; itr != right; itr++) {
            f(*itr);
        }
    }

private:
    class ItemAccessor {
    public:
        ItemAccessor(ChthollyTree& ct, ll i): ct(ct), i(i) {}
        ItemAccessor& operator = (const T& x) {ct.assign(i, i+1, x);return *this;}
        ItemAccessor& operator += (const T& x) {ct.update(i, i+1, [x](auto& p){p.w += x;});return *this;}
        ItemAccessor& operator -= (const T& x) {ct.update(i, i+1, [x](auto& p){p.w -= x;});return *this;}
        operator T() const {T r;ct.visit(i, i+1, [&r](auto& p){r = p.w;}); return r;}
    private:
        ChthollyTree& ct;
        ll i;
    };

    class RangeAccessor {
    public:
        RangeAccessor(ChthollyTree& ct, ll b, ll e):ct(ct), b(b), e(e) {}
        void operator = (const T& x) {ct.assign(b, e, x);}
        void operator += (const T& x) {ct.update(b, e, [&x](auto& p){p.w += x;});}
        void operator -= (const T& x) {ct.update(b, e, [&x](auto& p){p.w -= x;});}
    private:
        ChthollyTree& ct;
        ll b;
        ll e;
    };

public:
    // 通过下标访问单点值的语法糖
    ItemAccessor operator [] (ll i) {
        return ItemAccessor(*this, i);
    }

    // 通过下标访问区间值的语法糖
    RangeAccessor operator [] (const tuple<ll, ll>& range) {
        return RangeAccessor(*this, std::get<0>(range), std::get<1>(range));
    }

    T sum(ll l, ll r) {
        T ret = 0;
        visit(l, r, [&](auto& p) {
            ret += p.w * (std::min(p.r, r)-std::max(p.l, l));
        });
        return ret;
    }

    T min(ll l, ll r) {
        bool first = true;
        T ret = 0;
        visit(l, r, [&](auto& p) {
            if(first) {
                first = false;
                ret = p.w;
            } else {
                ret = std::min(ret, p.w);
            }
        });
        return ret;
    }
    
    T max(ll l, ll r) {
        bool first = true;
        T ret = 0;
        visit(l, r, [&](auto& p) {
            if(first) {
                first = false;
                ret = p.w;
            } else {
                ret = std::max(ret, p.w);
            }
        });
        return ret;
    }
};

template<typename T, typename Cmp=less<int>>
class RMQ {
    vector<vector<T>> dp; //dp[i][j]表示从a[i]起连续2^j次方个数的最值

    static int ceil_log2(int n) {
        int r = 0;
        while((1<<r)<n) r++;
        return r;
    }

    static int floor_log2(int n) {
        int r = 0;
        while((1<<r)<=n) r++;
        return r-1;
    }

    int max_or_min(const T& a, const T& b) const {
        return Cmp()(a, b)?a:b;
    }

public:
    RMQ() = default;
    RMQ(const T* a, int n) {init(a, n);}
    RMQ(const vector<T>& a) {init(&a[0], a.size());}

    void init(const T* a, int n) {
        dp.resize(n, vector<T>(ceil_log2(n)+1));
        for(int i=0;i<n;i++){
            dp[i][0] = a[i];
        }
        for(int j=1,s=1;s<n;s=(1<<j++)){
            for(int i=0;i+s<n;i++){
                dp[i][j] = max_or_min(dp[i][j-1], dp[i+s][j-1]);
            }           
        }
    }
    
    //返回[i, j]范围内的最值
    T query(int i, int j) const {
        assert(i<=j);
        int k = floor_log2(j-i+1);
        return max_or_min(dp[i][k], dp[j-(1<<k)+1][k]);
    }
};

template<typename T>
using RMinQ = RMQ<T, less<T>>;
template<typename T>
using RMaxQ = RMQ<T, greater<T>>;

// 二维向量
struct v2d {
    double x;
    double y;
};

// 二维向量拟叉积运算
double pseudoCross(const v2d& v1, const v2d& v2) {
    return v1.x * v2.y - v1.y * v2.x;
}

v2d operator - (const v2d& v1, const v2d& v2) {
    return v2d{v1.x-v2.x, v1.y-v2.y};
}

// 返回一个逆时针围成的凸包（如果要顺时针可以把上下边界换一换，改变while中的比较就可以）
vector<v2d> convexHull(vector<v2d>& pnts) {
    sort(pnts.begin(), pnts.end(), [](const v2d& v1, const v2d& v2) {
        return ((v1.x != v2.x)?(v1.x< v2.x):(v1.y < v2.y));
    });
    int n = pnts.size();
    vector<int> v(n*2); // v 其实是两个单调栈在中间接起来
    int p = n; // 从v中间向后增长的单调栈, p为栈顶的下一个位置（将要被使用的空间）
    int q = n; // 从v中间向前增长的单调栈, q为栈顶的下一个位置（将要被使用的空间）
    for(int i=0; i<n; i++){
        while(p-n>=2 && pseudoCross(pnts[i]-pnts[v[p-1]], pnts[v[p-1]]-pnts[v[p-2]])>=0){
            p--; // 弯曲方向不对，出栈
        }
        while(n-q>=2 && pseudoCross(pnts[i]-pnts[v[q+1]], pnts[v[q+1]]-pnts[v[q+2]])<=0){
            q++; // 弯曲方向不对，出栈
        }
        v[p++] = i;
        v[q--] = i;
    }
    vector<v2d> res;
    for(int i=q+1;i<p-1;i++) {
        res.push_back(pnts[v[i]]);
    }
    return res;
}