B_1168 @ 2020-03-27 11:10:46
如题，尝试用分块模板过，但是不知为何开了O2只能拿90，哪怕是用了从ST表模板题题面复制的快读模板也过不了……为什么不用ST表？因为我ST表模板题是靠分块过的……用了O2之后#8 和#10 都能卡在500ms左右，但是#9 就是TLE，请各位dalao们伸出援手，用更多的常数优化卡过这道题，或者让这个*山一样的万年模板能用臭氧冲过去，在此先谢过各位了
以下是极度丑陋的代码
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
//devised from my P3372 Segment Tree I Template: only 50 points is expected this way
//First attempt with O2 gave 90; pumping ozone smashed the results to 0.
long long n,m,len,a[maxn],val_max[maxn],val_min[maxn],be[maxn];
/*
void modify(long long from,long long to,long long ad){
for(long long i=from;i<=min(to,be[from]*len);i++) a[i]+=ad,val[be[from]]+=ad;
if(be[from]!=be[to]){
for(long long i=(be[to]-1)*len+1;i<=to;i++) a[i]+=ad,val[be[to]]+=ad;
}
for(long long i=be[from]+1;i<=be[to]-1;i++) add[i]+=ad;
}
*/
inline int read(){ //This is from the ST chart template but it did NOT work sufficiently
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
long long query_min(long long from,long long to){
long long cnt=9223372036854775805;
for(long long i=from;i<=min(to,be[from]*len);i++) cnt=min(cnt, a[i]);
if(be[from]!=be[to]){
for(long long i=(be[to]-1)*len+1;i<=to;i++) cnt=min(cnt, a[i]);
}
for(long long i=be[from]+1;i<=be[to]-1;i++) cnt=min(cnt, val_min[i]);
return cnt;
}
long long query_max(long long from,long long to){
long long cnt=-9223372036854775805;
for(long long i=from;i<=min(to,be[from]*len);i++) cnt=max(cnt, a[i]);
if(be[from]!=be[to]){
for(long long i=(be[to]-1)*len+1;i<=to;i++) cnt=max(cnt, a[i]);
}
for(long long i=be[from]+1;i<=be[to]-1;i++) cnt=max(cnt, val_max[i]);
return cnt;
}
int main(){
n=read();m=read();
len=sqrt(n);
for(long long i=1;i<=n;i++) be[i]=(i-1)/len+1;
for(long long i=1;i<=n;i++) {
val_min[i]=9223372036854775805;
val_max[i]=-9223372036854775805;
}
for(long long i=1;i<=n;i++){
a[i]=read();
val_min[be[i]]=min(val_min[be[i]],a[i]);
val_max[be[i]]=max(val_max[be[i]],a[i]);
}
for(long long i=1;i<=n-m+1;i++){
printf("%d ",query_min(i,i+m-1));
}
printf("\n");
for(long long i=1;i<=n-m+1;i++){
printf("%d ",query_max(i,i+m-1));
}
}by B_1168 @ 2020-04-16 04:01:31
@暴力出奇迹 @chenxinyang2006
利用了@玉签初报明 神犇的数据体大法和现学的快输后，#9得以用768ms/10.41MB通过！
事实证明，由两次查询改为数据体大约可以节约1/3的时间
以下放代码：
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,m,len,a[maxn],b[maxn],be[maxn],ans=0;
struct node{
int max,min;
}val[maxn];
inline int read(){ //This is from the ST chart template but it did NOT work sufficiently
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline node query (int from,int to){
node cnt;
cnt.min=2147483647,cnt.max=-2147483647;
for (int i=from;i<=min(to,be[from]*len);++i) {
cnt.min=min(cnt.min, a[i]);
cnt.max=max(cnt.max, a[i]);
}
if(be[from]!=be[to]){
for (int i=(be[to]-1)*len+1;i<=to;++i) {
cnt.min=min(cnt.min, a[i]);
cnt.max=max(cnt.max, a[i]);
}
}
for (int i=be[from]+1;i<=be[to]-1;++i) {
cnt.min=min(cnt.min, val[i].min);
cnt.max=max(cnt.max, val[i].max);
}
return cnt;
}
int main(){
n=read();m=read();
len=sqrt(n);
for (int i=1;i<=n;++i) be[i]=(i-1)/len+1;
for (int i=1;i<=len+1;++i) {
val[i].min=2147483647;
val[i].max=-2147483647;
}
for (int i=1;i<=n;++i){
a[i]=read();
val[be[i]].min=min(val[be[i]].min,a[i]);
val[be[i]].max=max(val[be[i]].max,a[i]);
}
for(int i=1;i<=n-m+1;++i){
node temp=query(i,i+m-1);
write(temp.min);
putchar(' ');
b[i]=temp.max;
}
putchar('\n');
for(int i=1;i<=n-m+1;++i){
write(b[i]);
putchar(' ');
}
}