【前言】
充满欺骗意味的题目。
【暴力】
记录每个羁绊是否出现,根据打法不同,复杂度亦不相同。
【比较厉害的暴力】
我们有一个稍微奇妙一点的做法。
用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; } };