JRzyh @ 2020-11-29 12:10:14
刚学分块，求助
#\
p\
r\
a\
g\
m\
a\
\
G\
C\
C\
\
t\
a\
r\
g\
e\
t\
(\
"\
a\
v\
x\
,\
s\
s\
e\
2\
,\
s\
s\
e\
3\
,\
s\
s\
e\
4\
,\
m\
m\
x\
"\
)
#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);
}
}
using namespace GenHelper;
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
inline int read()
{
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
unsigned long long out;
int size,num,n,m,s,a[20000008],block[4480],l[4480],r[4480],belong[20000008],be[4480][4480],la[4480][4480],st[4480][15];
inline int query(int l,int r)
{
if(r<l)return -114514;
int k=log2(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
srand(s);
for(register int i=1;i<=n;i++)
{
a[i]=read();
}
size=sqrt(n);
num=n/size+(n%size!=0);
l[1]=1;
r[1]=size;
for(register int i=2;i<=num;i++)
{
l[i]=r[i-1]+1;
r[i]=min(l[i]+size-1,n);
}
for(register int i=1;i<=num;i++)
{
for(register int j=l[i];j<=r[i];j++)
{
block[i]=max(block[i],a[j]);
belong[j]=i;
}
for(register int j=l[i];j<=r[i];j++)
{
be[i][j-l[i]+1]=max(be[i][j-l[i]],a[j]);
}
for(register int j=r[i];j>=l[i];j--)
{
la[i][r[i]-j+1]=max(la[i][r[i]-j],a[j]);
}
}
for(register int i=1;i<=num;i++)
{
st[i][0]=block[i];
}
for(register int j=1;j<=log2(num);j++)
{
for(register int i=1;i+(1<<j)-1<=num;i++)
{
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
while(m--)
{
int x=read()%n+1,y=read()%n+1,l1=min(x,y),r1=max(x,y),ans=0;
if(belong[l1]==belong[r1])
{
for(int i=l1;i<=r1;i++)
{
ans=max(a[i],ans);
}
out+=ans;
continue;
}
ans=max(ans,la[belong[l1]][r[belong[l1]]-l1+1]);
ans=max(ans,be[belong[r1]][r1-l[belong[r1]]+1]);
ans=max(ans,query(belong[l1]+1,belong[r1]-1));
out+=ans;
}
printf("%llu",out);
return 0;
}by critnos @ 2020-11-29 12:20:05
其实这个每一块的前缀后缀最大可以用一个一维数组存的
by critnos @ 2020-11-29 12:26:39
be[i] 表示从 l[belong[i]]~i 的最大值，la 同理
应该会快一些，你的预处理和我的速度是没什么区别的，下面 st 表的查询也不慢，是每一块的前缀后缀最大的问题吧
by JRzyh @ 2020-11-29 12:34:00
@mcyl35 thx
by Yuanchenpu @ 2020-11-29 12:45:18
#\
p\
r\
a\
g\
m\
a\
\
G\
C\
C\
\
t\
a\
r\
g\
e\
t\
(\
"\
a\
v\
x\
,\
s\
s\
e\
2\
,\
s\
s\
e\
3\
,\
s\
s\
e\
4\
,\
m\
m\
x\
"\
)
#include<bits/stdc++.h>
using namespace std;
namespace IO {
const int SIZE = (1 << 20) + 1;
char ibuf[SIZE], *iS, *iT;
inline char gc() {
return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++) : *iS++);
}
inline void qread() {}
template<class T1, class ...T2>
inline void qread(T1 &IEE, T2 &... ls) {
register T1 __ = 0, ___ = 1;
register char ch;
while (!isdigit(ch = gc())) ___ = (ch == '-') ? -___ : ___;
do {
__ = (__ << 1) + (__ << 3) + (ch ^ 48);
} while (isdigit(ch = gc()));
__ *= ___;
IEE = __;
qread(ls...);
return;
}
}
using namespace IO;
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);
}
}
using namespace GenHelper;
void srand(unsigned x)
{z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
static int a, b;
a=rand_()&32767;
b=rand_()&32767;
return a << 15 | b;
}
int max(int a,int b){return (a<b)?b:a;}
int min(int a,int b){return (a<b)?a:b;}
unsigned long long out;
int size,num,n,m,s,a[20000008],block[4480],l[4480],r[4480],belong[20000008],be[20000008],la[20000008],st[4480][15];
inline int query(int l,int r)
{
if(r<l)return -114514;
int k=log2(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
qread(n,m,s);
srand(s);
for(register int i=1;i<=n;i++)
{
a[i]=read();
}
size=sqrt(n);
num=n/size+(n%size!=0);
l[1]=1;
r[1]=size;
for(register int i=2;i<=num;i++)
{
l[i]=r[i-1]+1;
r[i]=min(l[i]+size-1,n);
}
for(register int i=1;i<=num;i++)
{
for(register int j=l[i];j<=r[i];j++)
{
block[i]=max(block[i],a[j]);
belong[j]=i;
}
be[l[i]]=a[l[i]];
for(register int j=l[i]+1;j<=r[i];j++)
{
be[j]=max(be[j-1],a[j]);
}
la[r[i]]=a[r[i]];
for(register int j=r[i];j>=l[i];j--)
{
la[j]=max(la[j+1],a[j]);
}
}
for(register int i=1;i<=num;i++)
{
st[i][0]=block[i];
}
for(register int j=1;j<=log2(num);j++)
{
for(register int i=1;i+(1<<j)-1<=num;i++)
{
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
while(m--)
{
int x=read()%n+1,y=read()%n+1,l1=min(x,y),r1=max(x,y),ans=0;
if(belong[l1]==belong[r1])
{
for(int i=l1;i<=r1;i++)
{
ans=max(a[i],ans);
}
out+=ans;
continue;
}
ans=max(ans,la[l1]);
ans=max(ans,be[r1]);
ans=max(ans,query(belong[l1]+1,belong[r1]-1));
out+=ans;
}
printf("%llu",out);
return 0;
}@Zhaoyuhang2008 卡过了
by JRzyh @ 2020-11-29 12:48:22
@Yuanchenpu thx!