数据结构分块+ST表 P3793题解

Prean · 2020-03-26 19:48:44 · 题解

警告！卡常警告！！！

极度卡常的一道题。就是数据范围极大的RMQ，数据随机，~~出题人太懒了让我们自己造数据~~

首先st表和线段树肯定都过不去， nlogn 的时间在 n=2e7 的情况下虽然不会TLE（假如常数大了还是会TLE的），但是空间肯定爆了，于是尝试优化。

用什么优化呢？线段树？不行，空间大，时间大，常数还大。平衡树？似乎没问题，但是常数大了就会TLE。那怎么办呢？要把阶级降低才行。说到这个的话，一定能够想到这个东西：

分块

没错是的。

分成 \sqrt n 个块，每一个块的大小是 \sqrt n 。那么我们可以在块上RMQ，预处理的时间是 O( \sqrt nlog \sqrt n) 。

因为C++自带的 log 函数太慢，我们可以自己初始化：

int log[20000005]={-1};
for(register int i=1;i<=n;++i)
{
    log[i]=log[i>>1]+1;
}

这样初始化对于LCA的倍增算法也有效。不过要注意的是如果是LCA的话log数组不用初始化。

然后就是分类讨论。

1. L和R在一个块内。

很简单，直接暴力就行了。

What？你不怕超时吗？

真的不怕。因为数据随机，所以L和R在同一个块内的概率是 \frac 1 n ，所以时间也不会大到哪儿去。就算是 \frac {1} {\sqrt n} 吧，时间也是 \sqrt n \times \sqrt n，不会超时。

2. 不在同一个块内并且所在块不相邻

不多说，就是直接ST表。但是L和R不一定是各自所在的块的分界线。怎么办呢？我们可以记一个前缀最大和后缀最大，这样算法就不会退化成 O( n^{ \frac 3 2 } ) 了。

3. 不在同一个块内并且所在块相邻

这样的话ST表就失效了，因为要查询的区间里面没有在ST表内的元素。这个时候我们只要找到L所在块的后缀最大和R所在块的前缀最大，取两个最大的就行了。

这样就搞定辣！

不过本题极度卡常，贴上自己被卡常的代码：

#include<iostream>
const int M=2e7+5;unsigned long long ans;
int st[4505][15],mL[M],mR[M],a[M];
int n,m,s,t,p=4480,l[4505],x[4505],y[4505],bl[M];
inline int max(int a,int b){return a>b?a:b;}
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
inline void ask(int L,int R)
{
    if(L>R)std::swap(L,R);int res=0;
    if(bl[L]==bl[R])
    {
        for(int i=L;i<=R;++i)res=max(res,a[i]);
        ans+=res;return;
    }if(bl[R]-bl[L]==1){ans+=max(mR[L],mL[R]);return;}
    int k=l[bl[R]-bl[L]-1];
    res=max(st[bl[L]+1][k],st[bl[R]-(1<<k)][k]);
    res=max(res,max(mR[L],mL[R]));ans+=res;
}
signed main()
{
    int i,j;std::cin>>n>>m>>s;srand(s);
    for(i=1;i<=n;++i)
    {
        a[i]=read();bl[i]=i/p+1;
        st[bl[i]][0]=max(st[bl[i]][0],a[i]);
    }t=bl[n];l[0]=-1;
    for(i=1;i<=t;++i)
    {
        l[i]=l[i-1]+((1<<l[i-1]+1)==i);
        x[i]=(i-1)*p;y[i]=x[i]+p-1;
    }x[1]=1;y[t]=n;
    for(i=1;i<=n;++i)mL[i]=max(a[i],i^x[bl[i]]?mL[i-1]:0);
    for(i=n;i>=1;--i)mR[i]=max(a[i],i^y[bl[i]]?mR[i+1]:0);
    for(j=1;(1<<j)<=t;++j)for(i=1;i+(1<<j)-1<=t;++i)
    st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
    for(;m;--m)ask(read()%n+1,read()%n+1);std::cout<<ans;
}

数据结构 分块+ST表 P3793题解