分块求调

P1253 扶苏的问题

zhaohanwen @ 2023-11-13 21:19:33

记录

调试时，将块长 len 改为 n 时就没有WA，只有AC和TLE，证明对整块的处理没有问题，但是散块的处理却出现了问题，求大佬调试。

#include<bits/stdc++.h>
using namespace std;
#define CONNECT_BASE(x,y) x##y
#define CONNECT(x,y) CONNECT_BASE(x,y)
#define DEBUG_BASE(x) cerr<<#x<<'='<<x<<' '
#define DEB_1(x) DEBUG_BASE(x)
#define DEB_2(x,y) DEB_1(x),DEB_1(y)
#define DEB_3(x,y,z) DEB_1(x),DEB_2(y,z)
#define DEB_4(x,y,z,w) DEB_1(x),DEB_3(y,z,w)
#define DEB_5(a,b,c,d,e) DEB_1(a),DEB_4(b,c,d,e)
#define DEB_6(a,b,c,d,e,f) DEB_1(a),DEB_5(b,c,d,e,f)
#define COUNT_BASE(_1,_2,_3,_4,_5,_6,x,...) x
#define COUNT(...) COUNT_BASE(__VA_ARGS__,6,5,4,3,2,1,0)
#define D(...) std::cerr << "[In Line " << __LINE__ << "]: ",CONNECT(DEB_,COUNT(__VA_ARGS__))(__VA_ARGS__) , cerr << '\n'
#define nhd std::cerr << "nahida\n";
#define ll long long
#define pb push_back
#define lll __int128
#define lb lower_bound
#define ld long double
#define cnl cout<<endl;
#define R(i,n) for(int i=1;i<=n;i++)
const ll INF=LLONG_MAX;
const int N=1e6+10;
template <typename T>
inline void read(T &x)
{
   T s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   x=s*w;
}
template <typename T>
inline void write(T x)
{
    if(x<0) {
        putchar('-');
        x = -x;
    }
    if(x>9) write(x / 10);
    putchar(x % 10 + '0');
}
int n,len;
ll a[N],block[N],tag[N],id[N];
void build()
{
    fill(block,block+n+5,-INF);
    len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        id[i]=(i-1)/len+1;
        block[id[i]]=max(block[id[i]],a[i]);
    }
}
void pushdown(int k)
{
    if(tag[k]!=0)
    {
        for(int i=(k-1)*len+1;i<=k*len;i++)
        {
            a[i]=tag[k];
        }
        tag[k]=0;
    }
}
void rebuild(int k)
{
    block[k]=-INF;
    for(int i=(k-1)*len+1;i<=k*len;i++)
    {
        block[k]=max(block[k],a[i]);
    }
}
void add(int l,int r,ll w)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            a[i]+=w;
        }
        rebuild(p1);
        return ;
    }
    for(int i=l;i<=p1*len;i++)
    {
        a[i]+=w;
    }
    rebuild(p1);
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        a[i]+=w;
    }
    rebuild(p2);
    for(int i=p1+1;i<=p2-1;i++)
    {
        block[i]+=w;
        tag[i]+=w;
    }
}
void change(int l,int r,ll w)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            a[i]=w;
        }
        rebuild(p1);
        return ;
    }
    for(int i=l;i<=p1*len;i++)
    {
        a[i]=w;
    }
    rebuild(p1);
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        a[i]=w;
    }
    rebuild(p2);
    for(int i=p1+1;i<=p2-1;i++)
    {
        block[i]=w;
        tag[i]=w;
    }
}
ll query(int l,int r)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    ll ans=-INF;
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            ans=max(ans,a[i]);
        }
        return ans;
    }
    for(int i=l;i<=p1*len;i++)
    {
        ans=max(ans,a[i]);
    }
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        ans=max(ans,a[i]);
    }
    for(int i=p1+1;i<=p2-1;i++)
    {
        ans=max(ans,block[i]);
    }
    return ans;
}
signed main()
{
    int q;
    read(n);read(q);
    R(i,n) read(a[i]);
    build();
    while(q--)
    {
        int op,l,r;
        read(op);read(l);read(r);
        if(op==1)
        {
            int x;
            read(x);
            change(l,r,x);
        }
        else if(op==2)
        {
            int x;
            read(x);
            add(l,r,x);
        }
        else if(op==3)
        {
            write(query(l,r));
            putchar('\n');
        }
//      R(i,n) cerr<<a[i]<<' ';
//      cerr<<endl;
    }
    return 0;
}

by mashduihca @ 2023-11-13 21:44:49

@zhaohanwen 应该是的吧..

by zhaohanwen @ 2023-11-13 21:54:24

@mashduihca 还是寄了，60pts。

貌似没处理好加和修改的顺序，但是我不会啊，请问该怎么在保证复杂度的前提上处理好顺序？

