Topic link: Click to view

Main idea: Given n n n operations and one m, each operation is modeled after each operation. Each operation is divided into two kinds. The current number of initialization is 1:

1. 1 x: The output of the current number multiplied by X
2. 2x: The output of the current number divided by the number of operations x

Topic analysis: for this question, the first reaction is simulation, and WA is the fruit of it. Later, why do we think about WA? The reason is that the division can not be calculated separately. That is to say, although multiplication can be distributed to take modules, but division can not be done, so there is no way to simulate at all. If we have multiplied the number before, then we can't convert it into the number not multiplied before and then quadrature, so that we can get the normal modulus operation.

This idea is really coincident, but I did not think it out by myself. First, the line segment tree is initialized to 1. Each operation maintains the line segment tree. If operation 1, the number of current positions is changed to x. If operation 2, the number of x positions is changed to 1. Then the sum of intervals is calculated with query function every time. The interval is from 1 to the current position. See the code for details:

#include<iostream>
#include<cstdio> 
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<cmath>
using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const int N=1e5+100;

int mod;

struct Node
{
	int l,r;
	LL sum;
}tree[N<<2];

void build(int k,int l,int r)
{
	tree[k].l=l;
	tree[k].r=r;
	tree[k].sum=1;
	if(l==r)
	{
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}

void update(int k,int pos,int val)
{
	if(tree[k].l==tree[k].r)
	{
		tree[k].sum=val;
		return;
	}
	int mid=(tree[k].l+tree[k].r)>>1;
	if(mid>=pos)
		update(k<<1,pos,val);
	else
		update(k<<1|1,pos,val);
	tree[k].sum=tree[k<<1].sum*tree[k<<1|1].sum%mod;
}

LL query(int k,int l,int r)
{
	if(tree[k].l>r||tree[k].r<l)
		return 1;//Notice here, because it's a multiplication, it doesn't qualify to return 1 instead of 0.
	if(tree[k].l>=l&&tree[k].r<=r)
		return tree[k].sum;
	return (query(k<<1,l,r)*query(k<<1|1,l,r))%mod;
}

int main()
{
//	freopen("input.txt","r",stdin);
	int w;
	cin>>w;
	int kase=0;
	while(w--)
	{
		int n;
		printf("Case #%d:\n",++kase);
		scanf("%d%d",&n,&mod);
		build(1,1,n);
		for(int i=1;i<=n;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(a==1)
			{
				update(1,i,b);
				printf("%lld\n",query(1,1,i));
			}
			else
			{
				update(1,b,1);
				printf("%lld\n",query(1,1,i));
			}
		}
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}