Fraction @ 2018-09-16 15:49:48
RT,无比正常的线段树,难道是线段树常数
贴代码:
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define fp(i, l, r) for(register int i = (l); i <= (r); ++i)
#define fd(i, l, r) for(register int i = (l); i >= (r); --i)
#define ll long long
#define il inline
using namespace std;
template <typename T> il void read(T &dig) {
bool flag = false;
char c = getchar();
dig = 0;
while(!isdigit(c) && c != '-') c = getchar();
if(c == '-') flag = true, c = getchar();
while(isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if(flag) dig = -dig;
}
const int inf = INT_MAX;
const int MAXN = (int)4e6 + 5;
int n, k;
int num[MAXN];
class Segment {
#define MTH 1
public:
Segment() {return ;}
~Segment() {return ;}
#undef MTH
#define YHB 2
protected:
int maxn[MAXN], minn[MAXN];
#undef YHB
#define HKH 3
public:
il int ls(int node) {return node << 1;}
il int rs(int node) {return node << 1 | 1;}
il void build(int node, int l, int r) {
if(l == r) {
maxn[node] = num[l];
minn[node] = num[l];
return ;
} else {
int mid = (l + r) >> 1;
build(ls(node), l, mid);
build(rs(node), mid+1, r);
maxn[node] = max(maxn[ls(node)], maxn[rs(node)]);
minn[node] = min(minn[ls(node)], minn[rs(node)]);
}
}
il int query_max(int node, int wantl, int wantr, int nowl, int nowr) {
int ret = -inf;
if(wantl <= nowl && nowr <= wantr) {
return maxn[node];
} else {
int mid = (nowl + nowr) >> 1;
if(wantl <= mid) ret = max(ret, query_max(ls(node), wantl, wantr, nowl, mid));
if(wantr > mid) ret = max(ret, query_max(rs(node), wantl, wantr, mid+1, nowr));
}
return ret;
}
il int query_min(int node, int wantl, int wantr, int nowl, int nowr) {
int ret = inf;
if(wantl <= nowl && nowr <= wantr) {
return minn[node];
} else {
int mid = (nowl + nowr) >> 1;
if(wantl <= mid) ret = min(ret, query_min(ls(node), wantl, wantr, nowl, mid));
if(wantr > mid) ret = min(ret, query_min(rs(node), wantl, wantr, mid+1, nowr));
}
return ret;
}
#undef HKH
};
Segment t;
il void init() {
read(n), read(k);
fp(i, 1, n) read(num[i]);
t.build(1, 1, n);
}
il void solve() {
fp(i, 1, n-k+1) printf("%d ", t.query_min(1, i, i+k-1, 1, n));
printf("\n");
fp(i, 1, n-k+1) printf("%d ", t.query_max(1, i, i+k-1, 1, n));
}
int main() {
init();
solve();
return 0;
}
by The_Chaos @ 2018-09-16 15:58:13
@Fraciton 请使用单调队列。
这和在线段树模板题里打分块一样不合时宜。被卡很正常。
by 一扶苏一 @ 2018-09-16 15:58:31
@Fraciton 线段树是
by Fraction @ 2018-09-16 16:01:21
@一扶苏一 不是能过吗
by Nero_Claudius @ 2018-09-16 16:09:53
@hsfzLZH_ 分块大法好虽然我打的zkw
by Nero_Claudius @ 2018-09-16 16:10:32
@hsfzLZH_ 话说。。。这不是线段树板子题吗?当年老师教线段树的时候就打了这道题
by 一扶苏一 @ 2018-09-16 16:39:25
@Fraciton 线段树这么大的常数1e6一般都跑不过去的吧……
by Burnside @ 2018-10-24 13:01:27
@一扶苏一 捕捉神仙 我刚打完线段树
by 一扶苏一 @ 2018-10-24 14:16:27
@Burnside 您抓到了一只蒟蒻qwq
by Burnside @ 2018-10-24 14:36:23
@一扶苏一 神仙呐qwq
我线段树a了qwq
by 一扶苏一 @ 2018-10-24 18:20:14
@Burnside 所以您神仙呐orz