HDU5475 – An easy problem(线段树)

HDU5475

【题意】n个操作(op,x);op == 1时乘上x，op==2时除以输入的第x个操作的x，保证第x都是操作1且每个2中的x不重复。求每次操作之后的值对M取余。

【分析】一直想着乘法逆元，还去找怎么求非素数的逆元可惜有些数不存在逆元，还试过大数计算，然后最大值太大可能是，足以让任何大数乘法算法TLE，然后就被智商碾压了，再也回不过来了。其实超级简单，用一颗线段树维护1~n个操作的值的乘积，而保证了第x都是操作1且每个2中的x不重复，使得每次除法就是在线段树中删掉第x[i]个数。

【AC CODE】1341ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1e5+10;
LL ret[MAXN<<1], val[MAXN],MOD;
int op[MAXN];

inline int id(int x, int y){return x+y|x!=y;}
void update(int x, int y, int p, int v)
{
	if(x == y)
	{
		ret[id(x,y)] = v;
		return;
	}
	int m = (x+y)>>1;
	if(p <= m) update(x,m,p,v);
	else update(m+1,y,p,v);
	ret[id(x,y)] = ret[id(x,m)]*ret[id(m+1,y)]%MOD;
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t,count = 0;
	scanf("%d", &t);
	while(t--)
	{
		int n;
		scanf("%d %I64d", &n, &MOD);
		repe(i,1,n*2) ret[i] = 1;
		printf("Case #%d:\n", ++count);
		repe(i,1,n)
		{
			scanf("%d%I64d", &op[i],&val[i]);
			if(1 == op[i])
				update(1,n,i,val[i]);
			else
				update(1,n,val[i],1);
			printf("%I64d\n", ret[id(1,n)]);
		}
	}
	return 0;
}