Codechef 14.11 FNCS 分块
题目大意：
给定一个长度为$n$的序列$a_i$，同时还有$n$个函数，第$i$个函数为$f_i=\sum_{j=l_i}^{r_j}a_j$，函数的值会随着$a_i$的变化而发生改变。
现在要支持一些操作，要么改变某个$a_i$的值，要么给定$l,r$，求$\sum_{i=l}^{r}f_i$。
数据范围$n,q\leq{10^5}$。
算法讨论：
考虑分块，将$n$个函数分成$\sqrt{n}$块，在块内维护所有函数的和函数中每个$a_i$的常系数以及块内的答案，利用打标记再扫一遍的方法，时间复杂度$O(n\sqrt{n})$。
同样用分块的方法维护序列$a_i$的前缀和，将序列分成$\sqrt{n}$块，当我们修改某个$a_i$的时候，在$a_i$后面的块打上标记，$a_i$所在的块暴力重建，时间复杂度$\sqrt{n}$，同时对于函数所在的每个块利用我们维护的$a_i$的常数$O(1)$修改，时间复杂度$O(\sqrt{n})$。
考虑如何回答询问，首先对于函数的整块直接更新答案，对于$O(\sqrt{n})$零散部分的函数，每个函数都能用$a_i$的两个前缀和相减，而我们已经维护了前缀和，可以$O(1)$计算，时间复杂度$O(\sqrt{n})$。
综上，我们就能在$O((n+q)\sqrt{n})$的时间解决此题。
时空复杂度：
时间复杂度$O((n+q)\sqrt{n})$，空间复杂度$O(n\sqrt{n})$。
代码：（跟题解写的不是一个算法QwQ）
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, L, stdin);
if (S == T)
return EOF;
}
return *S++;
}
int getint() {
static int c, x;
while (!isdigit(c = getc()));
x = c - '0';
while (isdigit(c = getc()))
x = (x << 1) + (x << 3) + c - '0';
return x;
}
char buf[100010 * 21], *o = buf;
void output(llu x) {
static short stack[25], top;
top = 0;
while (x)
stack[top++] = x % 10, x /= 10;
while (top--)
*o++ = '0' + stack[top];
*o++ = '\n';
}
#define N 100010
int n, a[N], l[N], r[N];
int lp[N], rp[N], label[N], cnt;
int c[351][N];
ll ans[351];
ll A[N];
ll query(int x) {
static ll re;
for (re = 0; x; x ^= (x & -x))
re += A[x];
return re;
}
void modify(int x, int d) {
for (; x <= n; x += x & -x)
A[x] += d;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
freopen("tt.out", "w", stdout);
#endif
n = getint();
int i, j;
for (i = 1; i <= n; ++i) {
a[i] = getint();
modify(i, a[i]);
}
for (i = 1; i <= n; ++i) {
l[i] = getint();
r[i] = getint();
}
//int m = ceil(sqrt(n * log(n)));
int m = ceil(sqrt(n));
int point = 0;
while (point < n) {
lp[++cnt] = point + 1;
for (i = 1; i <= m && point < n; ++i)
++point;
rp[cnt] = point;
for (i = lp[cnt]; i <= rp[cnt]; ++i)
label[i] = cnt;
}
for (i = 1; i <= cnt; ++i) {
for (j = lp[i]; j <= rp[i]; ++j) {
++c[i][l[j]];
--c[i][r[j] + 1];
}
for (j = 1; j <= n; ++j)
ans[i] += (ll)(c[i][j] += c[i][j - 1]) * a[j];
}
int type, x, y, q = getint();
llu re;
while (q--) {
type = getint();
x = getint();
y = getint();
if (type == 1) {
for (i = 1; i <= cnt; ++i)
ans[i] += (ll)c[i][x] * (y - a[x]);
modify(x, -a[x] + y);
a[x] = y;
}
else {
re = 0;
for (i = label[x] + 1; i < label[y]; ++i)
re += ans[i];
if (label[x] == label[y]) {
for (i = x; i <= y; ++i)
re += query(r[i]) - query(l[i] - 1);
}
else {
for (i = x; label[i] == label[x]; ++i)
re += query(r[i]) - query(l[i] - 1);
for (i = y; label[i] == label[y]; --i)
re += query(r[i]) - query(l[i] - 1);
}
output(re);
}
}
fwrite(buf, 1, o - buf, stdout);
fflush(stdout);
return 0;
}
评论 (0)