题目：Codechef Chef and Churu

俺的题解：https://www.luogu.com.cn/paste/vgggg7m0

俺的代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100005, M = 350;
typedef long long LL;
typedef pair<int, int> PII;
int st[M], ed[M], pos[N];
int t;
LL sum[M];
LL tr[N];
PII func[N];
LL cnt[M][N];
int a[N];
int n, q;
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int c)  
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL query(int x)  
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
//计算一个函数的值
LL calc(int i)
{
    int L = func[i].first, R = func[i].second;
    LL val = query(R) - query(L - 1);
    return val;
}
void init()
{
    int block = sqrt(n);
    t = n / block;
    if (n % block) t++;
    for (int i = 1; i <= t; i++)
    {
        st[i] = (i - 1) * block + 1;
        ed[i] = i * block;
    }
    ed[t] = n;
    for (int i = 1; i <= n; i++)
    {
        pos[i] = (i - 1) / block + 1;
        sum[pos[i]] += calc(i);
    }
    for (int i = 1; i <= n; i++) 
    {
        int id = pos[i];
        int L = func[i].first, R = func[i].second;
        cnt[id][L]++, cnt[id][R + 1]--;
    }
    for (int i = 1; i <= t; i++)
        for (int j = 1; j <= n; j++)
            cnt[i][j] += cnt[i][j - 1];
}
LL ask(int L, int R)
{
    int p = pos[L], q = pos[R];
    LL res = 0;
    if (p == q)
    {
        for (int i = L; i <= R; i++) res += calc(i);
    }
    else
    {
        for (int i = p + 1; i <= q - 1; i++) res += sum[i];
        for (int i = L; i <= ed[p]; i++) res += calc(i);
        for (int i = st[q]; i <= R; i++) res += calc(i);
    }
    return res;
}
void change(int x, int c)
{
    int d = c - a[x];
    for (int i = 1; i <= t; i++) sum[i] += 1ll * cnt[i][x] * d;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
    {
        scanf("%d", &a[i]);
        add(i, a[i]);
    }
    for (int i = 1; i <= n; i++) 
    {
        int l, r;
        scanf("%d%d", &l, &r);
        func[i] = { l, r };
    }
    scanf("%d", &q);
    init();
    for (int i = 1; i <= q; i++)
    {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1)
        {
            change(x, y);
            add(x, y - a[x]);
            a[x] = y;
        }
        else printf("%lld\n", ask(x, y));
    }
    return 0;
}

Codechef 上面 subtask3 错了一个点，百思不得其解