线段树优化做法
如果仔细读过题的话，就会发现这是一个静态的区间查询最大值与最小值。
很多人（如果你学过线段树的话）就会想到，我当年学线段树的例题不就是区间加，然后求区间最大值吗？何况还没有区间加这一操作，岂不嗨皮哉？？？
好的，看看数据范围。
1*10^6？？？
线段树能过的去吗？还需要维护两个值，不得两棵线段树吗？？？
这个问题就不难解决了：
首先是时间的问题。我们的常识告诉我们，O(nlogn)只能走100000，但是如果你的常数不是很大的话，单从线段树的时间复杂度上说，nlog₂n在n=1000000的话是1000000*20=20000000，加点常数还是可以过的。
接下来解决很多人总要写两棵线段树的问题。由上文知，20000000要求你的常数很小，而你如果写两棵线段树会增大你的常数，而且写起来费事，所以不如只写一棵线段树。
怎么写呢？？？
在此之前先了解一下我的宏定义QAQ，方便理解以下代码
#define root 1,n,1 //根节点的左右边界与节点编号 #define lson l,m,rt<<1 //左儿子的左右边界与节点编号 #define rson m+1,r,rt<<1|1 //右儿子的左右边界与节点编号
我们不妨写一个结构体
struct node{
int maxx,minn;//最大值与最小值
}t, z[mn<<2];//t是用来接query函数（一会再讲）的返回值的
//z[]是用来存线段树主体的。 直接一起存，是不是省了两棵线段树的麻烦？
那么怎么更新呢？分别更新呗：
inline void update(int rt){//rt表示要更新的线段树节点
z[rt].maxx=max(z[rt<<1].maxx,z[rt<<1|1].maxx);
z[rt].minn=min(z[rt<<1].minn,z[rt<<1|1].minn);
} 这样就可以更新当前节点啦！
我们的基础数值可以和建树操作一起进行。
inline void build(intl,int r,int rt){//建树
if(l==r){z[rt].minn=z[rt].maxx=read();}//这里一起进行（我用了个读入优化）
int m=(l+r)>>1;
build(lson);//左儿子
build(rson);//右儿子
update(rt);
} 因为我们没有区间值的变化，所以就不写modify这部分了。接下来是一个查询的过程，这里有个细节，你要同时返回最小值与最大值，不能把左边和右边的一组答案直接作为这一个区间的答案，所以你只能把左右两边同时比较最大值最小值，最大值取两者中最大值最大，最小值取两者中最小值最小，然后合并成一个node结构体。
所以，为了简化这一步骤，可以多写一个函数：
inline node cmp(node a,node b){//函数名字就不要深究了
return (node){a.maxx > b.maxx ? a.maxx : b.maxx, a.minn < b.minn ? a.minn : b.minn};
} 然后用在查询（query）函数中：
这里有个小小的优化：
如果你的判断是只有两个的话，这样会多次进入循环，所以可以直接从判断上省去一部分时间。
inline node query(int l,int r,int rt,int nowl,int nowr){
//变量分别是线段树左右端点，线段树节点编号，查询范围左右端点
if(nowl<=l && r<=nowr){return z[rt];}
int m=(l+r)>>1;
if(nowl<=m){
if(m<nowr)
return cmp(query(lson,nowl,nowr),query(rson,nowl,nowr));//直接递归
else
return query(lson,nowl,nowr);
}else{
return query(rson,nowl,nowr);
}
} 这样返回的就是区间的最大值和最小值了
主函数的部分直接在完整代码中详细讲解了
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 1000100
#define inf 1 << 30
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';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');
}
//This is AC head above...
struct node{
int maxx, minn;
} t,z[mn<<2];
inline node cmp(node a,node b){
return (node){a.maxx > b.maxx ? a.maxx : b.maxx, a.minn < b.minn ? a.minn : b.minn};
}
inline void update(int rt){
z[rt].maxx = max(z[rt << 1].maxx, z[rt << 1 | 1].maxx);
z[rt].minn = min(z[rt << 1].minn, z[rt << 1 | 1].minn);
}
inline void build(int l,int r,int rt){
if(l==r){
z[rt].maxx = z[rt].minn = read();
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
inline node query(int l,int r,int rt,int nowl,int nowr){
if(nowl<=l && r<=nowr){
return z[rt];
}
int m = (l + r) >> 1;
if(nowl<=m){
if(m<nowr)
return cmp(query(lson, nowl, nowr), query(rson, nowl, nowr));
else
return query(lson, nowl, nowr);
}else{
return query(rson, nowl, nowr);
}
}
int n, k;
int a[mn];
int main(){
n = read(), k = read();//读入
build(root);//建树（并且直接读入叶节点数值）
go(i,1,n-k+1,1){//这里的循环用来求区间最大值最小值，顺便输出最小值
node ooo = query(root, i, i + k - 1);//k是区间的固定长度，所以直接按长度与循环到的左端点询问
printf("%d ", ooo.minn);//输出最小值（不敢用cin了QAQ）
a[i] = ooo.maxx;//存储最大值
}
putchar('\n');
go(i,1,n-k+1,1){
printf("%d ", a[i]);//输出最大值（不敢用cin了）
}
return 0;
} 
京公网安备 11010502036488号