Codechef 15.3 TREECNT2 数学,并查集
Codechef 14.6 TWOCOMP 树链求交+网络流

Codechef 14.11 FNCS 分块

shinbokuow posted @ Nov 20, 2015 04:09:32 PM in Something with tags 分块 , 470 阅读

 

题目大意:

给定一个长度为$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;
} 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter