题目大意:
给定n q 为序列的个数和操作的个数
给定n个数的序列b[]作为分母
初始全为0的序列a[]作为分子
两种操作
add l r 为a[]的l到r区间全部+1
query l r 为查询l到r区间a[i]/b[i]的总和(向下取整)
因为是向下取整 所以线段树维护区间的min(b[i]-a[i]%b[i])
那么当区间的这个最小的sub值为0时 说明这个区间内至少有一个点有新的贡献
所以当sub值为0时 才更新答案并向下更新 否则更新lazy和sub即可
即在代码中 更新lazy和sub 当sub恰好等于0 那么更新now
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define LL long long #define mem(i,j) memset(i,j,sizeof(i)) using namespace std; const int N=1e5+5; const int MOD=1e9+7; int n, m, b[N]; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 LL lazy[N<<2], now[N<<2], sub[N<<2]; void pushUp(int rt) { sub[rt]=min(sub[rt<<1],sub[rt<<1|1]); now[rt]=now[rt<<1]+now[rt<<1|1]; } void pushDown(int rt) { if(lazy[rt]) { lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; sub[rt<<1]-=lazy[rt]; sub[rt<<1|1]-=lazy[rt]; lazy[rt]=0; } } void build(int l,int r,int rt) { lazy[rt]=0; now[rt]=0; if(l==r) { sub[rt]=b[l]; return; } int m=(l+r)>>1; build(lson); build(rson); pushUp(rt); } void updatesub(int l,int r,int rt) { if(l==r) { now[rt]++; sub[rt]=b[l]; return; } pushDown(rt); int m=(l+r)>>1; if(sub[rt<<1]==0) updatesub(lson); if(sub[rt<<1|1]==0) updatesub(rson); pushUp(rt); } void update(int L,int R,int l,int r,int rt) { if(L<=l && r<=R) { lazy[rt]++; sub[rt]--; if(sub[rt]==0) updatesub(l,r,rt); return; } pushDown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,lson); if(m<R) update(L,R,rson); pushUp(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l && r<=R) return now[rt]; pushDown(rt); int m=(l+r)>>1; int res=0; if(L<=m) res+=query(L,R,lson); if(m<R) res+=query(L,R,rson); return res; } void init() { mem(now,0); mem(sub,0); mem(lazy,0); } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) scanf("%d",&b[i]); init(); build(1,n,1); while(m--) { char op[10]; scanf("%s",op); int l,r; scanf("%d%d",&l,&r); if(op[0]=='a') update(l,r,1,n,1); else printf("%d ",query(l,r,1,n,1)); } } return 0; }