关于各类分块做法

critnos @ 2020-08-11 12:33:26

by Andy_chen @ 2020-08-11 13:45:49

stO 26535 Orz

顺便这个做法好玄学呀

by Spasmodic @ 2020-08-11 13:46:08

wc，放错代码了

/*
作者：hqztrue
链接：https://www.zhihu.com/question/300065962/answer/519188661
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
inline int max(int x,int y){int m=(x-y)>>31;return y&m|x&~m;}
inline int min(int x,int y){int m=(y-x)>>31;return y&m|x&~m;}
const int N=100105,D_max=18,L=27,inf=1<<30;
int f[N/L][D_max],M[N/L],a[N+L],stack[L+1],n,q,D;
struct node{
    int state[L+1],*a;
    int Qmin(int x,int y){return a[x+__builtin_ctz(state[y]>>x)];}
    void init(int *_a){
        int top=0;a=_a;
        for (int i=1;i<=L;++i){
            state[i]=state[i-1];
            while (top&&a[i]<=a[stack[top]])state[i]-=1<<stack[top],--top;
            stack[++top]=i;state[i]+=1<<i;
        }
    }
}c[N/L];
void build(){
    int nn=n/L;M[0]=-1;
    for (int i=1;i<=nn;++i){
        f[i][0]=inf;for (int j=1;j<=L;++j)f[i][0]=min(f[i][0],a[(i-1)*L+j]);
    }
    for (int i=1;i<=nn;++i)M[i]=!(i&(i-1))?M[i-1]+1:M[i-1];
    for (int j=1;j<=D;++j)
        for (int i=1;i<=nn-(1<<j)+1;++i)f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for (int i=1;i<=nn+1;++i)c[i].init(a+(i-1)*L);
}
inline int Qmin_ST(int x,int y){
    int z=M[y-x+1];return min(f[x][z],f[y-(1<<z)+1][z]);
}
inline int Qmin(int x,int y){
    int xx=(x-1)/L+1,yy=(y-1)/L+1,res;
    if (xx+1<=yy-1)res=Qmin_ST(xx+1,yy-1);else res=inf;
    if (xx==yy)res=min(res,c[xx].Qmin(x-(xx-1)*L,y-(yy-1)*L));
    else res=min(res,c[xx].Qmin(x-(xx-1)*L,L)),res=min(res,c[yy].Qmin(1,y-(yy-1)*L));
    return res;
}
namespace zzy{
    int f[N/L][D_max],M[N/L],stack[L+1];
    struct node{
        int state[L+1],*a;
        int Qmax(int x,int y){return a[x+__builtin_ctz(state[y]>>x)];}
        void init(int *_a){
            int top=0;a=_a;
            for (int i=1;i<=L;++i){
                state[i]=state[i-1];
                while (top&&a[i]>=a[stack[top]])state[i]-=1<<stack[top],--top;
                stack[++top]=i;state[i]+=1<<i;
            }
        }
    }c[N/L];
    void build(){
        int nn=n/L;M[0]=-1;
        for (int i=1;i<=nn;++i){
            f[i][0]=-inf;for (int j=1;j<=L;++j)f[i][0]=max(f[i][0],a[(i-1)*L+j]);
        }
        for (int i=1;i<=nn;++i)M[i]=!(i&(i-1))?M[i-1]+1:M[i-1];
        for (int j=1;j<=D;++j)
            for (int i=1;i<=nn-(1<<j)+1;++i)f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        for (int i=1;i<=nn+1;++i)c[i].init(a+(i-1)*L);
    }
    int Qmax_ST(int x,int y){
        int z=M[y-x+1];return max(f[x][z],f[y-(1<<z)+1][z]);
    }
    int Qmax(int x,int y){
        int xx=(x-1)/L+1,yy=(y-1)/L+1,res;
        if (xx+1<=yy-1)res=Qmax_ST(xx+1,yy-1);else res=-inf;
        if (xx==yy)res=max(res,c[xx].Qmax(x-(xx-1)*L,y-(yy-1)*L));
        else res=max(res,c[xx].Qmax(x-(xx-1)*L,L)),res=max(res,c[yy].Qmax(1,y-(yy-1)*L));
        return res;
    }
};
using namespace zzy;
const int S=3000005;
char str[S],*p=str;
inline void read(int &x){
    int bo=0;x=0;
    while(*p<'0'||*p>'9')if (*p++=='-')bo=1;
    while(*p>='0'&&*p<='9')x=x*10+*p++-'0';
    if (bo)x=-x;
}
char buf[15],out[S],*o=out;
inline void print(int x){
    char *b=buf;if (!x)*b++='0';//if (x<0)x=-x,*b++='-';
    while(x){*b++=x%10+48;x/=10;}
    while(b--!=buf)*o++=*b;
    *o++='\n';
}
int main(){
    fread(p,1,S,stdin);
    read(n);read(q);D=int(log2(n))+1;
    for (int i=1;i<=n;++i)read(a[i]);
    ::build();zzy::build();
    while (q--){
        int x,y;read(x);read(y);
        print(Qmax(x,y)-Qmin(x,y));
    }
    if (o>out)*--o=0;puts(out);
    return 0;
}

by Spasmodic @ 2020-08-11 13:46:15

@mcyl35

by Spasmodic @ 2020-08-11 13:51:55

@mcyl35

by critnos @ 2020-08-11 13:52:14

在康

by critnos @ 2020-08-11 13:58:59

@happydef 看不懂/kk

似乎是类似分块 ST 的东西

by Spasmodic @ 2020-08-11 14:04:39

@mcyl35

by Spasmodic @ 2020-08-11 14:04:49

@mcyl35 您看得懂这个吗qwq

by critnos @ 2020-08-11 14:17:10

/kk/kk

by critnos @ 2020-09-12 17:44:15

@happydef 这几天才看到 ST 表里的一个题解，https://www.luogu.com.cn/blog/qwaszx/solution-p3865