https://www.codechef.com/problems/FNCS
【题意】
【思路】
- 把n个函数分成√n块，预处理出每块中各个点(n个)被块中函数(√n个)覆盖的次数
- 查询时求前缀和，对于整块的分块求和，剩下右边不构成完整的一个块的树状数组求和
- 预处理：计算每个块中，序列中的第i个点被块中函数覆盖的次数，求出每个块内前缀的和（O(n√n)）；对于每个点，更新树状数组（nlogn）
- 单点修改：对于块状数组，因为已经知道了每个点被覆盖的次数，所以维护很简单（O(√n)）;对于树状数组，直接单点更新（O(logn)）;然后把a[pos]本身的值更新为x
- 查询：计算前缀和，求x到y之间的函数和就是计算cal(y)-cal(x-1)。对于前缀和，对于整块的直接求和（O(√n)），对于最右边剩下的树状数组查询区间和（最多√n个函数，每个函数logn,所以复杂度为√nlogn）
- 综上，时间复杂度为O(n√nlogn)
- 注意要爆long long,1e5*1e5*1e9=1e19,long long 的最大值为9223372036854775807，9e18多一点
【Accepted】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm> using namespace std;
typedef unsigned long long ull;
const int maxn=1e5+;
int n,m;
int a[maxn];
int belong[maxn];
int l[];
int r[];
ull sum[maxn];
ull tree[maxn];
int vis[][maxn];
struct Node
{
int l;
int r;
}q[maxn]; void init()
{
for(int i=;i<=n;i++)
{
tree[i]=0ull;
}
} int lowbit(int x)
{
return x&(-x);
}
void add(int k,int x)
{
while(k<=n)
{
tree[k]+=1ull*x;
k+=lowbit(k);
}
} ull query(int k)
{
ull res=0ull;
while(k)
{
res+=tree[k];
k-=lowbit(k);
}
return res;
}
ull query(int l,int r)
{
return query(r)-query(l-);
}
ull cal(int x)
{
if(x<)
{
return ;
}
int b=belong[x];
ull res=0ull;
for(int i=;i<b;i++)
{
res+=sum[i];
}
for(int i=l[b];i<=x;i++)
{
res+=query(q[i].l,q[i].r);
}
return res;
}
ull cal(int x,int y)
{
return cal(y)-cal(x-);
}
int main()
{
scanf("%d",&n);
init();
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
add(i,a[i]);
}
int block=sqrt(n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
belong[i]=(i-)/block+;
}
int cnt=n/block;
if(n%block)
{
cnt++;
}
for(int i=;i<=cnt;i++)
{
l[i]=(i-)*block+;
r[i]=i*block;
}
r[cnt]=n;
for(int i=;i<=cnt;i++)
{
for(int k=l[i];k<=r[i];k++)
{
vis[i][q[k].l]++;
vis[i][q[k].r+]--;
}
for(int k=;k<=n;k++)
{
vis[i][k]+=vis[i][k-];
sum[i]+=1ull*vis[i][k]*a[k];
}
}
scanf("%d",&m);
while(m--)
{
int op;
scanf("%d",&op);
if(op==)
{
int pos,x;
scanf("%d%d",&pos,&x);
for(int i=;i<=cnt;i++)
{
sum[i]+=1ull*vis[i][pos]*(x-a[pos]);
}
add(pos,x-a[pos]);
a[pos]=x;
}
else
{
int x,y;
scanf("%d%d",&x,&y);
ull ans=cal(x,y);
printf("%llu\n",ans);
}
} return ;
}
分块+树状数组