求卡常

#include<bits/stdc++.h>
#define endl '\n'
#define stt setvbuf(stdout, NULL, _IOFBF, 1 << 20)
#define start2 ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
const int MAXN = 1000005;
int n, m, x;
int a[MAXN], b[MAXN];
int ans[MAXN];
int st[MAXN], top;
int pre[MAXN];
struct STRUCT{
    int l, r, id;
}q[MAXN];
bool cmp(STRUCT x, STRUCT y){ return x.r < y.r; }
int c[MAXN];
void update(int start, int val){
    for(int i = start;i <= n;i += i & -i)
        c[i] += val;
}
int query(int start){
    int res = 0;
    for(int i = start;i > 0;i -= i & -i)
        res += c[i];
    return res;
}
int main(){
    stt;
    start2;
    cin >> n >> m >> x;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= n;i++)
        cin >> b[i];
    for(int i = 1;i <= m;i++)
        cin >> q[i].l;
    for(int i = 1;i <= m;i++){
        cin >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m, cmp);
    for(int i = 1;i <= n;i++){
        while(top > 0 && a[st[top]] <= a[i])
            top--;
        pre[i] = st[top];
        st[++top] = i;
    }
    int now = 1;
    for(int i = 1;i <= n;i++){
        int j = i;
        while(j > 0){
            if(b[i] % a[j] == x % a[j]){
                update(pre[j] + 1, 1);
                update(j + 1, -1);
            }
            j = pre[j];
        }
        while(now <= m && q[now].r == i){
            ans[q[now].id] = query(q[now].l);
            now++;
        }
    }
    for(int i = 1;i <= m;i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}