华师一附中OI组

标题: P1816 忠诚 [打印本页]

---

作者: admin    时间: 2018-4-21 17:59
标题: P1816 忠诚
https://www.luogu.org/problem/P1816

题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。

输入输出格式
输入格式：
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。

第二行为m个数,分别是账目的钱数

后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。

输出格式：
输出文件中为每个问题的答案。具体查看样例。

输入输出样例
输入样例#1：
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10
输出样例#1：
2 3 1

---

作者: 吴语林    时间: 2018-7-29 23:58

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int a[100020],minn[400040],m,n,x,y,t;
    
14. void biuld_xian(int l,int r,int o)
    
15. {
    
16.         if(l==r)
    
17.         {
    
18.                 minn[o]=a[l];
    
19.                 return;
    
20.         }
    
21.         int mid=(l+r)>>1;
    
22.         biuld_xian(l,mid,o*2);
    
23.         biuld_xian(mid+1,r,o*2+1);
    
24.         minn[o]=min(minn[o*2],minn[o*2+1]);
    
25. }
    
26. int query(int L,int R,int l,int r,int o)
    
27. {
    
28.         if(L<=l&&r<=R) return minn[o];
    
29.         int mid=(l+r)>>1;
    
30.         int a1=0x3f3f3f3f,a2=0x3f3f3f3f;
    
31.         if(L<=mid) a1=query(L,R,l,mid,o*2);
    
32.         if(R>mid) a2=query(L,R,mid+1,r,o*2+1);
    
33.         return min(a1,a2);
    
34. }
    
35. int main()
    
36. {
    
37.         scanf("%d%d",&n,&t);
    
38.         for(int i=1;i<=n;i++)
    
39.         {
    
40.                 scanf("%d",&a[i]);
    
41.         }
    
42.         biuld_xian(1,n,1);
    
43.         while(t--)
    
44.         {
    
45.                 scanf("%d%d",&x,&y);
    
46.                 printf("%d ",query(x,y,1,n,1));
    
47.         }
    
48.         return 0;
    
49. }

复制代码

---

作者: liubo    时间: 2018-7-30 23:45

1. #include<iostream>
   
2. using namespace std;
   
3. const int maxn = 100005;
   
4. struct node{
   
5.     int minv;
   
6.     int l,r;
   
7.     int mid(){
   
8.         return (l + r)/2;
   
9.     }
   
10. }t[300010];
    
11. int ans = 1 << 30,m,n;
    
12. void buildTree(int root,int l,int r){
    
13.     node &n = t[root];
    
14.     n.l = l;
    
15.     n.r = r;
    
16.     n.minv = 1 << 30;
    
17.     if(l == r)return;
    
18.     buildTree(root * 2 + 1,l,n.mid());
    
19.     buildTree(root * 2 + 2,n.mid() + 1,r);
    
20. }
    
21. void insertNum(int root,int i,int v){
    
22.     node &n = t[root];
    
23.     if(n.l == n.r && n.l == i){
    
24.         n.minv = v;
    
25.         return;
    
26.     }
    
27.     n.minv = min(n.minv,v);
    
28.     if(i > n.mid())
    
29.         insertNum(root * 2 + 2,i,v);
    
30.     else insertNum(root * 2 + 1,i,v);
    
31. }
    
32. void ask(int root,int l,int r){
    
33.     node &n = t[root];
    
34.     if(n.l == l && n.r == r){
    
35.         ans = min(ans,n.minv);
    
36.         return;
    
37.     }
    
38.     if(l > n.mid())
    
39.         ask(root * 2 + 2,l,r);
    
40.     else if(r <= n.mid())
    
41.         ask(root * 2 + 1,l,r);
    
42.     else{
    
43.         ask(root * 2 + 1,l,n.mid());
    
44.         ask(root * 2 + 2,n.mid() + 1,r);
    
45.     }
    
46. }
    
