洛谷P3987 我永遠喜歡珂朵莉~(set 樹狀數組)

題意

題目鏈接

Sol

不會卡常，自愧不如。下麵的代碼只有66分。我實在懶得手寫平衡樹了。。

思路比較直觀：拿個set維護每個數出現的位置，再寫個線段樹維護區間和

#include<bits/stdc++.h>
#define LL long long 
const int MAXN = 5e5 + 10, INF = 1e9 + 7;
using namespace std;
template<typename A, typename B> inline bool chmax(A &x, B y) {
    if(y > x) {x = y; return 1;}
    else return 0;
}
template<typename A, typename B> inline bool chmin(A &x, B y) {
    if(y < x) {x = y; return 1;}
    else return 0;
}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, op[MAXN], ql[MAXN], qr[MAXN], val[MAXN];
LL a[MAXN];
bool ha[MAXN];
set<int> s[MAXN];
void gao(int pos,  int x) {
    for(int i = 1; i * i <= x; i++) {
        if(x % i == 0) {
            if(ha[i]) s[i].insert(pos);
            if(i != (x / i))
                if(ha[x / i]) s[x / i].insert(pos);
        }
    }
}
#define lb(x) (x & (-x))
LL T[MAXN];
void Add(int p, int v) {
    while(p <= N) T[p] += v, p += lb(p);
}
LL Sum(int x) {
    LL ans = 0;
    while(x) ans += T[x], x -= lb(x);
    return ans;
}
LL Query(int l, int r) {
    return Sum(r) - Sum(l - 1);
}
void Modify(int p, int v) {
    Add(p, -a[p]);
    Add(p, a[p] / v);
}

void Change(int l, int r, int x) {
    auto it = s[x].lower_bound(l);
    while(1) {
        int pos = *it;
        if(it == s[x].end() || pos > r) return ;
        if(a[pos] % x != 0) {it++; s[x].erase(prev(it)); continue;}
        else Modify(pos, x), a[pos] /= x;
        it++;
    }
}
int main() {
//  freopen("a.in", "r", stdin);
    N = read(); M = read();
    for(int i = 1; i <= N; i++) a[i] = read(), Add(i, a[i]);
    for(int i = 1; i <= M; i++) {
        op[i] = read(), ql[i] = read(); qr[i] = read();
        if(op[i] == 1) val[i] = read(), ha[val[i]] = 1;
    }
    for(int i = 1; i <= N; i++) gao(i, a[i]);
    for(int i = 1; i <= M; i++) {
        if(op[i] == 1) {
            if(val[i] != 1) Change(ql[i], qr[i], val[i]);
        } else cout << Query(ql[i], qr[i]) << '\n';
    }
    return 0;
}