Description
小豆现在有一个数 x ，初始值为 1 。 小豆有 Q 次操作，操作有两种类型:
1 m： x=x*m ，输出 x mod M ；
2 pos： x=x/ 第 pos 次操作所乘的数（保证第 pos 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），输出 x mod M 。
Input
一共有 t 组输入。
对于每一组输入，第一行是两个数字 Q,M 。
接下来 Q 行，每一行为操作类型 op ，操作编号或所乘的数字 m （保证所有的输入都是合法的）。
Output
对于每一个操作，输出一行，包含操作执行后的 x mod M 的值
Sample Input
1
10 1000000000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7
Sample Output
2
1
2
20
10
1
6
42
504
84
wtcl
“首先mod不是质数，所以不能求逆元。”
因为忘了这句话而导致花了一小时思考为什么不能暴力。。。
- 注意到有加入操作和删除操作，一个很典型的想法就是线段树分治。
- 线段树分治：具有插入删除操作的信息影响的都是一个个时间区间,可以使用线段树来记录其覆盖的影响区间,并在其上通过标记的方式进行记录。
代码
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int maxn=100003;
int q,mod;
struct node{int l,r,mul;}a[maxn<<2];
struct node2{int lef,rig,val;}keep[maxn];
void build(int x,int left,int right)
{
a[x].l=left,a[x].r=right,a[x].mul=1;
if(left==right) return;
int mid=left+right>>1;
build(x<<1,left,mid),build(x<<1|1,mid+1,right);
}
void add(int x,int left,int right,int d)
{
if(a[x].r<left||a[x].l>right) return;
if(left<=a[x].l&&right>=a[x].r) return a[x].mul=a[x].mul*d%mod,void();
add(x<<1,left,right,d),add(x<<1|1,left,right,d);
}
void dfs(int x)
{
if(a[x].l==a[x].r) return cout<<a[x].mul<<'
',void();
a[x<<1].mul=a[x<<1].mul*a[x].mul%mod,dfs(x<<1);
a[x<<1|1].mul=a[x<<1|1].mul*a[x].mul%mod,dfs(x<<1|1);
}
signed main()
{
freopen("tmp.in","r",stdin);
int T; scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&q,&mod);
for(int i=1,opt,x;i<=q;++i)
{
keep[i]=(node2){0,0,0};
scanf("%lld%lld",&opt,&x);
if(opt==1) keep[i]=(node2){i,0,x};
else keep[x].rig=i;
}
build(1,1,q);
for(int i=1;i<=q;++i)
{
if(!keep[i].lef) continue;
if(!keep[i].rig) add(1,keep[i].lef,q,keep[i].val);
else add(1,keep[i].lef,keep[i].rig-1,keep[i].val);
}
dfs(1);
}
return 0;
}