47. int main(){
    
48.     cin >> m >> n;
    
49.     buildTree(0,1,m);
    
50.     for(int i = 1;i <= m;i++){
    
51.         int k;
    
52.         cin >> k;
    
53.         insertNum(0,i,k);
    
54.     }
    
55.     for(int i = 1;i <= n;i++){
    
56.         int l,r;
    
57.         cin >> l >> r;
    
58.         ans = 1 << 30;
    
59.         ask(0,l,r);
    
60.         cout << ans << " ";
    
61.     }
    
62.     return 0;
    
63. }

复制代码

---

作者: 黄煦喆    时间: 2018-7-31 09:22

1. #include<iostream>
   
2. using namespace std;
   
3. int m,n,t,s,e;
   
4. struct node
   
5. {
   
6.     int l,r,minv;
   
7.     node *pleft,*pright;
   
8.     int mid()
   
9.     {
   
10.         return l+(r-l>>1);
    
11.     }
    
12. }tree[400010];
    
13. int cnt;
    
14. void build(node *root,int l,int r)
    
15. {
    
16.     root->l=l;
    
17.     root->r=r;
    
18.     root->minv=9999999;
    
19.     if(l==r)return;
    
20.     else
    
21.     {
    
22.         int Mid=root->l+(r-l>>1);
    
23.         cnt++;
    
24.         root->pleft=tree+cnt;
    
25.         cnt++;
    
26.         root->pright=tree+cnt;
    
27.         build(root->pleft,l,Mid);
    
28.         build(root->pright,Mid+1,r);
    
29.     }
    
30. }
    
31. void _insert(node *root,int i,int v)
    
32. {
    
33.     if(root->l==i&&root->r==i)
    
34.     {
    
35.         root->minv=v;
    
36.         return;
    
37.     }
    
38.     else
    
39.     {
    
40.         root->minv=min(v,root->minv);
    
41.         if(i<=root->mid())_insert(root->pleft,i,v);
    
42.         else if(i>root->mid())_insert(root->pright,i,v);
    
43.     }
    
44. }
    
45. int query(node* root,int a,int b)
    
46. {
    
47.     if(root->l==a&&root->r==b)return root->minv;
    
48.     if(b<=root->mid())return query(root->pleft,a,b);
    
49.     else if(a>root->mid())return query(root->pright,a,b);
    
50.     else
    
51.     {
    
52.         int ans1=9999999,ans2=9999999;
    
53.         ans1=query(root->pleft,a,root->mid());
    
54.         ans2=query(root->pright,root->mid()+1,b);
    
55.         return min(ans1,ans2);
    
56.     }
    
57. }
    
58. int main()
    
59. {
    
60.     cin>>m>>n;
    
61.     build(tree,1,m);
    
62.     for(int i=1;i<=m;i++)
    
63.     {
    
64.         cin>>t;
    
65.         _insert(tree,i,t);
    
66.     }
    
67.     for(int i=1;i<=n;i++)
    
68.     {
    
69.         cin>>s>>e;
    
70.         cout<<query(tree,s,e)<<' ';
    
71.     }
    
72.     return 0;
    
73. }
    

复制代码

---

作者: zhwang    时间: 2018-7-31 10:04

1. #include<cstdio>
   
2. #include<algorithm>
   
3. #define INF 999999999
   
4. using namespace std;
   
5. int n,m;
   
6. int a[100001];
   
7. struct node
   
8. {
   
9.     int left;
   
10.     int right;
    
11.     int _min;
    
12. }tree[400001];
    
13. int l,r;
    
14. void setup(int root,int start,int end)
    
15. {
    
16.     tree[root].left=start;
    
17.     tree[root].right=end;
    
18.     if(start==end)
    
19.     {
    
20.         tree[root]._min=a[start];
    
21.     }
    
22.     else
    
23.     {
    
24.         setup(root*2,start,(start+end)/2);
    
25.         setup(root*2+1,(start+end)/2+1,end);
    
26.         tree[root]._min=min(tree[root*2]._min,tree[root*2+1]._min);
    
27.     }
    
28. }
    
