两RE求助

link

log块长分块+块间ST表+快内前后缀最小值，同块则暴力查询

#include <bits/stdc++.h>
using namespace std;
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;
}
inline int read() {
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return (a<<15)|b;
}
const int maxn=2e7+5;
const int LOG=log2(maxn)+1;
const int bl=maxn/LOG+5;//有几个块
int a[maxn];//原数组
int val[bl],st[bl],ed[bl],id[maxn];
//val是块内最小，st，ed是块的左右端点，id[i]是i属于哪一块
int pre[bl][LOG],lst[bl][LOG];
//前后缀最小值
inline int MAX(int a,int b) {
    return a>b?a:b;
}
int s[bl][LOG];//块间ST表
int LG[maxn];//LG[i]表示log2(i)
inline int query(int l,int r) {
    int sb=id[l];
    int eb=id[r];
    int res=a[l];
    if(sb==eb) {
        for(int i=l; i<=r; ++i) res=MAX(res,a[i]);
        return res;
        //块内暴力查
    }
    res=MAX(pre[eb][r-st[eb]],lst[sb][l-st[sb]]);
    l=sb+1;
    r=eb-1;
    if(l>r) return res;//两块相邻，不查询ST表
    int k=LG[r-l+1];
    return MAX(res,MAX(s[l][k],s[r-(1<<k)+1][k]));
}
int l,r;
int size,len;//size是块长，len是块数
int n,m,sra;
unsigned long long ans;
signed main() {
    for(int i=2; i<maxn; ++i) LG[i]=LG[i>>1]+1;

    cin>>n>>m>>sra;
    size=log2(n);
    len=n/size;
    srand(sra);

    for(int i=1; i<=n; ++i) a[i]=read();

    //预处理
    for(int i=1; i<=len; ++i) st[i]=ed[i-1]+1,ed[i]=st[i]+size-1;
    if(ed[len]<n) st[len+1]=ed[len]+1,ed[++len]=n;
    for(int i=1; i<=len; ++i) {
        for(int j=st[i]; j<=ed[i]; ++j)
            pre[i][j-st[i]]=MAX(pre[i][j-st[i]-1],a[j]),
            id[j]=i,
            val[i]=MAX(val[i],a[j]);
        for(int j=ed[i]; j>=st[i]; --j)
            lst[i][j-st[i]]=MAX(lst[i][j-st[i]+1],a[j]);
        s[i][0]=val[i];
    }
    //ST表
    for(int j=1; j<LOG; ++j)
        for(int i=1; i+(1<<j)<=len; ++i) {
            s[i][j]=MAX(s[i][j-1],s[i+(1<<(j-1))][j-1]);
        }
    while(m--) {
        l=read()%n+1,r=read()%n+1;
        if(l<=r) ans+=query(l,r);
        else ans+=query(r,l);
    }
    cout<<ans;
    return 0;
}