每日一题 day28 打卡
Analysis
这道题用线段树维护区间最小值很简单，因为没有修改所以连lazy_tag都不用，但是这道题可以用树状数组维护区间最小值，非常骚气。
线段树代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long
#define maxn 1000000+10
using namespace std;
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
inline void write(int x)
{
if(x<){putchar('-');x=-x;}
if(x>)write(x/);
putchar(x%+'');
}
int m,n;
int a[maxn];
struct Segment_tree
{
struct Segment_tree_node
{
int l,r,val;
}node[maxn*];
int n;
inline int size() {return n;}
inline int left_s(int x) {return (x<<);}
inline int right_s(int x) {return ((x<<)|);}
inline void init(int l,int r)
{
n=r-l+;
node[].l=;
node[].r=n;
build();
}
inline void push_up(int x)
{
node[x].val=min(node[left_s(x)].val,node[right_s(x)].val);
}
inline void build(int x)
{
if(node[x].l==node[x].r)
{
node[x].val=a[node[x].l];
return;
}
int mid=(node[x].l+node[x].r)>>;
node[left_s(x)].l=node[x].l;
node[left_s(x)].r=mid;
build(left_s(x));
node[right_s(x)].l=mid+;
node[right_s(x)].r=node[x].r;
build(right_s(x));
push_up(x);
}
inline int query(int x,int l,int r)
{
if(node[x].l==l&&node[x].r==r)
{
return node[x].val;
}
int mid=(node[x].l+node[x].r)>>;
if(r<=mid) return query(left_s(x),l,r);
if(l>mid) return query(right_s(x),l,r);
return min(query(left_s(x),l,mid),query(right_s(x),mid+,r));
}
}t;
signed main()
{
m=read();n=read();
for(int i=;i<=m;i++) a[i]=read();
t.init(,m);
for(int i=;i<=n;i++)
{
int x=read(),y=read();
int ans=t.query(,x,y);
write(ans);
printf(" ");
}
return ;
}
树状数组代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long
#define maxn 1000000+10
#define INF 2147483647
using namespace std;
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
inline void write(int x)
{
if(x<){putchar('-');x=-x;}
if(x>)write(x/);
putchar(x%+'');
}
int m,n;
int a[maxn];
int tree[maxn];
inline int lowbit(int num)
{
return num&(-num);
}
inline void update(int s,int num)
{
int i=s;
while(i<=m)
{
if(tree[i]>num)
tree[i]=num;
else return;
i+=lowbit(i);
}
}
inline int query(int l,int r)
{
int res=INF,i=r;
while(i>=l)
{
if(i-lowbit(i)>l)
{
res=min(res,tree[i]);
i-=lowbit(i);
}
else
{
res=min(res,a[i]);
--i;
}
}
return res;
}
signed main()
{
memset(tree,,sizeof(tree));
m=read();n=read();
for(int i=;i<=m;i++)
{
a[i]=read();
update(i,a[i]);
}
for(int i=;i<=n;i++)
{
int x=read(),y=read();
int ans=query(x,y);
write(ans);
printf(" ");
}
return ;
}
请各位大佬斧正（反正我不认识斧正是什么意思）