题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
typedef long long LL;
const LL INF=0x3f3f3f3f3f3f3f3f;
struct Node
{
int l,r;
LL mul;
}tr[N*4];
LL Q,M;
LL a[N];
void pushup(Node&u,Node&l,Node&r)
{
u.mul=l.mul*r.mul%M;
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u]={l,r,1};
return;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int k,LL val)
{
if(tr[u].l==k&&tr[u].r==k)
{
tr[u].mul=val;
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(k<=mid)modify(u<<1,k,val);
if(k>=mid+1)modify(u<<1|1,k,val);
pushup(u);
}
Node query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)return tr[u];
int mid=tr[u].l+tr[u].r>>1;
if(l>mid)return query(u<<1|1,l,r);
if(r<mid+1)return query(u<<1,l,r);
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
Node res;
pushup(res,left,right);
return res;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
#endif
int T;
cin>>T;
while(T--)
{
memset(a,0,sizeof a),memset(tr,0,sizeof tr);
cin>>Q>>M;
build(1,1,Q);
int small=1;
for(int i=1;i<=Q;i++)
{
int op;
LL x;
scanf("%d%lld",&op,&x);
if(op==1)
{
modify(1,small++,x);
a[i]=small-1;
Node q=query(1,1,small-1);
printf("%lld\n",q.mul%M);
}
else
{
int k=a[x];
modify(1,k,1);
Node q=query(1,1,small);
printf("%lld\n",q.mul%M);
}
}
}
return 0;
}