本文共 2418 字，大约阅读时间需要 8 分钟。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;//typedef long long LL;//typedef __int64 LL; //typedef long double DB; //typedef unisigned __int64 LL; //typedef unsigned long long ULL;#define EPS 1e-8#define MAXN 500050#define INF 0x3f3f3f3f#define PI acos(-1.0)//#define MOD 99991//#define MOD 99990001 //#define MOD 1000000007#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define max3(a,b,c) (max(max(a,b),c))#define min3(a,b,c) (min(min(a,b),c))#define xabs(a) ((a<0)?(-a):a)#define L(t) (t << 1) //Left son t*2#define R(t) (t << 1 | 1) //Right son t*2+1#define Mid(a,b) ((a+b)>>1) //Get Mid#define lowbit(a) (a&-a) //Get Lowbitint gcd(int a,int b){return b?gcd(b,a%b):a;}int lcm(int a,int b){return a*b/gcd(a,b);}struct node{ int l,r,maxval,minval;} tree[52005*4];void build(int l,int r,int root){ tree[root].l = l; tree[root].r = r; tree[root].maxval = 0; tree[root].minval = INF; if(l == r) return; int m = Mid(l,r); build(l,m,L(root)); build(m+1,r,R(root));}void modify(int l,int r,int root,int val){ tree[root].maxval=max(val,tree[root].maxval); tree[root].minval=min(val,tree[root].minval); if(tree[root].l == l && tree[root].r == r) { return; } int m=Mid(tree[root].l,tree[root].r); if(r <= m) modify(l,r,L(root),val); else if(l > m) modify(l,r,R(root),val); else { modify(l,m,L(root),val); modify(m+1,r,R(root),val); }}int query(int l,int r,int root){ if(tree[root].l == l && tree[root].r == r) { return tree[root].maxval; } int m=Mid(tree[root].l,tree[root].r); if(r <= m) return query(l,r,L(root)); else if(l > m) return query(l,r,R(root)); else { return max(query(l,m,L(root)),query(m+1,r,R(root))); }}int query1(int l,int r,int root){ if(tree[root].l == l && tree[root].r == r) { return tree[root].minval; } int m=Mid(tree[root].l,tree[root].r); if(r <= m) return query1(l,r,L(root)); else if(l > m) return query1(l,r,R(root)); else { return min(query1(l,m,L(root)),query1(m+1,r,R(root))); }}int main(){// freopen("in.txt","r",stdin);// freopen("out.txt,"w",stdout); int i,n,m,x,y; scanf("%d%d",&n,&m); build(0,52000,1); for(i=1;i<=n;i++) { scanf("%d",&x); modify(i,i,1,x); } for(i=0;i
线段树乱搞,就求一个区间最大最小值,每次插入维护区间就行了
转载地址：http://auhal.baihongyu.com/