LOJ6280 数列分块入门 4

LOJ6280 数列分块入门 4

标签

• 分块入门

前言

• 我的csdn和博客园是同步的，欢迎来访danzh-博客园~

简明题意

• 维护序列，支持两种操作：
  1. 区间加
  2. 区间查询

思路

• 多维护一个tag[]和一个sum[]就可以了~

注意事项

• 无

总结

• 无

AC代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;const int maxn = 1e5 + 10;int n, a[maxn];
int pos[maxn], len, tag[maxn], sum[maxn];void change(int l, int r, int c)
{for (int i = l; i <= min(len * pos[l], r); i++)a[i] += c, sum[pos[i]] += c;if (pos[l] != pos[r])for (int i = r; i >= len * pos[r] - len + 1; i--)a[i] += c, sum[pos[i]] += c;for (int i = pos[l] + 1; i <= pos[r] - 1; i++)tag[i] += c;
}int cal(int l, int r, int c)
{long long ans = 0;for (int i = l; i <= min(len * pos[l], r); i++)ans += 1ll * a[i] + tag[pos[i]], ans %= (c + 1);if (pos[l] != pos[r])for (int i = r; i >= len * pos[r] - len + 1; i--)ans += 1ll * a[i] + tag[pos[i]], ans %= (c + 1);for (int i = pos[l] + 1; i <= pos[r] - 1; i++)ans += sum[i] + 1ll * tag[i] * len, ans %= (c + 1);return ans;
}void solve()
{scanf("%d", &n);len = sqrt(n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]), pos[i] = (i - 1) / len + 1, sum[pos[i]] += a[i];for (int i = 1; i <= n; i++){int opt, l, r, c;scanf("%d%d%d%d", &opt, &l, &r, &c);if (opt == 0)change(l, r, c);elseprintf("%d\n", cal(l, r, c));}
}int main()
{freopen("Testin.txt", "r", stdin);//freopen("Testout.txt", "w", stdout);solve();return 0;
}