Chef and Churu

Chef and Churu

定义函数f[i]=a[li]+……+a[ri]

两个操作，修改a[i]为k；查询f[l]+……+f[r]

题目链接

#include
using namespace std;
#define Inc(i,L,r) for(register int i=(L);i<=(r);++i)
#define ll unsigned long long
const int N = 1e5+10,Maxsiz = 322;
int n,Q,a[N];
int siz,bl[N];
struct pair{int fir,sec;
}s[N];
struct BIT{ll c[N];#define lb(x) (x)&-(x)inline void add(int x,ll k){for(;x<=n;x+=lb(x))c[x]+=k;}inline ll sum(int x){ll ret=0;for(;x>0;x-=lb(x))ret+=c[x];return ret;}
}bit,num[Maxsiz];
ll block_sum[Maxsiz];//块和 
inline void init(){scanf("%d",&n);Inc(i,1,n)scanf("%d",&a[i]);Inc(i,1,n)bit.add(i,a[i]);//nlongn Inc(i,1,n)scanf("%d%d",&s[i].fir,&s[i].sec);siz=sqrt(n);Inc(i,1,n)bl[i]=(i-1)/siz+1;Inc(i,1,n)block_sum[bl[i]]+=bit.sum(s[i].sec)-bit.sum(s[i].fir-1);Inc(i,1,n)num[bl[i]].add(s[i].fir,1),num[bl[i]].add(s[i].sec+1,-1);//统计每个位置在块中出现的次数
}
inline void Change(int x,int k){Inc(i,1,bl[n])block_sum[i]+=num[i].sum(x)*(k-a[x]);//处理整块 bit.add(x,k-a[x]);//处理散块 a[x]=k;
}
inline ll Query(int L,int r){ll ret=0;if(bl[r]-bl[L]<=1){Inc(i,L,r)ret+=bit.sum(s[i].sec)-bit.sum(s[i].fir-1);//散块暴力求 }else {Inc(i,L,bl[L]*siz)ret+=bit.sum(s[i].sec)-bit.sum(s[i].fir-1);Inc(i,bl[L]+1,bl[r]-1)ret+=block_sum[i];//整块直接加 Inc(i,(bl[r]-1)*siz+1,r)ret+=bit.sum(s[i].sec)-bit.sum(s[i].fir-1);}return ret;
}
inline void solv(){scanf("%d",&Q);while(Q--){int op,L,r;scanf("%d%d%d",&op,&L,&r);if(op==1)Change(L,r);else cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！