题意
题目链接
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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605285.html