[Tjoi2018]数学计算

BZOJ

luogu

线段树分治

是不是想问为什么不暴力做?

模数没说是质数,所以不一定有逆元.

然后就是要每次build一下把线段树权值init成1,

博猪不知道为什么for就WA,build就过了(用RE自动机查了下,发现还是有0...)

for(int i=1;i<=(_<<1);i++)s[i]=1;

有知道的一定在评论告诉我

其他的就是线段树分治的板子了罢

到写这篇blog的时候博猪还是luogu跑得最快的,BZOJrk12嘻嘻

#define ls x<<1,l,mid

#define rs x<<1|1,mid+1,r

#include<bits/stdc++.h>

using namespace std;

const int _=1e5+5;

int re(){

	int x=0,w=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*w;

}

int t,p,q;

int val[_],ed[_],s[_<<2];

void mul(int&x,int y){x=1ll*x*y%p;}

void bu(int x,int l,int r){

	s[x]=1;if(l==r)return;int mid=(l+r)>>1;bu(ls);bu(rs);

}

void upd(int x,int l,int r,int ql,int qr,int v){

	if(ql<=l&&r<=qr){mul(s[x],v);return;}int mid=(l+r)>>1;

	if(ql<=mid)upd(ls,ql,qr,v);if(qr>mid)upd(rs,ql,qr,v);

}

void solve(int x,int l,int r,int v){

	mul(v,s[x]);if(l==r){printf("%d\n",v);return;}

	int mid=(l+r)>>1;solve(ls,v);solve(rs,v);

}

int main(){

	t=re();

	while(t--){

		memset(ed,0,sizeof(ed));

		q=re(),p=re();

		for(int i=1;i<=q;i++){

			int op=re(),v=re();

			if(op==1)ed[i]=q,val[i]=v;

			else ed[v]=i-1;

		}

		bu(1,1,q);

		for(int i=1;i<=q;i++)if(ed[i])upd(1,1,q,i,ed[i],val[i]);

		solve(1,1,q,1);

	}

	return 0;

}