这里又被卡常,朴素线段树就是慢了,所以打了zkw线段树,然后$RE$两个点,好像是开区间问题,索性放弃zkw线段树,开始毒瘤优化,加个读入输出优化和开$-o2$还是跑过去了。
朴素版:
#include<cstdio>
const int MAXN = 2000000 + 6;
const int INT_MAX = 0x7fffffff;
inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int min(int a,int b){return a < b ? a : b;}
inline int max(int a,int b){return a > b ? a : b;}
int read(){
int op = 1,ans = 0;char s = getchar();
while(s < '0' || s > '9'){if(s == '-'){op = -1;}s = getchar();}
while(s >='0' && s <='9'){ans = ans * 10 + s - '0';s = getchar();}
ans *= op;
return ans;
}
void print(int x){
if(x < 0){putchar('-');x = -x;}
if(x > 9){print(x / 10);}
putchar(x % 10 + '0');
}
void println(int x){
print(x);
putchar('\n');
}
class SegmentTree{
public:int l,r;
public:int min;
};
SegmentTree t[MAXN * 4];
inline int MID(int l,int r){return (l + r) >> 1;}
void build(int p,int l,int r){
t[p].l = l;t[p].r = r;
if(l == r){
t[p].min = read();
return;
}
build(LEFT(p),l,MID(l,r));
build(RIGHT(p),MID(l,r) + 1,r);
t[p].min = min(t[LEFT(p)].min,t[RIGHT(p)].min);
}
int ask(int p,int l,int r){
if(l <= t[p].l && r >= t[p].r){
return t[p].min;
}
int ans = INT_MAX;
if(l <= MID(t[p].l,t[p].r)){
ans = min(ans,ask(LEFT(p),l,r));
}
if(r > MID(t[p].l,t[p].r)){
ans = min(ans,ask(RIGHT(p),l,r));
}
return ans;
}
int main(){
int n = read(),m = read();
build(1,1,n);
println(0);
for(int i = 1;i < n;i++){
if(i - m <= 0){
println(ask(1,1,i));
}else{
println(ask(1,i - m + 1,i));
}
}
return 0;
}
zkw线段树,它常数太小了,都不用开快读:
#include<cstdio>
const int MAXN = 2000000 + 6;
const int INT_MAX = 0x7fffffff;
class zkwSegmentTree{
public:int min;
};
typedef zkwSegmentTree zkw;
zkw t[MAXN * 2];
inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int min(int a,int b){return a < b ? a : b;}
inline int max(int a,int b){return a > b ? a : b;}
int n,M,m;
void build(){
for(M = 1;M < (n + 2);M <<= 1);
for(int i = M + 1;i <= M + n;i++){
int gg;
scanf("%d",&gg);
t[i].min = gg;
}
for(int i = M - 1;i;i--){
t[i].min = min(t[LEFT(i)].min,t[RIGHT(i)].min);
}
}
int ask(int l,int r){
int ans = INT_MAX;
for(l += M - 1,r += M + 1;l ^ r ^ 1;l >>= 1,r >>= 1){
if(~l & 1){
ans = min(ans,t[l ^ 1].min);
}
if(r & 1){
ans = min(ans,t[r ^ 1].min);
}
}
return ans;
}
int main(){
scanf("%d %d",&n,&m);
build();
printf("0\n");
for(int i = 1;i < n;i++){
if(i - m <= 0){
printf("%d\n",ask(1,i));
}else{
printf("%d\n",ask(i - m + 1,i));
}
}
return 0;
}