问一下各位大佬分块能过吗？

Brandon鹏 @ 2018-07-14 17:02:20

// luogu-judger-enable-o2
#include<cstdio>
#include<cmath>
int a[1000001];
int home[1000001];
int n,m;
char x;
struct node
{
    int l;
    int r;
    int biao;
}kuai[1010];
int ge;
int ans;
int l,r,w,c;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int len=(int)sqrt(n+0.0);
    kuai[1].l=1;
    kuai[1].r=len;
    if(n%len==0)
    {
        ge=n/len;
        for(int i=2;i<=ge;i++)
        {
            kuai[i].l=kuai[i-1].l+len;
            kuai[i].r=kuai[i-1].r+len;
        }
    }
    else
    {
        ge=n/len+1;
        for(int i=2;i<ge;i++)
        {
            kuai[i].l=kuai[i-1].l+len;
            kuai[i].r=kuai[i-1].r+len;
        }
        kuai[ge].l=kuai[ge-1].l+len;
        kuai[ge].r=n;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=ge;j++)
        {
            if(kuai[j].l<=i&&kuai[j].r>=i)
            {
                home[i]=j;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("\n%c",&x);
        if(x=='M')
        {
            scanf("%d%d%d",&l,&r,&w);
            if(home[l]!=home[r])
            {
                for(int t=l;t<=kuai[home[l]].r;t++)
                {
                    a[t]+=w;
                }
                for(int t=kuai[home[r]].l;t<=r;t++)
                {
                    a[t]+=w;
                }
                for(int t=home[l+1];t<=home[r-1];t++)
                {
                    kuai[t].biao+=w;
                }
            }
            else
            {
                for(int t=l;t<=r;t++)
                {
                    a[t]+=w;
                }
            }
        }
        if(x=='A')
        {
            ans=0;
            scanf("%d%d%d",&l,&r,&c);
            for(int t=l;t<=r;t++)
            {
                if(a[t]+kuai[home[t]].biao>=c)
                {
                    ans++;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

by Rye_Catcher @ 2018-07-14 17:29:59

能过

by zltttt @ 2018-07-14 17:32:08

能

by Brandon鹏 @ 2018-07-14 17:33:57

希望各位大佬帮忙看一下上面的分块，这是模拟的，居然90分

#include<cstdio>
int n,m;
int a[1000001];
char x;
int l,r,w,c;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("\n%c",&x);
        if(x=='M')
        {
            scanf("%d%d%d",&l,&r,&w);
            for(int j=l;j<=r;j++)
            {
                a[j]+=w;
            }
        }
        if(x=='A')
        {
            int ans=0;
            scanf("%d%d%d",&l,&r,&c);
            for(int j=l;j<=r;j++)
            {
                if(a[j]>=c)
                {
                    ans++;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

by Brandon鹏 @ 2018-07-14 17:34:46

@zltttt 问一下大佬怎么过呢？上面的代码有什么问题呢？

by zltttt @ 2018-07-14 18:07:08

@Brandon鹏 你的询问是O(n)的当然会超时...... 然后整块修改出的下标还有问题......

by zltttt @ 2018-07-14 18:15:34

@Brandon鹏

这样至少不会Wa了

剩下的问题是优化询问的复杂度，这个最好自己想或者看题解

#include<cstdio>
#include<cmath>
int a[1000001];
int home[1000001];
int n,m;
char x;
struct node
{
    int l;
    int r;
    int biao;
}kuai[1010];
int ge;
int ans;
int l,r,w,c;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int len=(int)sqrt(n+0.0);
    kuai[1].l=1;
    kuai[1].r=len;
    if(n%len==0)
    {
        ge=n/len;
        for(int i=2;i<=ge;i++)
        {
            kuai[i].l=kuai[i-1].l+len;
            kuai[i].r=kuai[i-1].r+len;
        }
    }
    else
    {
        ge=n/len+1;
        for(int i=2;i<ge;i++)
        {
            kuai[i].l=kuai[i-1].l+len;
            kuai[i].r=kuai[i-1].r+len;
        }
        kuai[ge].l=kuai[ge-1].l+len;
        kuai[ge].r=n;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=ge;j++)
        {
            if(kuai[j].l<=i&&kuai[j].r>=i)
            {
                home[i]=j;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("\n%c",&x);
        if(x=='M')
        {
            scanf("%d%d%d",&l,&r,&w);
            if(home[l]!=home[r])
            {
                for(int t=l;t<=kuai[home[l]].r;t++)
                {
                    a[t]+=w;
                }
                for(int t=kuai[home[r]].l;t<=r;t++)
                {
                    a[t]+=w;
                }
                for(int t=home[l]+1;t<=home[r]-1;t++)
                {
                    kuai[t].biao+=w;
                }
            }
            else
            {
                for(int t=l;t<=r;t++)
                {
                    a[t]+=w;
                }
            }
        }
        if(x=='A')
        {
            ans=0;
            scanf("%d%d%d",&l,&r,&c);
            for(int t=l;t<=r;t++)
            {
                if(a[t]+kuai[home[t]].biao>=c)
                {
                    ans++;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

by Brandon鹏 @ 2018-07-17 21:17:41

谢谢了

by Brandon鹏 @ 2018-07-18 10:04:34

@Brandon鹏 居然把分块搞错了还混了那么多分，无语了。

by Brandon鹏 @ 2018-07-18 10:16:20

@Brandon鹏 话说我想到的优化方法有两种，一种是找出最大值，如果小整块跳，一种是排序查找，但是好像又T了啊，题解说是二分，但是我写的太腐朽了，不敢敲。