羁绊计算问题题解

【前言】
充满欺骗意味的题目。
【暴力】
记录每个羁绊是否出现，根据打法不同，复杂度亦不相同。
【比较厉害的暴力】
我们有一个稍微奇妙一点的做法。
用f[i]表示i与i+1到f[i]都建立了羁绊，可以发现f[i]具有单调性，那么在暴力的过程中，f[i]>=r则可以退出了。
这样的话可以优化不少，但还不够。
【正解】
我们还是用f[i]表示相同的东西，但这一次，我们用一些数据结构来维护区间最大值、最小值、区间和。
复杂度O(mlogn)

参考代码：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型二维数组 
     * @param aRowLen int a数组行数
     * @param aColLen int* a数组列数
     * @return long长整型vector
     */
    long long ans;
    long long f[300005*4][4];
    vector<long>v;
    void combine(int s)
    {
        f[s][0]=f[s+s][0]+f[s+s+1][0];
        f[s][1]=max(f[s+s][1],f[s+s+1][1]);
        f[s][3]=min(f[s+s][3],f[s+s+1][3]);
    }
    void build(int l,int r,int s)
    {
        if (l==r){
            f[s][0]=l,f[s][1]=l,f[s][3]=l;
            return;
        }
        build(l,(l+r)/2,s+s),build((l+r)/2+1,r,s+s+1);
        combine(s);
    }
    void down(int l,int r,int s){
    if (f[s][2]){
        f[s][1]=f[s][2];
        f[s][0]=f[s][2]*(r-l+1);
        f[s][3]=f[s][2];
        if (l!=r)
            f[s+s][2]=f[s][2],f[s+s+1][2]=f[s][2];
        f[s][2]=0;
    }
    }
    void get(int l,int r,int s,int ll,int rr,int v){
    down(l,r,s);
    if (r<ll||rr<l)return;
    if (f[s][3]>=v)return;
    if (ll<=l&&r<=rr){
        if (f[s][1]<=v){
            f[s][2]=v;
            ans+=(long long)v*(r-l+1)-f[s][0];
            down(l,r,s);
            return;
        }
    }
    get(l,(l+r)/2,s+s,ll,rr,v),get((l+r)/2+1,r,s+s+1,ll,rr,v);
    combine(s);
    }
    vector<long> wwork(int n, int m, int** a, int aRowLen, int* aColLen) {
        // write code here
        build(1,n,1);
        int l,r;
        for (int i=1;i<=m;i++)
        {
            l=a[i-1][0];
            r=a[i-1][1];
            ans=0;
            get(1,n,1,l,r,r);
            v.push_back(ans);
        }
        return v;
    }
};