ZOJ 3940 Modulo Query

0–M对某个数字取模，相当于把0–M区间进行切割，每次暴力切割一下。结果的算的时候二分一下即可。。。

看了官方题解才会。。。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;const int maxn=+;
long long mod=1e9+;
int T,m,sz;
struct X
{
    int x;
    long long y;
    bool operator<(const X&a)const
    {
        return x < a.x;
    }
    X(int a,long long b) {x=a,y=b;}
};
long long sum[maxn],cnt[maxn];
int v[maxn];long long get(int now)
{
    long long res=;
    int l=,r=sz-;
    while(l<=r)
    {
        int mid=(l+r)/;
        if(v[mid]>=now)
        {
            l=mid+;
            res=sum[mid];
        }
        else r=mid-;
    }
    return res;
}int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int n; scanf("%d%d",&n,&m);
        priority_queue<X>q;
        q.push(X(m,));
        for(int i=;i<=n;i++)
        {
            int x; scanf("%d",&x);
            while()
            {
                if(q.top().x<x) break;
                X head=q.top(); q.pop();
                q.push(X(x-, (head.x + ) / x*head.y));
                if ((head.x+)%x>=) q.push(X(head.x%x, head.y));
            }
        }        sz=;
        v[sz]=q.top().x; cnt[sz]=q.top().y;
        q.pop(); sz++;        while(!q.empty())
        {
            X head=q.top(); q.pop();
            if(head.x==v[sz-]) cnt[sz-]+=head.y;
            else
            {
                v[sz]=head.x;
                cnt[sz]=head.y;
                sz++;
            }
        }        sum[]=cnt[];
        for(int i=;i<sz;i++) sum[i]=sum[i-]+cnt[i];        int Q; scanf("%d",&Q);
        long long ans=;
        for(long long i=;i<=Q;i++)
        {
            int g; scanf("%d",&g);
            ans=(ans+i*get(g)%mod)%mod;
        }        printf("%lld\n",ans%mod);
    }
    return ;
}