codechef FNCS-程序员宅基地

题意：一个数列a，若干个函数，每个函数j=sigma(a[i]),l[j]<=i<=r[j]。

op1:修改数列a中x位置元素为y。op2：求L~R的函数和。n<=1e5。

 

标程：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9') {
    if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
   return x*f;
}
const int N=100005;
int n,blo,a[N],l[N],r[N],b[320][N],q,x,y,op;
ll sum[N],k1[N],k2[N],s[N];

int trans1(int x){
    return x>blo*blo?blo:(x-1)/blo+1;}//所在块 
int trans2(int x){
    int t=trans1(x);return t==blo?n:t*blo;}//所在块的右端点 

void modi(int pos,int x)
{
    for (int i=trans1(pos);i<=blo;i++) k1[i]+=x;
    for (int i=pos,t=trans2(pos);i<=t;i++) k2[i]+=x;
}

ll qry(int x){
    return s[x]+k1[trans1(x)-1]+k2[x];
}

ll calc(int x)
{
    ll res=0;int id=trans1(x);
    for (int i=1;i<id;i++) res+=sum[i];
    for (int i=(id-1)*blo+1;i<=x;i++) res+=qry(r[i])-qry(l[i]-1);
    return res;
}

int main()
{
    n=read();blo=(int)sqrt(n);
    for (int i=1;i<=n;i++) a[i]=read(),s[i]=(ll)s[i-1]+a[i];
    for (int i=1;i<=n;i++) l[i]=read(),r[i]=read();
    
   for (int i=1;i<=blo;i++)
   {
       int bl=(i-1)*blo+1,br=(i==blo)?n:i*blo;
       for (int j=bl;j<=br;j++) b[i][l[j]]++,b[i][r[j]+1]--;
       for (int j=1;j<=n;j++) b[i][j]+=b[i][j-1];
       for (int j=1;j<=n;j++) sum[i]+=(ll)b[i][j]*a[j];
    }
    
    q=read();
    while (q--)
    {
        op=read();x=read();y=read();
        if (op==1)
        {
            for (int i=1;i<=blo;i++) sum[i]+=(ll)b[i][x]*(y-a[x]);
         modi(x,y-a[x]);a[x]=y;
        }else printf("%llu\n",calc(y)-calc(x-1));
    }
   return 0;
}

 

易错点：1.没有开ll挂了90分。不要以为ll是小问题。

2.还要unsigned long long。

3.注意左右端点，尤其是最后一块。写个trans函数比较直观。

 

题解：分块+块链

对函数进行分块，每一块维护每个数列元素的需统计次数以及sum。（每个元素的出现次数可以用差分+前缀和）。

查询的时候整块暴力统计sum，零碎的直接统计即可。

零碎的统计要支持修改和区间查询，树状数组（插入查询O(logn）），块链（插入O(sqrt(n))，查询O(1)）都行。块链，就是对原数列分块，统计大块的前缀和，对于每个块统计内部元素的前缀和。