比赛 SYOI 专题 4:分块(根号杂烩) 评测结果 AAAAAAAAAAAAAAA
题目名称 数列操作A 最终得分 100
用户昵称 yrtiop 运行时间 1.115 s
代码语言 C++ 内存使用 2.66 MiB
提交时间 2024-04-17 17:30:02
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 100005;
typedef long long ll;
int n,m;
int pos[maxn],L[maxn],R[maxn];
ll a[maxn],sum[maxn];
void Add(int x,ll k) {
    int p = pos[x];
    sum[p] += k;
    a[x] += k;
    return ;
}
ll query(int l,int r) {
    ll ans = 0;
    int p = pos[l],q = pos[r];
    if(p == q) {
        for(int i = l;i <= r;++ i) {
            ans += a[i];
        }
        return ans;
    }
    for(int i = p + 1;i <= q - 1;++ i) {
        ans += sum[i];
    }
    for(int i = l;i <= R[p];++ i) {
        ans += a[i];
    }
    for(int i = L[q];i <= r;++ i) {
        ans += a[i];
    }
    return ans;
}
int main() {
    freopen("shulie.in","r",stdin);
    freopen("shulie.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i) {
        scanf("%lld",&a[i]);
    }
    int t = sqrt(n);
    for(int i = 1;i <= t;++ i) {
        L[i] = (i - 1) * t + 1;
        R[i] = i * t; 
        for(int j = L[i];j <= R[i];++ j) {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
    if(t * t < n) {
        L[t + 1] = t * t + 1;
        R[t + 1] = n;
        ++ t;
        for(int j = L[t];j <= R[t];++ j) {
            sum[t] += a[j];
            pos[j] = t;
        }
    }
    scanf("%d",&m);
    for(int i = 1;i <= m;++ i) {
        char s[3];
        scanf("%s",s);
        if(s[0] == 'S') {
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(l , r));
        }
        else {
            int x;
            ll k;
            scanf("%d%lld",&x,&k);
            Add(x , k);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}