29. int findout(int root,int start,int end)
    
30. {
    
31.     if(tree[root].left==start&&tree[root].right==end)
    
32.     {
    
33.         return tree[root]._min;
    
34.     }
    
35.     int answer=INF;
    
36.     if(start>=tree[root*2+1].left)
    
37.     {
    
38.         answer=findout(root*2+1,start,end);
    
39.     }
    
40.     else
    
41.     {
    
42.         if(end<=tree[root*2].right)
    
43.         {
    
44.             answer=findout(root*2,start,end);
    
45.         }
    
46.         else
    
47.         {
    
48.             answer=min(findout(root*2,start,tree[root*2].right),findout(root*2+1,tree[root*2+1].left,end));
    
49.         }
    
50.     }
    
51.     return answer;
    
52. }
    
53. int main()
    
54. {
    
55.     scanf("%d%d",&n,&m);
    
56.     for(int i=1;i<=n;i++)
    
57.     {
    
58.         scanf("%d",&a[i]);
    
59.     }
    
60.     setup(1,1,n);
    
61.     for(int i=1;i<=m;i++)
    
62.     {
    
63.         scanf("%d%d",&l,&r);
    
64.         printf("%d ",findout(1,l,r));
    
65.     }
    
66.     return 0;
    
67. }

复制代码

---

作者: admin    时间: 2019-11-9 21:26
楼上大佬们都是用线段树再做，其实还有更简单的写法，ST表。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int mn=100010;
   
4. int n,k,i,j,x,y,z;
   
5. int a[mn],f[mn][100];
   
6. void check()
   
7. {
   
8.         for (int i=1; i<=n; i++,cout<<endl)
   
9.                 for (int j=0; i+(1<<j)-1<=n; j++)  cout<<setw(4)<<f[i][j];
   
10. }
    
11. int main()
    
12. {
    
13.         cin>>n>>k;
    
14.         for (int i=1; i<=n; i++) cin>>a[i];
    
15.         ///递推得到F数组
    
16.         for (i=1; i<=n; i++) f[i][0]=a[i];
    
17.         for (j=1; (1<<j)<=n; j++)
    
18.                 for (i=1; i+(1<<j)-1<=n; i++)
    
19.                         f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); ///注意边界
    
20.         ///check();
    
21.         while (k--)
    
22.         {
    
23.                 cin>>x>>y;
    
24.                 z=log2(y-x+1);
    
25.                 cout<<min(f[x][z],f[y-(1<<z)+1][z])<<" ";
    
26.         }
    
27.         return 0;
    
28. }

复制代码

---

作者: 秀木于林    时间: 2019-12-20 17:54

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int a[100100],f[100100][20],l,r,n,m;
   
5. int pow2(int x)
   
6. {
   
7.     int s=1;
   
8.     for(int i=1; i<=x; i++) s*=2;
   
9.     return s;
   
10. }
    
11. int main()
    
12. {
    
13.     cin>>n>>m;
    
14.     int t=log2(n);
    
15.     for(int i=1;i<=n;i++)
    
16.         cin>>f[i][0];
    
17.     for(int j=1;j<=t;j++)
    
18.     for(int i=1;i<=n;i++)
    
19.         if(i+(1<<j)-1<=n)
    
20.     ///f[i][j]=min(f[i][j-1],f[i+pow2(j-1)][j-1]);
    
21.     f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    
22. 
    
23. /*
    
24.     for(int i=1;i<=n;i++,cout<<endl)
    
25.         for(int j=1;j<=20;j++)
    
26.         if(i+pow2(j)-1<=n)
    
27.         cout<<f[i][j]<<' ';
    
28. */
    
29. 
    
30.     for(int k=1;k<=m;k++)
    
31.     {
    
32.         cin>>l>>r;
    
33.         int j=log2(r-l+1);
    
34.         cout<<min(f[l][j],f[r-(1<<j)+1][j])<<' ';
    
35.     }
    
36.     return 0;
    
37. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2