问题 H: 老管家的忠诚
时间限制: 0 Sec 内存限制: 128 MB
提交: 54 解决: 21
[提交][状态][讨论版][命题人:外部导入]
题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。 在询问过程中账本的内容可能会被修改
输入
输入中第一行有两个数m,n表示有m(m< =100000)笔账,n表示有n个问题，n< =100000。 接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y 当p=1 则查询x,y区间 当p=2 则改变第x个数为y
输出
输出文件中为每个问题的答案。具体查看样例。
样例输入
10 3
1 2 3 4 5 6 7 8 9 10
1 2 7
2 2 0
1 1 10
样例输出
2 0
提示
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include<cmath>
#include <vector>
using namespace std;
typedef long long ll;
const ll maxn = <<;
const ll maxd = 1e8+;
const ll mod = ;
ll b[maxn];
ll date[maxn*-],n;
void init(ll nn)
{
n=;
while(n<nn)
{
n*=;
}
for(ll i=;i<=*n-;i++)
{
date[i]=mod;
}
}
void update(ll k,ll a)
{
k+=n-;
date[k]=a;
while(k>)
{
k=(k-)/;
date[k]=min(date[k*+],date[k*+]);
}
}
ll query(ll a,ll b,ll k,ll l,ll r)
{
if(r<=a||b<=l)
{
return mod;
}
if(a<=l&&r<=b)
{
return date[k];
}else
{
ll vl=query(a,b,k*+,l,(l+r)/);
ll vr=query(a,b,k*+,(l+r)/,r);
return min(vl,vr);
}
}
int main()
{
ll i,m,j,k,l;
scanf("%lld %lld",&j,&m);
init(j);
for(i=;i<j;i++)
{
scanf("%lld",&b[i]);
update(i,b[i]);
}
ll r,q;
for(i=;i<=m;i++)
{
scanf("%lld %lld %lld",&q,&l,&r);
if(q==)
{
update(l-,r);
b[l-]=r;
continue;
}
if(l>r)
{
swap(l,r);
}
if(l==r)
{
printf("%lld",b[l-]);
if(i<m)
{
printf(" ");
}else
{
printf("\n"); }
continue;
}
ll mm=;
printf("%lld",query(max(l-,mm),r,,,n));
if(i<m)
{
printf(" ");
}
}
return ;
}