# [BZOJ1699]&&[Usaco2007 Jan]Balanced Lineup 排队

6 3
1
7
3
4
2
5
1 5
4 6
2 2

6
3
0

Gold

BZOJ 1699

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ls(x) x<<1
#define rs(x) (x<<1)+1
const int inf=0x7fffffff;
struct tnode
{
int l,r,maxs,mins;
}tree[200005];
int a[50005];
int i,j,t,n,m,q,k,z,y,x,amax,amin;
{
int x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
void build(int s,int tl,int tr)
{
int i,j,t,mid;
tree[s].l=tl;tree[s].r=tr;
if (tl==tr)
{
tree[s].maxs=tree[s].mins=a[tl];
return ;
}
mid=(tl+tr)>>1;
build(ls(s),tl,mid);build(rs(s),mid+1,tr);
tree[s].maxs=max(tree[ls(s)].maxs,tree[rs(s)].maxs);
tree[s].mins=min(tree[ls(s)].mins,tree[rs(s)].mins);
}
void find(int s,int tl,int tr)
{
int i,j,t,mid;
if (tree[s].l>=tl && tree[s].r<=tr)
{
amax=max(amax,tree[s].maxs);
amin=min(amin,tree[s].mins);
return ;
}
mid=(tree[s].l+tree[s].r)>>1;
if (tr<=mid) find(ls(s),tl,tr);
else if (tl>mid) find(rs(s),tl,tr);
else
{
find(ls(s),tl,mid);
find(rs(s),mid+1,tr);
}
}
int main()
{