网站页面设计需要遵循的六大原则,网站建设公司制作网站,信誉好的新乡网站建设,大连网站建设开源正题
题目链接:https://www.luogu.com.cn/problem/P3793 题目大意
给出nnn个数字的一个序列mmm次询问区间最大值
保证数据随机 1≤n,m≤21071\leq n,m\leq 2\times 10^71≤n,m≤2107 解题思路
使用STSTST表可以做到O(1)O(1)O(1)询问#xff0c;但是预处理的时空复杂度都是…正题
题目链接:https://www.luogu.com.cn/problem/P3793 题目大意
给出nnn个数字的一个序列mmm次询问区间最大值
保证数据随机
1≤n,m≤2×1071\leq n,m\leq 2\times 10^71≤n,m≤2×107 解题思路
使用STSTST表可以做到O(1)O(1)O(1)询问但是预处理的时空复杂度都是O(nlogn)O(n\log n)O(nlogn)且自带大常数导致过不了。
如何加快预处理的时间因为是lxl的题目所以考虑使用分块。每次询问可以分为整块的部分和不是整块的零散部分。
去掉没有跨块的情况那么零散的部分就是块内前后缀最大值。然后整块的部分用STSTST表就好了。
那么没有跨块的情况是不是还需要给每个块维护一个STSTST表这样空间还是过不了其实可以考虑将没有跨块的情况按顺序每个块每个块离线处理这样就可以过了。
但是数据保证随机所以随机到同一个块内的概率是1T\frac{1}{T}T1也就是期望n\sqrt nn次暴力处理是O(n)O(\sqrt n)O(n)的所以直接暴力处理就可以了
时间复杂度O(nlognm)O(n\log\sqrt nm)O(nlognm)。 code
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N2e710;
namespace GenHelper{unsigned z1,z2,z3,z4,b;unsigned rand_(){b((z16)^z1)13;z1((z14294967294U)18)^b;b((z22)^z2)27;z2((z24294967288U)2)^b;b((z313)^z3)21;z3((z34294967280U)7)^b;b((z43)^z4)12;z4((z44294967168U)13)^b;return (z1^z2^z3^z4);}
}
void srand(unsigned x)
{using namespace GenHelper;
z1x; z2(~x)^0x233333333U; z3x^0x1234598766U; z4(~x)51;}
int read()
{using namespace GenHelper;int arand_()32767;int brand_()32767;return a*32768b;
}
int n,m,a[N],lg[N],p[N],q[N],g[5000][13];
int L[5000],R[5000],pos[N];
unsigned s;
unsigned long long ans;
int AskT(int l,int r){if(lr)return 0;int zlg[r-l1];return max(g[l][z],g[r-(1z)1][z]);
}
int main()
{scanf(%d%d%u,n,m,s);srand(s);for(int i1;in;i)a[i]read();int Tsqrt(n);for(int i1;iT;i)L[i]R[i-1]1,R[i]i*T;if(R[T]!n)T,L[T]R[T-1]1,R[T]n;for(int i1;iT;i){for(int jL[i];jR[i];j)pos[j]i,g[i][0]max(g[i][0],a[j]);p[L[i]]a[L[i]];q[R[i]]a[R[i]];for(int jL[i]1;jR[i];j)p[j]max(p[j-1],a[j]);for(int jR[i]-1;jL[i];j--)q[j]max(q[j1],a[j]);}for(int j1;(1j)T;j)for(int i1;i(1j)-1T;i)g[i][j]max(g[i][j-1],g[i(1j-1)][j-1]);for(int i2;iT;i)lg[i]lg[i1]1;for(int i1;im;i){int lread(),rread();ll%n1;rr%n1;if(lr)swap(l,r);int xpos[l],ypos[r];int tmp0;if(xy){for(int il;ir;i)tmpmax(tmp,a[i]);}else{tmpAskT(x1,y-1);tmpmax(tmp,max(q[l],p[r]));}anstmp;}printf(%llu\n,ans);
}
