【题解】LA P2191【Potentiometers】

这里是线段树维护区间和,单点修改,区间查询。

水题一道,但是输入方式特别鬼畜,详情见代码。


#include<cstdio>
#include<iostream>
#include<string>

namespace OI{
    using std::string;
    using std::cin;
}
using namespace OI;

const int MAXN = 666666;
int A[MAXN];

class SegmentTree{
    public:int l,r;
    public:int sum;
};
SegmentTree t[MAXN * 4];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int MID(int l,int r){return (l + r) >> 1;}

void maintain(int p){
    t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;
}

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].sum = A[l];
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    maintain(p);
}

void change(int p,int x,int v){
    if(t[p].l == t[p].r){
        t[p].sum = v;
        return;
    }
    if(x <= MID(t[p].l,t[p].r)){
        change(LEFT(p),x,v);
    }else{
        change(RIGHT(p),x,v);
    }
    maintain(p);
}

int ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].sum;
    }
    int ans = 0;
    if(l <= MID(t[p].l,t[p].r)){
        ans += ask(LEFT(p),l,r);
    }
    if(r > MID(t[p].l,t[p].r)){
        ans += ask(RIGHT(p),l,r);
    }
    return ans;
}

int main(){
    int n;
    int Case = 0;
    while(scanf("%d",&n) == 1 && n){
        if(Case){
            printf("\n");
        }
        
        printf("Case %d:\n",++Case);
        for(int i = 1;i <= n;i++){
            scanf("%d",&A[i]);
        }
        build(1,1,n);
        string op;
        int x,y;
        while(cin >> op && op != "END"){
            scanf("%d %d",&x,&y);
            printf("op:%d %d\n",x,y);
            if(op == "M"){
                printf("%d\n",ask(1,x,y));
            }else{
                change(1,x,y);
            }
        }
    }
    
    return 0;
}