现在的位置: 首页 > 综合 > 正文

hdu 1166 敌兵布阵

2014年02月04日 ⁄ 综合 ⁄ 共 1298字 ⁄ 字号 评论关闭
线段树区间求和
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>

#define INF 0x3fffffff
#define N 50010
#define M (N << 2)
#define LL long long
#define mod 95041567

using namespace std;

struct Node{
    int val;
    int sum;
};

int p[M];

void build(int rt, int l, int r){
    if(l == r){
        scanf("%d", &p[rt]);
        return ;
    }
    int mid = (r - l) / 2 + l;
    int lc = rt << 1;
    int rc = lc + 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    p[rt] = p[lc] + p[rc];
}

void update(int rt, int l, int r, int pos, int val){
    if(l == r) {
        p[rt] += val;
        return ;
    }
    int mid = (r - l)/ 2 + l;
    int lc = rt << 1;
    int rc =lc + 1;
    if(pos <= mid) update(lc, l, mid, pos, val);
    else update(rc, mid + 1, r, pos, val);
    p[rt] = p[lc] + p[rc];
}

void query(int rt, int l, int r, int L, int R, int &val){
    if(l == L && r == R){
        val += p[rt];
        return ;
    }
    int mid = (r - l) / 2 + l;
    int lc = rt << 1;
    int rc = lc + 1;
    if(L > mid) query(rc, mid + 1, r, L, R, val);
    else if(R <= mid) query(lc, l, mid, L, R, val);
    else {
        query(lc, l, mid, L, mid, val);
        query(rc, mid + 1, r, mid + 1, R, val);
    }
}

int main() {
  //  freopen("in.txt", "r", stdin);
    int t, cnt = 0;
    scanf("%d", &t);
    while(t --){
        printf("Case %d:\n", ++ cnt);
        int n;
        scanf("%d", &n);
        build(1, 1, n);
        while(1){
            char s[10];
            scanf("%s", s);
            if(s[0] == 'E') break;
            int i, j;
            scanf("%d %d", &i, &j);
            if(s[0] == 'Q') {
                int val = 0;
                query(1, 1, n, i, j, val);
                printf("%d\n", val);
            }
            else {
                if(s[0] == 'S') j = -j;
                update(1, 1, n, i, j);
            }
        }
    }
    return 0;
}

抱歉!评论已关闭.