cf1208 E Let Them Slide(差分+RMQ\单调队列)

 

题意

如题目的图所示,每行都可以左右移动,但是数字不允许断开,且不许越界(宽度为w)。

单独求每一列的最大的和为多少。

 

思路

对于每一列来说,在每一行上都有一个可以取到的区间,

所以,对于一列来说,答案就是每行的区间最大值的和。区间最大值可以用RMQ或者单调队列求。

一开始题目看错了,以为是w*n<=1e6,其实是w<=1e6,n<=1e6,Σleni<=1e6(leni为第i行的长度),直接上w*n*log,果断T了。

显然,当leni 比w小很多时,中间会有很多列都可以取到整行的所有数字,所以对于这些列,它们求的区间最大值,其实就是整行的最大值。

对于头尾的一些列,取不到所有数字,那我们就暴力算出它们可以取到的区间,然后查询。

由于w*n<=1e12,而中间那些列查出来的最大值其实是一样的,所以可以用差分。

 

(一些细节)

有时候查询出来的区间最大值是负数,但是有时候其实可以取到0(移到空格),而有时候只能取负数(移不到空格)。

len <= i <= w - len + 1 符合条件的第i列可以取到整行

当整行都为负数时,

有时候第len列和第(w-len+1)列只能取负数,

但是,第len+1列和第(w-len+1 - 1)列一定可以取到空格,也就是0

所以,我们把第len列和第(w-len+1)列,归为暴力算的部分,因为暴力算的时候,都有特判是否可以取0。

这样,中间的那些就可以直接max(0,rmq(1,len))了

 

代码(RMQ)

(我的姿势比较差,代码又长,跑的还慢,跑了700+ms)

 

cf1208 E Let Them Slide(差分+RMQ\单调队列)
#include <stdio.h>
#include <queue>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <set>
using namespace std;
typedef long long int ll;
const int maxn = 1e6 + 10;
const int inf = 70000000;
const ll mod = 998244353;
const ll seed = 131;
int st[maxn][20],mm[maxn],b[maxn];
void initRMQ(int n)
{
    mm[0] = -1;
    for(int i = 1;i <= n;i++){
        mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1:mm[i - 1];
        st[i][0] = b[i];
    }
    for(int j = 1;j <= mm[n];j++){
        for(int i = 1;i + (1 << j) - 1 <= n;i++){
            st[i][j] = max(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int rmq(int x,int y)
{
    int k = mm[y - x + 1];
    return max(st[x][k],st[y - (1 << k) + 1][k]);
}
ll ans[maxn];
int main()
{
    int n,w,len,l,r;
    ll temp;
    while(scanf("%d%d",&n,&w) != EOF){
        memset(ans,0,sizeof(ans));
        while(n--){
            scanf("%d",&len);
            for(int i = 1;i <= len;i++){
                scanf("%d",&b[i]);
            }
            initRMQ(len);

            //i <= w - len + 1
            //i >= len
            //len <= i <= w - len + 1 符合条件的第i列可以取到整行
            int cnt = w,flag = 0;

            //中间
            if(len + 1 <= w - len + 1 - 1){
                temp = max((ll)rmq(1,len),(ll)0);
                ans[len + 1] += temp;
                ans[w - len + 1] -= temp;
                cnt = len;
                flag = 1;
            }

            //头
            for(int i = 1;i <= cnt;i++){
                if(len >= i)
                    r = i;
                else
                    r = len;
                if(w - len < i)//w-len+l=i
                    l = i - (w - len);
                else
                    l = 1;

                temp = rmq(l,r);
                if(temp < 0){
                    if(len < i || (w - len) >= i)
                        temp = 0;
                }
                ans[i] += temp;
                ans[i + 1] -= temp;
            }

            //尾
            if(!flag)
                cnt = len;
            else
                cnt = 0;
            for(int i = w - len + 1 + cnt;i <= w;i++){
                if(len >= i)
                    r = i;
                else
                    r = len;
                if(w - len < i)//w-len+l=i
                    l = i - (w - len);
                else
                    l = 1;

                temp = rmq(l,r);
                if(temp < 0){
                    if(len < i || (w - len) >= i)
                        temp = 0;
                }
                ans[i] += temp;
                ans[i + 1] -= temp;
            }
        }

        for(int i = 1;i <= w;i++){
            ans[i] += ans[i - 1];
            printf("%lld ",ans[i]);
        }
        puts("");
    }
    return 0;
}
View Code

 

 

 

还有单调队列版的,等我过了再来更新

 

上一篇:白条取现怎么取不了呀


下一篇:php数组去重复代码