[Tjoi2018]数学计算

BZOJ
luogu
线段树分治
是不是想问为什么不暴力做?
模数没说是质数,所以不一定有逆元.
然后就是要每次build一下把线段树权值init成1,
博猪不知道为什么for就WA,build就过了(用RE自动机查了下,发现还是有0...)

for(int i=1;i<=(_<<1);i++)s[i]=1;

有知道的一定在评论告诉我
其他的就是线段树分治的板子了罢
到写这篇blog的时候博猪还是luogu跑得最快的,BZOJrk12嘻嘻

#define ls x<<1,l,mid
#define rs x<<1|1,mid+1,r
#include<bits/stdc++.h>
using namespace std;
const int _=1e5+5;
int re(){
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int t,p,q;
int val[_],ed[_],s[_<<2];
void mul(int&x,int y){x=1ll*x*y%p;}
void bu(int x,int l,int r){
    s[x]=1;if(l==r)return;int mid=(l+r)>>1;bu(ls);bu(rs);
}
void upd(int x,int l,int r,int ql,int qr,int v){
    if(ql<=l&&r<=qr){mul(s[x],v);return;}int mid=(l+r)>>1;
    if(ql<=mid)upd(ls,ql,qr,v);if(qr>mid)upd(rs,ql,qr,v);
}
void solve(int x,int l,int r,int v){
    mul(v,s[x]);if(l==r){printf("%d\n",v);return;}
    int mid=(l+r)>>1;solve(ls,v);solve(rs,v);
}
int main(){
    t=re();
    while(t--){
        memset(ed,0,sizeof(ed));
        q=re(),p=re();
        for(int i=1;i<=q;i++){
            int op=re(),v=re();
            if(op==1)ed[i]=q,val[i]=v;
            else ed[v]=i-1;
        }
        bu(1,1,q);
        for(int i=1;i<=q;i++)if(ed[i])upd(1,1,q,i,ed[i],val[i]);
        solve(1,1,q,1);
    }
    return 0;
}

[Tjoi2018]数学计算

原文：https://www.cnblogs.com/sdzwyq/p/9866707.html