bzoj 5334 [Tjoi2018]数学计算
Link
Solution
直接上线段树
相当于单点修改,只查询区间 ((1,n)) 的积
Code
// Copyright lzt
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<long long, long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i, j, k) for (register int i = (int)(j); i <= (int)(k); i++)
#define rrep(i, j, k) for (register int i = (int)(j); i >= (int)(k); i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = 10 * x + ch - '0';
ch = getchar();
}
return x * f;
}
#define lc (i << 1)
#define rc (i << 1 | 1)
const int maxn = 100100;
int tc, q, m;
struct Node {
int l, r, val;
} tr[maxn << 2];
void build(int i, int l, int r) {
tr[i].l = l; tr[i].r = r; tr[i].val = 1;
if (l == r) return;
int md = (l + r) >> 1;
build(lc, l, md); build(rc, md + 1, r);
}
void upd(int i, int p, int v) {
if (tr[i].l == tr[i].r) {
tr[i].val = v;
return;
}
int md = (tr[i].l + tr[i].r) >> 1;
if (p <= md) upd(lc, p, v); else upd(rc, p, v);
tr[i].val = tr[lc].val * 1ll * tr[rc].val % m;
}
void work() {
tc = read();
build(1, 1, 100000);
while (tc--) {
q = read(), m = read();
rep(i, 1, q) {
int op = read(), x = read();
if (op == 1) {
upd(1, i, x);
}
else if (op == 2) {
upd(1, x, 1);
}
printf("%d
", tr[1].val);
}
rep(i, 1, 100000) upd(1, i, 1);
}
}
int main() {
#ifdef LZT
freopen("in", "r", stdin);
#endif
work();
#ifdef LZT
Debug("My Time: %.3lfms
", (double)clock() / CLOCKS_PER_SEC);
#endif
}