比赛 |
EYOI与SBOI开学欢乐赛13th |
评测结果 |
AAAAAAAAAA |
题目名称 |
WHZ 的序列 |
最终得分 |
100 |
用户昵称 |
yrtiop |
运行时间 |
0.996 s |
代码语言 |
C++ |
内存使用 |
10.08 MiB |
提交时间 |
2022-10-21 19:10:27 |
显示代码纯文本
#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 2e5 + 5;
int n,a[maxn];
struct BIT {
ll c[maxn],sum[maxn];
BIT() {
memset(c , 0 , sizeof(c));
}
int lowbit(int x) {
return x & -x;
}
void add(int x,int y) {
int res = x;
for(;x <= n;x += lowbit(x))c[x] += y,sum[x] += 1ll * res * y;
return ;
}
ll query(int x) {
ll ans = 0;
int res = x;
for(;x;x -= lowbit(x))ans += 1ll * (res + 1) * c[x] - sum[x];
return ans;
}
}tr[2];
int main() {
freopen("whz_sequence.in","r",stdin);
freopen("whz_sequence.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i <= n;++ i) {
scanf("%d",&a[i]);
tr[~ i & 1].add((i + 1) / 2 , a[i]);
tr[~ i & 1].add((i + 1) / 2 + 1 , -a[i]);
}
int Q;
scanf("%d",&Q);
while(Q --) {
int op,l,r,d;
scanf("%d %d %d",&op,&l,&r);
if(op == 1) {
scanf("%d",&d);
if((r - l) & 1) {
tr[~ l & 1].add((l + 1) / 2 , d);
tr[~ l & 1].add(r / 2 + 1 , -d);
tr[l & 1].add(l / 2 + 1 , d);
tr[l & 1].add((r + 1) / 2 + 1 , -d);
}
else {
tr[~ l & 1].add((l + 1) / 2 , d);
tr[~ l & 1].add((r + 1) / 2 + 1 , -d);
tr[l & 1].add(l / 2 + 1 , d);
tr[l & 1].add(r / 2 + 1 , -d);
}
}
else {
ll ans = 0;
if((r - l) & 1) {
ans += tr[~ l & 1].query(r / 2) - tr[~ l & 1].query((l + 1) / 2 - 1);
ans -= tr[l & 1].query((r + 1) / 2) - tr[l & 1].query(l / 2);
}
else {
ans += tr[~ l & 1].query((r + 1) / 2) - tr[~ l & 1].query((l + 1) / 2 - 1);
ans -= tr[l & 1].query(r / 2) - tr[l & 1].query(l / 2);
}
printf("%lld\n",ans);
}
}
return 0;
}