c/c++语言开发共享洛谷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; }