【类欧几里得】aladin

题目描述:

给你 $n$ 个盒子，有 $q$ 个操作，操作有两种：
第一种操作输入格式为 $1LRAB$，表示将编号为 $L$ 到 $R$ 的盒子里的石头数量变为 $(X?L+1)\times A?\mathrm{m}\mathrm{o}\mathrm{d}?B$，其中 $X$ 为盒子的编号。
第二种操作输入格式为 $2LR$，表示查询编号为 $L$ 到 $R$ 的盒子里的石头总数。

等差数列修改只需要记录$A$，$B$和开始位置即可，主要是单点取模比较恶心，于是把取模化为减法，即${\sum }_{i=l-L}^{r-L}i\times A-\lfloor \frac{i\times A}{B}\rfloor \times B$。前半部分可以直接等差数列求和，将后半的$B$提出后只需要计算${\sum }_{i=l-L}^{r-L}\lfloor \frac{i\times A}{B}\rfloor$。可以用前缀和转化，所以只需要能实现快速计算${\sum }_{i=0}^n\lfloor \frac{i\times A}{B}\rfloor$即可。
这时就需要类欧几里得算法了，类欧几里得算法可以在$O(logn)$计算出形如${\sum }_{i=0}^n\lfloor \frac{A\times i+B}{C}\rfloor$的式子。对于$B=0$的情况有一种显然的几何证明法。图源

对于${\sum }_{i=0}^n\lfloor \frac{i\times A}{B}\rfloor$，当$A>B$时，记$A=B\times \lfloor \frac{A}{B}\rfloor +A\mathrm{m}\mathrm{o}\mathrm{d}B$。则原式化为${\sum }_{i=0}^n\lfloor \frac{i\times (B\times \lfloor \frac{A}{B}\rfloor +A\mathrm{m}\mathrm{o}\mathrm{d}B)}{B}\rfloor$，提出前项得$$\sum _{i=0}^n\lfloor \frac{i\times A}{B}\rfloor =\lfloor \frac{B}{A}\rfloor \sum _{i=0}^{n}i+\sum _{i=0}^n\frac{(A\mathrm{m}\mathrm{o}\mathrm{d}B)\times i}{B}\text{if }A>B$$，前项可通过等差求和快速算出，后项则转化为了$A<B$的情况。

当$A<B$时，将${\sum }_{i=0}^n\lfloor \frac{i\times A}{B}\rfloor$放入坐标系中，其几何含义显然为$y=\frac{A}{B}x$与$x=n$围出的三角形内的整点个数（不计$x$轴）。记$m=\lfloor \frac{n\times A}{B}\rfloor$，则三角形内的整点可以转化为矩形$(n,m)$内的整点个数（不计$x$，$y$轴）减去红色三角形内的整点个数再加上斜线上的整点个数。矩形内很好算，$n\times m$即可。斜线上由于该斜线为$y=\frac{A}{B}x=\frac{\frac{A}{gcd(A,B)}}{\frac{B}{gcd(A,B)}}x$。所以在横坐标上每$\frac{B}{gcd(A,B)}$就有一个整点，所以斜线上一共有$\lfloor \frac{n\times gcd(A,B)}{B}\rfloor$个整点。最后是红色三角形，我们可以将其旋转至$x$轴上，可以发现它又变成一个三角形内整点问题，即为${\sum }_{i=1}^m\lfloor \frac{i\times B}{A}\rfloor$。则有$$\sum _{i=0}^n\lfloor \frac{i\times A}{B}\rfloor =n\times \lfloor \frac{n\times A}{B}\rfloor +\lfloor \frac{n\times gcd(A,B)}{B}\rfloor -\sum _{i=1}^{\lfloor \frac{n\times A}{B}\rfloor }\lfloor \frac{i\times B}{A}\rfloor \text{if }A<B$$我们又将其转化为了$A>B$的情况，于是可以进行递归计算，直到$A\mathrm{m}\mathrm{o}\mathrm{d}B=0$。
可以发现过程十分类似求$gcd$的过程，这是其算法名称来源，也可以证明其复杂度为$O(logn)$。
解决了区间修改之后便是一道线段树的板题，离散化后直接开或动态开点都能过，这里就不多赘述。

#include<bits/stdc++.h>
#define ll long long
#define k1 (k<<1)
#define k2 (k<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int N=1e6+5;
int n,m,q[N],L[N],R[N];
int *disc[N],cnt,tot,last=-1; //离散化
ll A[N],B[N],val[N];
template<class T>
void Read(T &x)
{x=0;int f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar());for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';return;
}
bool cmp(int *a,int *b) {return *a<*b;}
ll gcd(ll x,ll y) {return y?gcd(y,x%y):x;}
ll sim_euclid(ll a,ll b,ll n) //类欧
{ll x=a/b;a%=b;ll sum=n*(n+1)/2*x;if(!a||!b) return sum;ll res=n/b,m=a*n/b;return sum+n*m-sim_euclid(b,a,m)+res;
}
ll calc(ll a,ll b,ll n)
{if(n<0) return 0;ll g=gcd(a,b);return n*(n+1)/2*a-b*sim_euclid(a/g,b/g,n);
}
class Segment_tree{ //维护离散后区间信息private:struct node{ll sum,a,b,p;}t[N];public:void Change(int k,int l,int r,ll a,ll b,int p){t[k].sum=calc(a,b,p+val[r]-val[l]-1)-calc(a,b,p-1);t[k].a=a;t[k].b=b;t[k].p=p;return;}void pushdown(int k,int l,int r){if(t[k].b){Change(k1,l,mid,t[k].a,t[k].b,t[k].p);Change(k2,mid,r,t[k].a,t[k].b,t[k].p+val[mid]-val[l]);t[k].a=t[k].b=t[k].p=0;}return;}void change(int k,int l,int r,int x,int y,ll a,ll b){if(x>=r||y<=l) return;if(x<=l&&y>=r) {Change(k,l,r,a,b,val[l]-val[x]+1);return;}pushdown(k,l,r);if(x<=mid) change(k1,l,mid,x,y,a,b);if(y>=mid) change(k2,mid,r,x,y,a,b);t[k].sum=t[k1].sum+t[k2].sum;return;}ll query(int k,int l,int r,int x,int y){if(x>=r||y<=l) return 0;if(x<=l&&y>=r) return t[k].sum;pushdown(k,l,r);ll res=0;if(x<=mid) res+=query(k1,l,mid,x,y);if(y>=mid) res+=query(k2,mid,r,x,y);return res;}
}t;
int main()
{Read(n);Read(m);for(int i=1;i<=m;i++){Read(q[i]);Read(L[i]);L[i]--;Read(R[i]);disc[++tot]=&L[i];disc[++tot]=&R[i];if(q[i]==1) Read(A[i]),Read(B[i]);}sort(disc+1,disc+tot+1,cmp);for(int i=1;i<=tot;i++){if(*disc[i]!=last) last=*disc[i],*disc[i]=++cnt,val[cnt]=last;else *disc[i]=cnt;}for(int i=1;i<=m;i++){if(q[i]==1) t.change(1,1,cnt,L[i],R[i],A[i],B[i]);else printf("%lld\n",t.query(1,1,cnt,L[i],R[i]));}return 0;
}

总结：
所以为啥09年的题16年类欧才被提出。。。