小清新数据结构 WA on #8 求调 悬关

#include<bits/stdc++.h>
#define int __int128
using namespace std;
int n,m,q,x[300005],v[300005];
const int M=1000000000000000003LL;
struct node{
    int l,r,sum,fa,fm;
}t[1200005];
void read(int &x){
    long long y;cin>>y;x=y;
}
void write(int x){
    long long y=x;cout<<y<<"\n";
}
void build(int rt,int l,int r){
    t[rt].l=l,t[rt].r=r;t[rt].fm=1;if (l==r)return;
    int mid=(l+r)/2;build(rt*2,l,mid);build(rt*2+1,mid+1,r);
}
void pushup(int rt){t[rt].sum=t[rt*2].sum+t[rt*2+1].sum;}
void pushdown(int rt){
    if (t[rt].fm!=1){
        (t[rt*2].fm*=t[rt].fm)%=M,(t[rt*2+1].fm*=t[rt].fm)%=M;
        (t[rt*2].fa*=t[rt].fm)%=M,(t[rt*2+1].fa*=t[rt].fm)%=M;
        (t[rt*2].sum*=t[rt].fm)%=M,(t[rt*2+1].sum*=t[rt].fm)%=M;
        t[rt].fm=1;
    }
    if (t[rt].fa){
        (t[rt*2].fa+=t[rt].fa)%=M,(t[rt*2+1].fa+=t[rt].fa)%=M;
        (t[rt*2].sum+=t[rt].fa)%=M,(t[rt*2+1].sum+=t[rt].fa)%=M;
        t[rt].fa=0;
    }
}
int ksm(int a,int b){
    if (b==0)return 1;if (b&1)return ksm(a,b^1)*a%M;
    int k=ksm(a,b>>1);return k*k%M;
}
void add(int rt,int l,int r,int x){
    //if (rt==1){cout<<"add";
    //write(l);
    //write(r);
    //write(x);}
    if (t[rt].l>r||t[rt].r<l)return;
    if (t[rt].l>=l&&t[rt].r<=r){
        (t[rt].sum+=x)%=M;(t[rt].fa+=x)%=M;return;
    }
    pushdown(rt);add(rt*2,l,r,x);add(rt*2+1,l,r,x);pushup(rt);
}
void mul(int rt,int l,int r,int x){
    //if (rt==1){cout<<"mul";
    //write(l);
    //write(r);
    //write(x);}
    if (t[rt].l>r||t[rt].r<l)return;
    if (t[rt].l>=l&&t[rt].r<=r){
        (t[rt].sum*=x)%=M;(t[rt].fa*=x)%=M;(t[rt].fm*=x)%=M;return;
    }
    pushdown(rt);mul(rt*2,l,r,x);mul(rt*2+1,l,r,x);pushup(rt);
}
int sum(int rt,int l,int r){
    if (t[rt].l>r||t[rt].r<l)return 0;
    if (t[rt].l>=l&&t[rt].r<=r)return t[rt].sum;
    return (sum(rt*2,l,r)+sum(rt*2+1,l,r))%M;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    read(n),read(m),read(q);
    build(1,1,n);
    set<int> s;
    for (int i=1;i<=m;i++){
        read(x[i]);
        s.insert(x[i]);
    }
    for (int i=1;i<=m;i++){
        int V;
        read(V),v[x[i]]=V;
    }
    for (int i=2;i<n;i++){
        int r=*s.lower_bound(i);
        if (r!=i){
            int l=*(--s.lower_bound(i));
            add(1,i,i,v[l]*(r-i)%M);
        }
    }
    for (int i=1;i<=q;i++){
        int op,l,r;read(op),read(l),read(r);
        if (op==2){
            write(sum(1,l,r));
        }
        else{
            int q=*s.lower_bound(l),p=*(--s.lower_bound(l));
            if (p+1<=l-1)add(1,p+1,l-1,(q-l)*v[p]%M);
            if (l+1<=q-1){
                int x=r*ksm(v[p],M-2)%M;
                mul(1,l+1,q-1,x);
            }
            add(1,l,l,-sum(1,l,l));
        }
    }
    return 0;
}