# 【Tyvj1039】忠诚 2

## 样例输入 SampleInput

10 3
1 2 3 4 5 6 7 8 9 10
1 2 7
2 2 0
1 1 10

2 0

Tyvj 1039

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x7fffffff
struct point
{
int l,r,min,ls,rs,fa;
bool used;
};
point tree[1000000];
int a[200000];
int c[200000];
int i,j,t,n,m,k,z,y,x,tot;
void test()
{
for (i=1;i<=tot;i++)
{
cout<<"(i="<<i<<")"<<tree[i].fa<<"^"<<tree[i].l<<"~"<<tree[i].r<<";"<<tree[i].ls<<"/"<<tree[i].rs<<":"<<tree[i].min<<endl;
}
}
void maketree(int x,int y)
{
int i,j,t;
tot++;
t=tot;
tree[t].l=x;
tree[t].r=y;
if (x==y)
{
tree[t].min=a[x];
c[x]=t;
}
if (x!=y)
{
tree[t].ls=tot+1;
maketree(x,(x+y)/2);
tree[t].rs=tot+1;
maketree((x+y)/2+1,y);
tree[t].min=min(tree[tree[t].ls].min,tree[tree[t].rs].min);
tree[tree[t].ls].fa=t;
tree[tree[t].rs].fa=t;
}
}
int find(int k,int x,int y)
{
int i,j,t,mid;
if (x>y) return 0;
if (x==y) return tree[c[x]].min;
mid=(tree[k].l+tree[k].r)/2;
if (tree[k].l>=x && tree[k].r<=y) return tree[k].min;
if (y<=mid) return find(tree[k].ls,x,y);
if (x>=mid+1) return find(tree[k].rs,x,y);
return min(find(tree[k].ls,x,mid),find(tree[k].rs,mid+1,y));
}
int modify(int x,int y)
{
int i,j,t;
t=c[x];
tree[t].min=y;
while (t=tree[t].fa)
{
tree[t].min=min(tree[tree[t].ls].min,tree[tree[t].rs].min);
}
}
int main()
{
//freopen("tyvj1039.in","r",stdin);
//freopen("tyvj1039.out","w",stdout);
scanf("%d%d",&m,&n);
memset(c,0,sizeof(c));
for (i=1;i<=m;i++) scanf("%d",&a[i]);
tot=0;
maketree(1,m);
//test();
tree[1].fa=0;
for (i=0;i<n;i++)
{
scanf("%d%d%d",&z,&x,&y);
if (z==1)
{
printf("%d",find(1,x,y));
}
if (z==2)
{
modify(x,y);
//test();
}
}
return 0;
}``````