洛谷P4588 [TJOI2018]数学计算【线段树】

题目链接

题解

用线段树维护即可

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

#define ls (u << 1)

#define rs (u << 1 | 1)

using namespace std;

const int maxn = 100005,maxm = 100005,INF = 1000000000;

inline LL read(){

	LL out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int Q,P;

LL val[maxn << 2];

void build(int u,int l,int r){

	if (l == r){val[u] = 1; return;}

	int mid = l + r >> 1;

	build(ls,l,mid);

	build(rs,mid + 1,r);

	val[u] = 1ll * val[ls] * val[rs] % P;

}

void modify(int u,int l,int r,int pos,LL v){

	if (l == r){val[u] = v; return;}

	int mid = l + r >> 1;

	if (mid >= pos) modify(ls,l,mid,pos,v);

	else modify(rs,mid + 1,r,pos,v);

	val[u] = 1ll * val[ls] * val[rs] % P;

}

LL query(int u,int l,int r,int L,int R){

	if (l >= L && r <= R) return val[u];

	int mid = l + r >> 1;

	if (mid >= R) return query(ls,l,mid,L,R);

	if (mid < L) return query(rs,mid + 1,r,L,R);

	return 1ll * query(ls,l,mid,L,R) * query(rs,mid + 1,r,L,R) % P;

}

int main(){

	int T = read();

	while (T--){

		Q = read(); P = read(); LL opt,v;

		build(1,1,Q);

		REP(i,Q){

			opt = read(); v = read();

			if (opt & 1) modify(1,1,Q,i,v % P);

			else modify(1,1,Q,v,1);

			printf("%lld\n",query(1,1,Q,1,i));

		}

	}

	return 0;

}

巴特西

洛谷P4588 [TJOI2018]数学计算【线段树】

题目链接

题解

最新文章

热门文章

巴特西

洛谷P4588 [TJOI2018]数学计算 【线段树】

题目链接

题解

最新文章

热门文章

洛谷P4588 [TJOI2018]数学计算【线段树】