luoguP4588 [TJOI2018]数学计算

题意

考虑一个操作会对一段时间内的询问产生影响，于是将线段树上的这段时间打上乘这个数的标记，最后dfs整颗线段树。

code:

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define ls(p) (p<<1)

#define rs(p) (p<<1|1)

const int maxn=100010;

int T,n,mod;

int a[maxn],ans[maxn],mul[maxn<<2];

void build(int p,int l,int r)

{

	mul[p]=1;

	if(l==r)return;

	int mid=(l+r)>>1;

	build(ls(p),l,mid);build(rs(p),mid+1,r);

}

void change(int p,int l,int r,int ql,int qr,int k)

{

	if(l>=ql&&r<=qr){mul[p]=mul[p]*k%mod;return;}

	int mid=(l+r)>>1;

	if(ql<=mid)change(ls(p),l,mid,ql,qr,k);

	if(qr>mid)change(rs(p),mid+1,r,ql,qr,k);

}

void getquery(int p,int l,int r,int sum)

{

	sum=sum*mul[p]%mod;

	if(l==r){ans[l]=sum;return;}

	int mid=(l+r)>>1;

	getquery(ls(p),l,mid,sum);getquery(rs(p),mid+1,r,sum);

}

signed main()

{

	scanf("%lld",&T);

	while(T--)

	{

		memset(a,0,sizeof(a));

		scanf("%lld%lld",&n,&mod);

		build(1,1,n);

		for(int i=1;i<=n;i++)

		{

			int op,x;scanf("%lld%lld",&op,&x);

			if(op==1)a[i]=x;

			else change(1,1,n,x,i-1,a[x]),a[x]=0;

		}

		for(int i=1;i<=n;i++)if(a[i])change(1,1,n,i,n,a[i]);

		getquery(1,1,n,1);

		for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);

	}

	return 0;

}

巴特西

luoguP4588 [TJOI2018]数学计算

题意

最新文章

热门文章