Mar 8

uva - 2191 - Potentiometers 不指定

felix021 @ 2009-3-8 01:32 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(4315) | Via 本站原创 | |
抽象题意:给出最多200,000个不超过1000的非负整数,对最多200,000次以下两类操作进行处理
1.  M x y   ——求第x到第y个整数之间的所有整数的和。
2.  S x v   ——将第x个整数的值置为v。

显然,硬搞要TLE的,稍微想了一下,就知道应该用线段树(或者树状数组?)来完成。
关于线段树可以参考 http://acm.whu.edu.cn/blog/read.php?26 以及 http://acm.whu.edu.cn/blog/read.php?51

简单的说,就是用一个平衡二叉树来存储这些东西,
每个叶节点存放一个整数(一个单位"线段"),
而每个分支节点存放的是一条"线段"

在M操作的时候,只要递归地将线段xy分割,能够在logN的时间内查询出
在S操作的时候,只要递归地找到对应的叶节点更新,并在返回的时候一层层更新涉及到的分支节点即可,也是logN。

好久没有写稍长的代码了,这个线段树的具体实现也忘得差不多了,还是去翻了一下yyt的论文。
不过这次写得顺利多了,思路比较清晰。
具体的代码为
#include<stdio.h>

struct node{
    int l, m, r, v;
} tree[1000100];
int res[200100];

void make(int l, int r, int i = 1){
    tree[i].l = l;
    tree[i].r = r;
    tree[i].m = (l + r) / 2;
    if(l == r){
        tree[i].v = res[l];
        return;
    }else{
        make(l, tree[i].m, 2 * i);
        make(tree[i].m + 1, r, 2 * i + 1);
        tree[i].v = tree[2*i].v + tree[2*i+1].v;
    }
}

void insert(int n, int v, int i = 1){
    if(tree[i].l == tree[i].r && tree[i].l == n){
        tree[i].v = v;
    }else{
        if(n <= tree[i].m){
            insert(n, v, 2 * i);
        }else{
            insert(n, v, 2 * i + 1);
        }
        tree[i].v = tree[2*i].v + tree[2*i+1].v;
    }
}

int count(int l, int r, int i = 1){
    if(tree[i].l == l && tree[i].r == r){
        return tree[i].v;
    }else{
        if(r <= tree[i].m){
            return count(l, r, 2 * i);
        }else if(l > tree[i].m){
            return count(l, r, 2 * i + 1);
        }else{
            return count(l, tree[i].m, 2 * i)
                 + count(tree[i].m + 1, r, 2 * i + 1);
        }
    }
}

void setv(){
    int n, v;
    scanf("%d%d", &n, &v);
    insert(n, v);
}

void measure(){
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", count(l, r));
}

int main(){
    int casec = 1, N, first = 1;
    char t;
    while(scanf("%d", &N), N != 0){
        if(first) first = 0;
        else putchar('\n');
        for(int i = 1; i <= N; ++i) scanf("%d", res+i);
        getchar();
        printf("Case %d:\n", casec++);
        make(1, N);
        while(true){
            t = getchar();
            if(t == 'M') measure();
            else if(t == 'S') setv();
            else if(t == 'E') {
                while(t = getchar(), t != '\n' && t != EOF);
                break;
            }
            while(t = getchar(), t != '\n' && t != EOF);
        }
    }
    return 0;
}





欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]