洛谷 P816 忠诚 题解

每日一题 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 ;

 }

请各位大佬斧正