#include<bits/stdc++.h>
using namespace std;
#define CONNECT_BASE(x,y) x##y
#define CONNECT(x,y) CONNECT_BASE(x,y)
#define DEBUG_BASE(x) cerr<<#x<<'='<<x<<' '
#define DEB_1(x) DEBUG_BASE(x)
#define DEB_2(x,y) DEB_1(x),DEB_1(y)
#define DEB_3(x,y,z) DEB_1(x),DEB_2(y,z)
#define DEB_4(x,y,z,w) DEB_1(x),DEB_3(y,z,w)
#define DEB_5(a,b,c,d,e) DEB_1(a),DEB_4(b,c,d,e)
#define DEB_6(a,b,c,d,e,f) DEB_1(a),DEB_5(b,c,d,e,f)
#define COUNT_BASE(_1,_2,_3,_4,_5,_6,x,...) x
#define COUNT(...) COUNT_BASE(__VA_ARGS__,6,5,4,3,2,1,0)
#define D(...) std::cerr << "[In Line " << __LINE__ << "]: ",CONNECT(DEB_,COUNT(__VA_ARGS__))(__VA_ARGS__) , cerr << '\n'
#define nhd std::cerr << "nahida\n";
#define ll long long
#define pb push_back
#define lll __int128
#define lb lower_bound
#define ld long double
#define cnl cout<<endl;
#define R(i,n) for(int i=1;i<=n;i++)
const ll INF=LLONG_MAX;
const int N=1e6+10;
template <typename T>
inline void read(T &x)
{
   T s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   x=s*w;
}
template <typename T>
inline void write(T x)
{
    if(x<0) {
        putchar('-');
        x = -x;
    }
    if(x>9) write(x / 10);
    putchar(x % 10 + '0');
}
int n,len;
ll a[N],block[N],tag1[N],tag2[N],id[N];
void build()
{
    fill(block,block+n+5,-INF);
    len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        id[i]=(i-1)/len+1;
        block[id[i]]=max(block[id[i]],a[i]);
    }
}
void pushdown(int k)
{
    if(tag1[k]!=0)
    {
        for(int i=(k-1)*len+1;i<=k*len;i++)
        {
            a[i]+=tag1[k];
        }
        tag1[k]=0;
    }
    if(tag2[k]!=0)
    {
        for(int i=(k-1)*len+1;i<=k*len;i++)
        {
            a[i]=tag2[k];
        }
        tag2[k]=0;
    }
}
void rebuild(int k)
{
    block[k]=-INF;
    for(int i=(k-1)*len+1;i<=k*len;i++)
    {
        block[k]=max(block[k],a[i]);
    }
}
void add(int l,int r,ll w)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            a[i]+=w;
        }
        rebuild(p1);
        return ;
    }
    for(int i=l;i<=p1*len;i++)
    {
        a[i]+=w;
    }
    rebuild(p1);
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        a[i]+=w;
    }
    rebuild(p2);
    for(int i=p1+1;i<=p2-1;i++)
    {
        block[i]+=w;
        tag1[i]+=w;
    }
}
void change(int l,int r,ll w)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            a[i]=w;
        }
        rebuild(p1);
        return ;
    }
    for(int i=l;i<=p1*len;i++)
    {
        a[i]=w;
    }
    rebuild(p1);
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        a[i]=w;
    }
    rebuild(p2);
    for(int i=p1+1;i<=p2-1;i++)
    {
        block[i]=w;
        tag2[i]=w;
    }
}
ll query(int l,int r)
{
    int p1=id[l],p2=id[r];
    pushdown(p1);pushdown(p2);
    ll ans=-INF;
    if(p1==p2)
    {
        for(int i=l;i<=r;i++)
        {
            ans=max(ans,a[i]);
        }
        return ans;
    }
    for(int i=l;i<=p1*len;i++)
    {
        ans=max(ans,a[i]);
    }
    for(int i=(p2-1)*len+1;i<=min(r,n);i++)
    {
        ans=max(ans,a[i]);
    }
    for(int i=p1+1;i<=p2-1;i++)
    {
        ans=max(ans,block[i]);
    }
    return ans;
}
signed main()
{
    int q;
    read(n);read(q);
    R(i,n) read(a[i]);
    build();
    while(q--)
    {
        int op,l,r;
        read(op);read(l);read(r);
        if(op==1)
        {
            int x;
            read(x);
            change(l,r,x);
        }
        else if(op==2)
        {
            int x;
            read(x);
            add(l,r,x);
        }
        else if(op==3)
        {
            write(query(l,r));
            putchar('\n');
        }
//      R(i,n) cerr<<a[i]<<' ';
//      cerr<<endl;
    }
    return 0;
}

by waauto @ 2023-11-13 21:59:18

先修改后加，修改的时候把加的tag清空

by zhaohanwen @ 2023-11-13 22:04:36

@waauto 太谢谢了！改完之后 90pts，最后一个点 \texttt{TLE} 了，估计 O(n \sqrt n) 跑 n=10^6,2s 需要卡卡常。

by zhaohanwen @ 2023-11-13 22:34:26

@waauto @mashduihca 现在卡常卡不过去了......

是 O(q \sqrt n) 过不了 10^6 吗？我看到讨论区有最后一个点 1.36s 而且没开 \texttt{O2} 的。

能帮忙找下可以优化的地方吗？目前已经加了 fread + 能开 int 的全开 int 了......

by mashduihca @ 2023-11-13 22:44:16

@zhaohanwen 那个，为什么 q\sqrt n 能过 1e6.

by zhaohanwen @ 2023-11-14 07:35:46

@mashduihca 但是讨论区有过的。

by mashduihca @ 2023-11-14 07:38:55

@zhaohanwen haoba

by zhaohanwen @ 2023-11-14 08:03:27

@mashduihca 我想想，最后一个点有区间推平，是不是可以用 ODT 艹过去。（assert检查了一下）

by zhaohanwen @ 2023-11-14 14:04:55

@mashduihca ODT+分块艹过去了。

（暴力数据结构的胜利！）

上一页 | 下一页