【BZOJ2506】calc

Description

           n       A1,A2,…,An。  m   ，      l,r,p,k，   l<=i<=r Ai mod p = k  i   。

Inputの最初の行の2つの正の整数nとm.2行目のn個の数は、A 1,A 2,...,Anを表す.以下のm行は、各行の4つの数がそれぞれl,r,p,kを表す.1<=l<=r<=nを満たす.
Outputは,質問ごとに1行出力し,実行可能値iの個数を表す.
Sample Input 5 2 1 5 2 3 7 1 3 2 1 2 5 3 0
Sample Output 2 1 HINT
データ範囲:

     0<n,m<=10^5，  1<=i<=n  Ai<=10^4，0<p<=10^4，0<=k<p。

Source
2011福建合宿
でたらめな問題><質問を2つに分割して反発原理で答えを得ることを考慮し、オフラインで座標順に質問をpサイズで2種類に分ける:p<=100、p>100 p<=100の私たちは、aが10000以下であるため、最大100回

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 100010
#define MAXINT 0x7fffffff
#define GET (ch>='0'&&ch<='9')
using namespace std;
int n,m,top;
int a[MAXN],ans[MAXN][2];
int c[110][110],Count[MAXN];
struct Query
{
    int opt,pos,p,k,id;
    bool operator <(const Query& a)const    {return pos<a.pos;}
}q[MAXN<<1];
void in(int &x)
{
    char ch=getchar();x=0;
    while (!GET)    ch=getchar();
    while (GET) x=x*10+ch-'0',ch=getchar();
}
void insert(int x)
{
    for (int i=1;i<=100;i++)    c[i][x%i]++;
    Count[x]++;
}
int main()
{
    in(n);in(m);int l,r,p,k;
    for (int i=1;i<=n;i++)  in(a[i]);
    for (int i=1;i<=m;i++)
    {
        in(l);in(r);in(p);in(k);
        q[++top].pos=l-1;q[top].p=p;q[top].k=k;q[top].id=i;q[top].opt=0;
        q[++top].pos=r;q[top].p=p;q[top].k=k;q[top].id=i;q[top].opt=1;
    }
    sort(q+1,q+top+1);int now=0;
    for (int i=1;i<=top;i++)
    {
        while (now<q[i].pos)    insert(a[++now]);
        if (q[i].p<=100)    ans[q[i].id][q[i].opt]+=c[q[i].p][q[i].k];
        else
            for (int j=q[i].k;j<=10000;j+=q[i].p)   ans[q[i].id][q[i].opt]+=Count[j];
    }
    for (int i=1;i<=m;i++)  printf("%d
",ans[i][1]-ans[i][0]);
}