比赛 |
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;
}