首页 > 代码库 > codevs 2174 忠诚S
codevs 2174 忠诚S
2174 忠诚S
时间限制: 1 s 空间限制: 32000 KB 题目等级 : 钻石 Diamond
题目描述 Description
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。(在询问过程中账本的内容可能会被修改)
输入描述 Input Description
输入中第一行有两个数m,n表示有m笔账,n表示有n个问。
接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y
当p=1 则查询x,y区间
当p=2 则改变第x个数为y
输出描述 Output Description
输出文件中为每个问题的答案。具体查看样例。
样例输入 Sample Input
10 3
1 2 3 4 5 6 7 8 9 10
1 2 7
2 2 0
1 1 10
样例输出 Sample Output
2 0
数据范围及提示 Data Size & Hint
m, n<=100000
喜闻乐见的Code
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxn 100010struct Segment_Tree{ int l,r,Min;}t[maxn*4];int a[maxn];void Built_Tree(int now,int L,int R) { t[now].l=L,t[now].r=R; if(L==R) { t[now].Min=a[R]; return; } int mid=(L+R)>>1,lc=now<<1,rc=now<<1|1; Built_Tree(lc,L,mid); Built_Tree(rc,mid+1,R); t[now].Min=min(t[lc].Min,t[rc].Min);}void MSN(int now,int pos,int x) { int l=t[now].l,r=t[now].r; if(l==r) { t[now].Min=x; return; } int mid=(l+r)/2,lc=now<<1,rc=now<<1|1; if(pos<=mid)MSN(lc,pos,x); if(pos>mid)MSN(rc,pos,x); t[now].Min=min(t[lc].Min,t[rc].Min);}int QI(int now,int L,int R) { int l=t[now].l,r=t[now].r; if(l==L&&R==r) return t[now].Min; int mid=(l+r)>>1,lc=now<<1,rc=now<<1|1; if(R<=mid) return QI(lc,L,R); else if(L>mid) return QI(rc,L,R); else return (min(QI(lc,L,mid),QI(rc,mid+1,R)));}int main() { int n,m; scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) scanf("%d",&a[i]); Built_Tree(1,1,m); while(n--) { int op,x,y; scanf("%d",&op); if(op==1) { scanf("%d%d",&x,&y); printf("%d ",QI(1,x,y)); } else { scanf("%d%d",&x,&y); MSN(1,x,y); } } return 0;}
codevs 2174 忠诚S
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。