锐客网

  1. 首页 > it技术 > >

线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN

线段树

直接在线段树上区间覆盖咯
怎么求和？

∑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; }

    推荐阅读


    上一篇：Android|BigImageViewer

    下一篇：[数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends