Problem

https://www.luogu.org/problemnew/show/P4433

Solution

https://www.luogu.org/blog/five20/solution-p4433

这里讲得挺清楚的。

顺便说一下代码实现，就是事先把 $A,B$ 的公因子提取出来，所以就一直会有 $gcd(A, B)=1$ 存在了。

然后因为考场上打的 ODT 就懒得去改线段树了。

// Code by ajcxsu
// Problem: aladin

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
typedef long long ll;
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') pl=ch=='-', ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

ll cac(ll n, ll a, ll b) {
    ll x=a/b; a%=b;
    ll sum=n*(n+1)/2*x;
    if(!a) return sum;
    ll m=a*n/b;
    return sum+n*m-cac(m, b, a)+n/b;
}
ll cac2(ll n, ll a, ll b) {
    if(n<1) return 0;
    ll g=__gcd(a, b);
    return n*(n+1)/2*a-b*cac(n, a/g, b/g);
}

struct Seg {
    int l, r;
    ll s, a, b;
    bool operator <(const Seg &b) const { return l<b.l; }
    bool operator ==(const Seg &b) const { return l==b.l; }
    ll cac() const {
        return cac2(s+r-l, a, b)-cac2(s-1, a, b);
    }
    Seg(int l=0, int r=0, ll s=0, ll a=0, ll b=0): 
        l(l), r(r), s(s), a(a), b(b) {}
} ;
ostream& operator << (ostream &out, Seg x) {
    return out;
}
set<Seg> s;

set<Seg>::iterator split(int pos) {
    set<Seg>::iterator it=s.lower_bound(pos);
    if(it!=s.end() && it->l==pos) return it;
    --it;
    if(pos>it->r) return s.end();
    Seg nd=*it;
    s.erase(it);
    s.insert(Seg(nd.l, pos-1, nd.s, nd.a, nd.b));
    return s.insert(Seg(pos, nd.r, nd.s+pos-nd.l, nd.a, nd.b)).first;
}

void assign(int l, int r, ll a, ll b) {
    split(l);
    set<Seg>::iterator itr=split(r+1), itl=split(l);
    s.erase(itl, itr);
    s.insert(Seg(l, r, 1, a, b));
}

ll query(int l, int r) {
    split(l);
    set<Seg>::iterator itr=split(r+1), itl=split(l);
    ll ans=0;
    for(;itl!=itr;itl++) ans+=itl->cac();    
    return ans;
}

int main() {
    #ifndef LOCAL
    freopen("aladin.in","r",stdin);
    freopen("aladin.out","w",stdout);
    #endif
    int n, m, a, b, c, d, e;
    gn(n), gn(m);
    s.insert(Seg(1, n, 1, 0, 1));
    while(m--) {
        gn(a), gn(b), gn(c);
        if(a==2) printf("%lld\n", query(b, c));
        else {
            gn(d), gn(e);
            assign(b, c, d, e);
        }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4433.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