Problem E E 、 小 花梨 的數組
時間限制：1000ms 空間限制：512MB
Description
小花梨得到了一個長度為?的數組?，現在要對它進行三種操作：
? 1 ? ] ?
? 2 ? ? 對所有的? ∈ [?,?],?[?] = ?[?] / ????????(?[?])
? 3 ? 求?[?]的值
????????(?) = {
1 (? = 1)
?的最小素因子(? ≥ 2)
現在給出初始數組?，對其進行?次操作，對于第三種操作輸出結果。
Input
第一兩個正整數?,?，表示數組的長度以及操作次數(1 ≤ ?,? ≤ 100000)
第二行輸入?個正整數表示數組?(1 ≤ ? ? ≤ 1000000)
接下來?行表示?次操作，每行輸入格式為"1 ? ?"或者"2 ? ?"，或者"3 ?"，對應上述三種操作。
1 ≤ ?,?,? ≤ ?,? ≤ ?
Output
對于第三種操作輸出答案即可，答案對10 9 + 7進行取模。
Example
Sample Input Sample Output
5 8
1 2 3 4 5
1 2 4
3 2
3 3
2 2 5
3 2
3 5
1 5 5
3 5
4
9
2
1
1

題意：

思路：

讀入的時候用唯一分解定理將a[i]分解為每一個質因子放入一個堆中。

我們知道一個數乘以它的最小的質因子后，它的最小的質因子不會改變。

如果先乘后除以它的最小的質因子，那么就是除以抵消一次乘法。那么我們可以標記一個數當前需要操作1多少次laze1，而不去實際更新數值，那么如果需要操作2的時候，laze1>0,那么影響只是laze1--，否則就是 需要執行的操作2次數laze2++.

我們用線段樹來處理區間操作的問題，

那么我們再來分析一下單點詢問是，該如何得到答案，我們知道，如果一個點的laze2有數值，laze2也有數值，那么這些除法操作一定在乘法操作之前，至于為什么，看上面laze變化的講解。所以我們可以先暴力除掉需要除掉的數，當數值等于1的時候停止。（因為沒有意義，又因為唯一分解定理可以知道一個小于等于1e6的數最多被除以十幾次而已），除以之后得到的剩余數值a[i] *它的最小質因子的laze1次冪就是當前的a[i]數值。

線段樹的pushdown 同樣根據上面的性質和優先級進行處理。

細節見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int *p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ // const int maxn = 1e7+50; bool noprime[maxn + 50]; vector <int> p; int getPrime() {// 華麗的初始化memset(noprime, false, sizeof(noprime));p.clear();int m = (int)sqrt(maxn + 0.5);// 優化的埃篩for (int i = 2; i <= m; i++) {if (!noprime[i]) {for (int j = i * i; j <= maxn; j += i) {noprime[j] = true;}}}// 把素數加到vector里for (int i = 2; i <= maxn; i++) {if (!noprime[i]) {p.push_back(i);}}//返回vector的大小return p.size();} ll pf[105][2];// 0 -> value 1->count const int N = 1e5 + 10; priority_queue<int, vector<int>, greater<int> > q[N]; const ll mod = 1e9 + 7;void getPrifac( ll n, int len, int id) {int pos = 0;for (int i = 0; 1ll * p[i]*p[i] <= n && i < len; i++) {if ( n % p[i] == 0) {// 算質因數的冪數while (n % p[i] == 0) {q[id].push(p[i]);n /= p[i];}// q[id].push(temp);}}if ( n > 1) {// pf[++pos][0] = n;// pf[pos][1]=1;q[id].push((n));}// return pos; // 優美的返回有多少個質因數// 1~pos } int n; ll a[N]; struct node {int l, r;int laze1;int laze2; } segment_tree[N << 2];void build(int rt, int l, int r) {segment_tree[rt].l = l;segment_tree[rt].r = r;segment_tree[rt].laze2 = 0;segment_tree[rt].laze1 = 0;if (l == r) {return ;}int mid = (l + r) >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r); } void pushdown(int rt) {int x = min(segment_tree[rt].laze2, segment_tree[rt << 1].laze1);segment_tree[rt << 1].laze1 -= x;segment_tree[rt << 1].laze2 += segment_tree[rt].laze2 - x;segment_tree[rt << 1].laze1 += segment_tree[rt].laze1;x = min(segment_tree[rt].laze2, segment_tree[rt << 1 | 1].laze1);segment_tree[rt << 1 | 1].laze1 -= x;segment_tree[rt << 1 | 1].laze2 += segment_tree[rt].laze2 - x;segment_tree[rt << 1 | 1].laze1 += segment_tree[rt].laze1;segment_tree[rt].laze1 = segment_tree[rt].laze2 = 0;} void update1(int rt, int l, int r) {if (segment_tree[rt].l >= l && segment_tree[rt].r <= r) {segment_tree[rt].laze1++;} else {pushdown(rt);int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;if (l <= mid) {update1(rt << 1, l, r);}if (r > mid) {update1(rt << 1 | 1, l, r);}} } void update2(int rt, int l, int r) {if (segment_tree[rt].l >= l && segment_tree[rt].r <= r) {if (segment_tree[rt].laze1) {segment_tree[rt].laze1--;} else {segment_tree[rt].laze2++;}} else {pushdown(rt);int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;if (l <= mid) {update2(rt << 1, l, r);}if (r > mid) {update2(rt << 1 | 1, l, r);}} }ll ask(int rt, int id) {if (segment_tree[rt].l == segment_tree[rt].r && segment_tree[rt].r == id) {while (segment_tree[rt].laze2 && a[id] > 1 && q[id].size()) {segment_tree[rt].laze2--;a[id] /= q[id].top();q[id].pop();}ll x = 1ll;if (q[id].size()) {x = q[id].top();}return (powmod(x, segment_tree[rt].laze1, mod) * a[id]) % mod;} else {pushdown(rt);int mid = (segment_tree[rt].r + segment_tree[rt].l) >> 1;if (id <= mid) {return ask(rt << 1, id);} else {return ask(rt << 1 | 1, id);}} } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);int m;int len = getPrime();scanf("%d %d", &n, &m);repd(i, 1, n) {scanf("%lld", &a[i]);getPrifac(a[i], len, i);}build(1, 1, n);int op;while (m--) {scanf("%d", &op);if (op == 1) {int l, r;scanf("%d %d", &l, &r);update1(1, l, r);} else if (op == 2) {int l, r;scanf("%d %d", &l, &r);update2(1, l, r);} else {int x;scanf("%d", &x);printf("%lld\n", ask(1, x) );}}return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11469651.html

總結

以上是生活随笔為你收集整理的美登杯”上海市高校大学生程序设计邀请赛 Problem E 、 小 花梨 的数组 （线段树）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。