luoguP 4588[TJOI 2018]数学計算

1462 ワード

に言及


1つの操作が一定時間のクエリに影響を及ぼすことを考慮して、セグメントツリー上のこの時間をこの数のタグに乗算し、最後にdfs全体のセグメントツリーを作成します.
code:
#include
using namespace std;
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
const int maxn=100010;
int T,n,mod;
int a[maxn],ans[maxn],mul[maxn<<2];
void build(int p,int l,int r)
{
    mul[p]=1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(ls(p),l,mid);build(rs(p),mid+1,r);
}
void change(int p,int l,int r,int ql,int qr,int k)
{
    if(l>=ql&&r<=qr){mul[p]=mul[p]*k%mod;return;}
    int mid=(l+r)>>1;
    if(ql<=mid)change(ls(p),l,mid,ql,qr,k);
    if(qr>mid)change(rs(p),mid+1,r,ql,qr,k);
}
void getquery(int p,int l,int r,int sum)
{
    sum=sum*mul[p]%mod;
    if(l==r){ans[l]=sum;return;}
    int mid=(l+r)>>1;
    getquery(ls(p),l,mid,sum);getquery(rs(p),mid+1,r,sum);
}
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        memset(a,0,sizeof(a));
        scanf("%lld%lld",&n,&mod);
        build(1,1,n);
        for(int i=1;i<=n;i++)
        {
            int op,x;scanf("%lld%lld",&op,&x);
            if(op==1)a[i]=x;
            else change(1,1,n,x,i-1,a[x]),a[x]=0;
        }
        for(int i=1;i<=n;i++)if(a[i])change(1,1,n,i,n,a[i]);
        getquery(1,1,n,1);
        for(int i=1;i<=n;i++)printf("%lld
",ans[i]); } return 0; }