HDU【1166】敌兵布阵(分块做法)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
int T, n, num, block;///num->块数，block->块的大小
int l[maxn], r[maxn], in[maxn], a[maxn], sum[maxn];
///l->块的左边界,r->块的右边界,in->当前索引属于哪个块

void Build(){
    block = sqrt(n);
    num = n/ block; if(n % block) num++;
    for(int i = 1; i <= num; i++)
        l[i] = (i - 1) * block + 1, r[i] = i * block;
    r[num] = n;
    for(int i = 1; i <= n; i++)
        in[i] = (i - 1) / block + 1;
    for(int i = 1; i <= num; i++)
        for(int j = l[i]; j <= r[i]; j++)
            sum[i] += a[j];
}

void UpDate(int x, int y){
    a[x] += y; sum[in[x]] += y;
}

int Query(int x, int y){
    int ans = 0;
    if(in[x] == in[y]){
        for(int i = x; i <= y; i++)
            ans += a[i];
        return ans;
    }
    for(int i = x; i <= r[in[x]]; i++)
        ans += a[i];
    for(int i = in[x] + 1; i < in[y]; i++)
        ans += sum[i];
    for(int i = l[in[y]]; i <= y; i++)
        ans += a[i];
    return ans;
}

int main(){
    scanf("%d", &T);
    for(int t = 1; t <= T; t++){
        printf("Case %d:\n", t);
        memset(sum, 0, sizeof(sum));
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        Build();
        char str[10];
        while(~scanf("%s", str) && str[0] != 'E'){
            int x, y;
            scanf("%d%d", &x, &y);
            if(str[0] == 'Q') printf("%d\n", Query(x, y));
            else if(str[0] == 'A') UpDate(x, y);
            else UpDate(x, -y);
        }
    }

    return 0;
}
/*
* ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
* └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
* │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/