Description
小豆现在有一个数 \(x\)，初始值为 \(1\). 小豆有 \(Q\) 次操作，操作有两种类型: 1 \(m\): \(x = x \times m\) ，输出 \(x\)%\(mod\); 2 \(pos\) : \(x = x /\) 第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 \(1\)，对于每一个类型 \(1\) 的操作至多会被除一次），输出 \(x\)%\(mod\)
一共有 \(t\) 组输入（ \(t \leq 5\)） 对于每一组输入，第一行是两个数字 \(Q\), \(mod\) \((Q \leq 100000, mod \leq 1000000000)\); 接下来 \(Q\) 行，每一行为操作类型 \(op\)，操作编号或所乘的数字 \(m\)（保证所有的输入都是合法的）.\(1 \leq Q \leq 100000\)
Output
对于每一个操作，输出一行，包含操作执行后的 \(x\) % \(mod\) 的值
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
题解
这并不是一道数学题。。。\(mod\) 不一定是质数所以除掉的数不一定有逆元……
努力将自己思维打开 注意到“每个数至多被删掉一次”，那相当于每个数只对一段区间里的答案有贡献 处理一下每个数被删除的时间 用线段树维护所有答案，进行区间修改（乘一个数）或单点查询。
我的小伙伴们想到了在线做法 线段树维护当前答案，即每个数对当前答案是否有贡献 操作1相当于单点修改，询问相当于区间 \([1,n]\) 求乘积。
我感觉下面这种方法更好想啊，也更好实现，可为啥我想了很久却想到上面那个奇怪方法啊【捂脸】 区别大概是离线与在线 我本以为此题不能在线，往离线方向想，就要考虑后面的所有答案 而往在线方向想，关注的就仅是当前答案。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005;
typedef long long ll;
int P;
struct data{ int op,x; }d[N];
int c[N];
struct tree{
int v;
tree *ch[2];
}pool[N*2],*root;
int cnt;
void build(tree *p,int l,int r){
p->v=1;
if(l==r) return;
int mid=(l+r)>>1;
build(p->ch[0]=&pool[++cnt],l,mid);
build(p->ch[1]=&pool[++cnt],mid+1,r);
}
void pushdown(tree *p){
p->ch[0]->v=((ll)p->ch[0]->v*p->v)%P;
p->ch[1]->v=((ll)p->ch[1]->v*p->v)%P;
p->v=1;
}
void change(tree *p,int l,int r,int L,int R,int c){
if(l==L && r==R) { p->v=((ll)p->v*c)%P; return; }
pushdown(p);
int mid=(l+r)>>1;
if(R<=mid) change(p->ch[0],l,mid,L,R,c);
else if(L>mid) change(p->ch[1],mid+1,r,L,R,c);
else {
change(p->ch[0],l,mid,L,mid,c);
change(p->ch[1],mid+1,r,mid+1,R,c);
}
}
int query(tree *p,int l,int r,int c){
if(l==r) return p->v;
pushdown(p);
int mid=(l+r)>>1;
if(c<=mid) return query(p->ch[0],l,mid,c);
return query(p->ch[1],mid+1,r,c);
}
int main()
{
int T,Q;
scanf("%d",&T);
root=&pool[++cnt];
while(T--){
scanf("%d%d",&Q,&P);
for(int i=1;i<=Q;i++){
scanf("%d%d",&d[i].op,&d[i].x);
if(d[i].op==2) c[d[i].x]=i;
}
build(root,1,Q);
for(int i=1;i<=Q;i++){
if(d[i].op==2) printf("%d\n",query(root,1,Q,i));
else {
change(root,1,Q,i,c[i]==0 ? Q : c[i]-1,d[i].x);
printf("%d\n",query(root,1,Q,i));
}
}
//clear
for(int i=1;i<=Q;i++) c[i]=0; cnt=1;
}
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/10017799.html
相关资源：数据结构—成绩单生成器
