HiHo一下 Week18 Week19 动态RMQ

HiHo

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为一个整数N，意义如前文所述。

每组测试数据的第2行为N个整数，分别描述每种商品的重量，其中第i个整数表示标号为i的商品的重量weight_i。

每组测试数据的第3行为一个整数Q，表示小Hi总共询问的次数与商品的重量被更改的次数之和。

每组测试数据的第N+4~N+Q+3行，每行分别描述一次操作，每行的开头均为一个属于0或1的数字，分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行，如果该行描述一个询问，则接下来为两个整数Li, Ri，表示小Hi询问的一个区间[Li, Ri]；如果该行描述一次商品的重量的更改，则接下来为两个整数Pi，Wi，表示位置编号为Pi的商品的重量变更为Wi

对于100%的数据，满足N<=10^6，Q<=10^6, 1<=Li<=Ri<=N，1<=Pi<=N, 0< weight_i, Wi< =10^4。

输出

对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。

样例

• 输入

10
3655 5246 8991 5933 7474 7603 6098 6654 2414 884 
6
0 4 9
0 2 10
1 4 7009
0 5 6
1 3 7949
1 3 1227

• 输出

2414
884
7474

思路

这里用的是线段树的方法(segment tree),线段树的教程有这个。

代码

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int MAX=1000005;
std::vector<int> items;
int tree[2*MAX];
int min(int a,int b){
    if (a<b) return a;
    else return b;
}
int  buildTree(int l,int r,int p){
    if (l==r) {
        tree[p] = items[l]; 
        return tree[p];
    }
    int m = (l+r)/2;
    tree[p] = min(buildTree(l,m,p<<1),buildTree(m+1,r,p<<1|1)); 
    return tree[p];
}
void update(int x,int y,int l,int r,int t){
    if(l==r) {
        tree[t] = y;return;
    }
    int m = (l+r)/2;
    if(x<=m) {  
    update(x,y,l,m,t<<1);}
    else update(x,y,m+1,r,t<<1|1);
    tree[t] = min(tree[t<<1],tree[t<<1|1]);
}
int query(int x,int y,int l,int r,int t){
    if(x<=l&&y>=r) return tree[t];
    int m = (l+r)/2;
    int val = 1e5;
    if(x<=m) val = min(val,query(x,y,l,m,t<<1));
    if(y>m) val = min(val,query(x,y,m+1,r,t<<1|1)); 
    return val;
}
int main(){
    int n,q,f,t,a,b;
    scanf("%d",&n);
    items.push_back(-1);
    for(int i=0;i<n;i++) {
        scanf("%d",&t);
        items.push_back(t);
    }   
    buildTree(1,n,1);
    scanf("%d",&q);
    while(q--){
        scanf("%d%d%d",&f,&a,&b);
        if(f) update(a,b,1,n,1);
        else printf("%d\n",query(a,b,1,n,1));
        }   
    return 0;
}