ZOJ 3940 E - Modulo Query 区间取模

看了好久的题解，快看的自闭了才看懂（是我太菜了QAQ）

区间取模

[0,m + 1) 区间依次对a1,a2...an取模
一个区间[0,r)的数 mod a[i]，
如果r>a[i]，那么——
这个区间会变成r/a[i]个[0,a[i])的区间，以及一个[0,r%a[i])的区间

map记录的是区间出现的频率

对于每个Yi，统计Σ(p[xi]) ，xi代表小于Yi的数字，p[xi]代表区间[0,xi)出现的次数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
struct node1
{
    ll x,y;
}a[100010];

map<ll,ll>p;
map<ll,ll>::iterator it;
int T;
ll n,m,sum,ans,q;

bool cmp(node1 k,node1 l)
{
    return k.x < l.x;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        p.clear();
        p[m + 1] = 1;
        for(int i = 1;i <= n; ++i)
        {
            ll x;
            scanf("%lld",&x);
            while(1)
            {
                it = p.upper_bound(x);
                if(it == p.end()) break;
                p[x] += it->first / x * it->second;
                if(it->first % x) p[it->first % x] += it->second;
                p.erase(it);
            }
        }
        sum = 0;
        for(it = p.begin();it != p.end(); ++it)
            sum += it->second;
        scanf("%lld",&q);
        for(int i = 0;i < q; ++i)
        {
            scanf("%lld",&a[i].x);
            a[i].y = (ll)i + 1;
        }
        sort(a,a + q,cmp);
        it = p.begin();
        ans = 0;
        for(int i = 0;i < q; ++i)
        {
            while(a[i].x >= it->first)
            {
                sum -= it->second;
                it++;
                if(it == p.end()) break;
            }
            if(it == p.end()) break;
            ans = (ans + sum * a[i].y) % P;
        }
        printf("%lld\n",ans);
    }
    return 0;
}