直接在线段树上区间覆盖咯
怎么求和？
∑x=lr(A?x) mod B=∑x=lrA?x?B?∑x=lr?A?xB?
【线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN】后半部分直接用类欧求就好了 类似 [类欧几里得算法 数论] BZOJ 2987 Earthquake 但是更简单
#include
#include
#include
using namespace std;
typedef long long ll;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}inline void read(int &x){
char c=nc(),b=1;
for (;
!(c>='0' && c<='9');
c=nc()) if (c=='-') b=-1;
for (x=0;
c>='0' && c<='9';
x=x*10+c-'0',c=nc());
x*=b;
}inline ll gcd(ll a,ll b ) { return b?gcd(b,a%b):a;
}
inline ll calc(ll a,ll b,ll n){
ll x=a/b,sum=x*n*(n+1)/2;
a%=b;
if (!a || !b) return sum;
return sum+n*(a*n/b)-calc(b,a,a*n/b)+n/b;
}
inline ll solve(ll a,ll b,ll n){
if (n<1) return 0;
ll g=gcd(a,b);
return n*(n+1)/2*a-b*calc(a/g,b/g,n);
}const int N=200005;
const int M=N<<1;
struct info{
int l,r,a,b;
info(int l=0,int r=0,int a=-1,int b=0):l(l),r(r),a(a),b(b) { }
ll val(){
return solve(a,b,r)-solve(a,b,l-1);
}
};
int ls[M],rs[M];
ll sum[M];
info F[M];
int ncnt;
int sx[N],icnt;
#define L(x) (sx[x])
#define R(x) (sx[x+1]-1)inline void mark(int &x,info f){
if (!x) x=++ncnt;
F[x]=f;
sum[x]=f.val();
}inline void modify(int &x,int l,int r,int a,int b,int ql,int qr){
if (!x) x=++ncnt;
int mid=(l+r)>>1;
if (ql<=l && r<=qr){
mark(x,info(L(l)-L(ql)+1,R(r)-L(ql)+1,a,b));
return;
}
if (F[x].a!=-1){
mark(ls[x],info(F[x].l,F[x].l+R(mid)-L(l),F[x].a,F[x].b));
mark(rs[x],info(F[x].l+L(mid+1)-L(l),F[x].r,F[x].a,F[x].b));
F[x].a=-1;
}
if (ql<=mid) modify(ls[x],l,mid,a,b,ql,qr);
if (qr>mid) modify(rs[x],mid+1,r,a,b,ql,qr);
sum[x]=sum[ls[x]]+sum[rs[x]];
}inline ll query(int &x,int l,int r,int ql,int qr){
if (!x) return 0;
int mid=(l+r)>>1;
if (ql<=l && r<=qr)
return sum[x];
if (F[x].a!=-1){
mark(ls[x],info(F[x].l,F[x].l+R(mid)-L(l),F[x].a,F[x].b));
mark(rs[x],info(F[x].l+L(mid+1)-L(l),F[x].r,F[x].a,F[x].b));
F[x].a=-1;
}
ll ret=0;
if (ql<=mid) ret+=query(ls[x],l,mid,ql,qr);
if (qr>mid) ret+=query(rs[x],mid+1,r,ql,qr);
return ret;
}const int maxn=1000000000;
int n,rt;
struct event{
int t,l,r,a,b;
}eve[N];
int main(){
int Q;
int order,l,r,a,b;
freopen("t.in","r",stdin);
freopen("t.out","w",stdout);
read(n);
read(Q);
sx[++icnt]=n+1;
for (int i=1;
i<=Q;
i++){
read(eve[i].t);
read(eve[i].l);
read(eve[i].r);
sx[++icnt]=eve[i].l;
sx[++icnt]=eve[i].r+1;
if (eve[i].t==1)
read(eve[i].a),read(eve[i].b),eve[i].a%=eve[i].b;
}
sort(sx+1,sx+icnt+1);
icnt=unique(sx+1,sx+icnt+1)-sx-1;
for (int i=1;
i<=Q;
i++){
l=lower_bound(sx+1,sx+icnt+1,eve[i].l)-sx;
r=upper_bound(sx+1,sx+icnt+1,eve[i].r)-sx-1;
if (eve[i].t==1)
modify(rt,1,icnt,eve[i].a,eve[i].b,l,r);
else
printf("%lld\n",query(rt,1,icnt,l,r));
}
return 0;
}
推荐阅读
- 牛客 C. 子段乘积（线段树）
- 牛客挑战赛39 C 牛牛的等差数列（线段树）（*）
- 牛客 数据结构（区间修改+求区间元素平方和）
- 校门外的树 线段树版
- 树链剖分|牛客练习赛51 F-ABCBA（树链剖分，线段树，状态转移）
- 数论|bzoj 1938 - 类欧几里得+线段树
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 并查集|[CF938G] Shortest Path Queries
- 牛客网 练习赛25 B最长区间