洛谷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;
}