Mancunian And Multiplicative Queries-Hackerearth

#include<bits/stdc++.h>
using namespace std;

#define pfi(a) printf("%d",a);
#define pfl(a) printf("%lld",a);
#define pfin(a) printf("%d\n",a);
#define pfln(a) printf("%lld\n",a);
#define pfis(a) printf("%d ",a);
#define pfls(a) printf("%lld ",a);
#define sfi(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define f(i,a,b) for(int i=a;i<b;i++)
#define pb(a) push_back(a);
#define mp(a,b) make_pair(a,b)
#define ll long long

const ll mod=1e9+7;
const int N=50004;

int BLOCK;
ll arr[N],func[N];
int freq[1000006]={0};

ll prod,ans;

struct util
{
    int l,r;
};

ll me(ll a, ll n)
{
    ll res=1;
    while(n>0)
    {
        if(n&1) res=(res*a)%mod;
        a=(a*a)%mod;
        n/=2;
    }
    return res;
}

ll mi(ll a){
    return me(a, mod-2);
}

bool cmp(util a,util b)
{
    int val1=a.l/BLOCK;
    int val2=b.l/BLOCK;

    if(val1!=val2)
        return val1<val2;

    if(val1%2==1)
        return a.r<b.r;

    return b.r>a.r;
}

void add(int idx)
{
    prod=(prod*mi(func[freq[arr[idx]]]))%mod;
    freq[arr[idx]]++;
    prod=(prod*func[freq[arr[idx]]])%mod;
}

void remove(int idx)
{
    prod=(prod*mi(func[freq[arr[idx]]]))%mod;
    freq[arr[idx]]--;
    prod=(prod*func[freq[arr[idx]]])%mod;
}

int main()
{
    int n,c,q;
    sfi(n)
    sfi(c)
    sfi(q)

    BLOCK=sqrt(n);

    f(i,1,n+1)
        sfl(arr[i])

    f(i,0,n+1)
        sfl(func[i])

    util queries[q];

    f(i,0,q)
    {
        sfi(queries[i].l)
        sfi(queries[i].r)
    }

    sort(queries,queries+q,cmp);

    int mleft=1,mright=0;

    prod=me(func[0],c);

    ans=1;

    f(i,0,q)
    {
        int left=queries[i].l;
        int right=queries[i].r;

        while(mright<right)
        {
            mright++;
            add(mright);

        }
        while(mright>right)
        {
            remove(mright);
            mright--;
        }
        while(mleft<left)
        {
            remove(mleft);
            mleft++;
        }
        while(mleft>left)
        {
            mleft--;
            add(mleft);
        }
        ans=(ans*prod)%mod;
    }

    pfl(ans)
}