思路:针对一个数组的操作,即对一个区间。可以用线段树去进行维护。初始化建树,叶子节点的值为1,维护每段区间上各个元素的乘积sum。M yi,将第i个元素的值改为yi。N di,将第di个元素的值改为1。输出即查询区间[1,Q]的sum值。也就是变成了单点更新、区间查询问题。
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<set>
#include<iostream>
#define ll long long
#define lson p<<1
#define rson p<<1|1
using namespace std;
const int maxn=1e5+;
ll mod;
struct node
{
int l,r;
ll sum;
}t[maxn<<];
void pushup(int p)
{
t[p].sum=(t[lson].sum*t[rson].sum)%mod;
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)
{
t[p].sum=;
return ;
}
int mid=(l+r)>>;
build(lson,l,mid);
build(rson,mid+,r);
pushup(p);
}
void update(int p,int k,ll val)
{
if(t[p].l==t[p].r)
{
t[p].sum=val;
return ;
}
int mid=(t[p].l+t[p].r)>>;
if(k<=mid) update(lson,k,val);
else update(rson,k,val);
pushup(p);
}
int main()
{
int u;
ios::sync_with_stdio(false);
cin>>u;
while(u--)
{
int n,m;
cin>>n>>mod;
build(,,n);
for(int i=;i<=n;i++)
{
char s;
ll x;
cin>>s;
cin>>x;
if(s=='M')
update(,i,x);
else
update(,x,);
printf("%lld\n",t[].sum);
}
}}