ST表 get ！

A4paper · 2018-09-18 19:42:20 · 个人记录

突然发现一直倍增倍增却忘了练ST表。。。

算了，先拍模板。

void build_ST()
{
    for(int i=1;i<=n;i++)   ST[i][0] = a[i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            fa[j][i] = max(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
}

void query(int l, int r)
{
    int x = log2(r-l+1);
    cout << max(ST[l][x],ST[r-(1<<x)+1][x]) << endl;
}

int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)   cin >> a[i];
    build_ST();
    for(int i=1,L,R;i<=m;i++)
    {
        cin >> L >> R;
        query(L,R);
    }
    return 0;
}

思路和倍增差不多，就不多解释了。。。

高端：

传送门

一道很有思维难度的题

简单来说，就是找前 k 大连续子区间和，且区间长度有范围。

那么现在有如下几个个任务：

1. 查询所有符合范围的子区间。
2. 统计区间和。
3. 找前k大值。

由于数据范围过大，每个任务都 O(n) 跑显然会 T

所以我们想办法优化，

对于任务 2 ，我们可以用前缀和优化，

对于任务 3 ， 我们可以用堆，

对于任务 1 ， 结合题意可以看出我们要不断维护区间最值，所以用 ST 表

详情请看注释：

Long n,k,l,r,ans;
Long a[MAXN];
int  ST[MAXN][20];

struct node{
    Long L,R         //左端点的合法区间
    Long v,u,sum;   //右端点、当前最优左端点、ans
};
priority_queue <node,vector<node> >que;

bool operator<(node a, node b){
    return a.sum < b.sum;
}
int min(int x, int y){     //注意这个函数
    return a[x]<a[y] ? x : y;//ST表内存的是位置，不能直接比较
}

void In(Long L, Long R, Long v) //左端点的合法区间、右端点
{
    node p;
    Long m = log2(R-L+1);
    p.L = L;    p.R = R;    p.v = v;
    if(L == R)  p.u = L;
    else        p.u = min(ST[L][m],ST[R-(1<<m)+1][m]);
    p.sum = a[v]-a[p.u];
    que.push(p);//求出了右端点确定时，区间内最优值
}

int main(void)
{
    cin >> n >> k >> l >> r;
    for(Long i=1;i<=n;i++)
    {
        cin >> a[i];
        a[i] += a[i-1];
        ST[i][0] = i;   //ST表内记录每个数的位置
    }
    for(Long i=1;(1<<i)<=n;i++)
    for(Long j=0;j+(1<<i)-1<=n;j++)
        ST[j][i] = min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
    for(Long i=l;i<=n;i++)  //i是右端点的位置
    {
        Long _L = max(i-r,(Long)0); //左端点最小值
        Long _R = i-l;               //左端点最大值
        In(_L,_R,i);
    }
    for(Long i=1;i<=k;i++)
    {
        node t = que.top(); que.pop();
        ans += t.sum;
        if(t.L <= t.u-1)    In(t.L,t.u-1,t.v);
        if(t.R >= t.u+1)    In(t.u+1,t.R,t.v);
        //这里将t.v对应的最优值取出后，将较优值不断存入
    }
    cout << ans;
    return 0;
}