http://acm.hdu.edu.cn/showproblem.php?pid=5475
Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 755 Accepted Submission(s):
431
Problem Description
#include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<algorithm> #define Lson root<<1, L, tree[root].Mid() #define Rson root<<1|1, tree[root].Mid() + 1, R const int N = 500010; typedef long long ll; struct Tree { ll L, R; ll sum; int Mid() { return (L + R) / 2; } } tree[N * 4]; ll a[N], m; void Push(int root) { tree[root].sum = (tree[root<<1].sum * tree[root<<1|1].sum) % m; }//维护区间乘积 void Build(int root, ll L, ll R) { tree[root].L = L, tree[root].R = R; if(L == R) { tree[root].sum = 1; return ; } Build(Lson); Build(Rson); Push(root); }//建树 void Update(int root, ll op, ll e) { if(tree[root].L == op && tree[root].R == op) { tree[root].sum = e % m; return ; } if(op <= tree[root].Mid()) Update(root<<1, op, e); else Update(root<<1|1, op, e); Push(root); }//区间单点更新 int main() { int t, q, op, x = 0; scanf("%d", &t); while(t--) { x++; scanf("%d%lld", &q, &m); printf("Case #%d:\n", x); Build(1, 1, q); for(int i = 1 ; i <= q ; i++) { scanf("%d%lld", &op, &a[i]); if(op == 1) Update(1, i, a[i]); else Update(1, a[i], 1); printf("%lld\n", tree[1].sum); } } return 0; }
#include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<algorithm> #define Lson root<<1, L, tree[root].Mid() #define Rson root<<1|1, tree[root].Mid() + 1, R const int N = 500010; typedef long long ll; ll a[N], m; int main() { int t, op, q, x = 0; scanf("%d", &t); while(t--) { x++; ll ans = 1; scanf("%d%lld", &q, &m); printf("Case #%d:\n", x); for(int i = 1 ; i <= q ; i++) { scanf("%d%lld", &op, &a[i]); if(op == 1) ans = ans * a[i] % m; else { a[a[i]] = 1; a[i] = 1; ans = 1; for(int j = 1 ; j < i ; j++) ans = ans * a[j] % m; } printf("%lld\n", ans); } } return 0; }
hdu 5475 An easy problem（暴力 || 线段树区间单点更新）
原文：http://www.cnblogs.com/qq2424260747/p/4854669.html