【Tyvj1039】忠诚 2

2014-03-26
竞赛题解 / 高级数据结构
TYVj线段树

描述 Description

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

输入格式 InputFormat

输入中第一行有两个数 m,n 表示有 m(m<=100000) 笔账, n 表示有 n 个问题，n<=100000。
接下来每行为 3 个数字，第一个 p 为数字 1 或数字 2，第二个数为 x，第三个数为 y。
当 p=1 则查询 x,y 区间。
当 p=2 则改变第 x 个数为 y。

输出格式 OutputFormat

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

样例输入 SampleInput

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

样例输出 SampleOutput

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;
}