rt.

link：https://www.codechef.com/problems/FNCS。

题目大意：

给定 $n$ 个正整数 $a_i$ 和 $n$ 个二元组 $(l_i,r_i)$，要求支持两种操作：

1. $a_k\gets x$。

2. 查询 $\sum\limits_{i=l}^r\sum\limits_{j=l_i}^{r_i} a_j$。

$1\le l_i,r_i\le n\le 10^5,1\le q\le 10^5$。

大致思路：对第二个 $\sum$ 进行分块，对散块再对 $\{a_n\}$ 进行分块，维护前缀和，根号平衡。

注：需要开 ull。

喜提 Wrong Answer/kk

#include<bits/stdc++.h>
#define int unsigned long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e5+5,M=4e2+5;
int l[N],r[N],id[N],len,tot,n,q;
int w[N],tag[N],c[N];
int sum[N],cnt[N][M];
int a[N],b[N];
void init() {
    len=sqrt(n)+0.5;
    tot=(n-1)/len+1;
    rep(i,1,n)
        id[i]=(i-1)/len+1;
    rep(i,1,n)
        w[i]=w[i-1]+c[i];
    rep(i,1,tot) {
        l[i]=(i-1)*len+1,r[i]=i*len;
        rep(j,l[i],r[i])
            ++cnt[i][a[j]],--cnt[i][b[j]+1];
        rep(j,1,n) {
            cnt[i][j]+=cnt[i][j-1];
            sum[i]+=cnt[i][j]*c[j];
        }
    }
}
void update(int qx,int val) {
    rep(i,qx,r[id[qx]])
        w[i]+=val-c[qx];
    rep(i,id[qx]+1,tot)
        tag[i]+=val-c[qx];
    rep(i,1,tot)
        sum[i]+=(val-c[qx])*cnt[i][qx];
    c[qx]=val;
}
int ask(int ql,int qr) {
    return (w[qr]+tag[id[qr]])-(w[ql-1]+tag[id[ql-1]]);
}
int query(int ql,int qr) {
    if(id[ql]==id[qr]) {
        int res=0;
        rep(i,ql,qr)
            res+=ask(a[i],b[i]);
        return res;
    } else {
        int res=0;
        rep(i,ql,r[id[ql]])
            res+=ask(a[i],b[i]);
        rep(i,id[ql]+1,id[qr]-1)
            res+=sum[i];
        rep(i,l[id[qr]],qr)
            res+=ask(a[i],b[i]);
        return res;
    }
}
signed main() {
    scanf("%llu",&n);
    rep(i,1,n)
        scanf("%llu",&c[i]);
    rep(i,1,n)
        scanf("%llu%llu",&a[i],&b[i]);
    init();
    scanf("%llu",&q);
    while(q--) {
        int op;
        scanf("%llu",&op);
        if(op==1) {
            int p,val;
            scanf("%llu%llu",&p,&val);
            update(p,val);
        } else {
            int l,r;
            scanf("%llu%llu",&l,&r);
            printf("%llu\n",query(l,r));
        }
    }
    return 0;
}