【hdu】적병포진(선단수, 더욱 결점, 구간구화)

2437 단어
최근에 라인 트리를 닦기 시작했는데, 주로 notonlysuccess를 둘러싼 라인 트리를 총괄적으로 닦았다.
결점 수정은 비교적 간단하다. 게으름 표시가 필요 없고 바로 이분귀속하면 된다.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long LL;
#define MAXD 10
#define maxn 50010
int n;
int tree[maxn << 2];
void BuildTree(int l,int r,int pos){   // 
    if(l == r){
        scanf("%d",&tree[pos]);
        return ;
    }
    int m = (l + r) >> 1;
    BuildTree(l,m,(pos << 1));
    BuildTree(m + 1,r,(pos << 1)|1);
    tree[pos] = tree[pos << 1] + tree[(pos << 1) | 1];
    return ;
}
void UpDate(int aim,int value,int l,int r,int pos){  // , , 
    if(l == r){
        tree[pos] += value;
        return ;
    }
    int m = (l + r) >> 1;
    if(aim <= m) UpDate(aim,value,l,m,pos << 1);
    else
        UpDate(aim,value,m + 1, r,(pos << 1)|1);
    tree[pos] = tree[pos << 1] + tree[(pos << 1)|1];
    return ;
}
int Query(int L,int R,int l,int r,int pos){
    if(L <= l && r <= R)
        return tree[pos];
    int m = (l + r) >> 1;
    int ans = 0;
    if(L <= m)
        ans += Query(L,R,l,m,pos << 1);
    if(m + 1<= R)
        ans += Query(L,R,m + 1,r,(pos << 1)|1);
    return ans;
}
int main(){
    int T,Case = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        BuildTree(1,n,1);  // 
        char str[MAXD];
        printf("Case %d:
",Case++); while(scanf("%s",str)){ if(str[0] == 'A'){ int a,b; scanf("%d%d",&a,&b); UpDate(a,b,1,n,1); } else if(str[0] == 'Q'){ int a,b; scanf("%d%d",&a,&b); int ans = Query(a,b,1,n,1); printf("%d
",ans); } else if(str[0] == 'S'){ int a,b; scanf("%d%d",&a,&b); UpDate(a,-b,1,n,1); } else break; } } return 0; }

좋은 웹페이지 즐겨찾기