HDU 5875 Function 优先队列+离线

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5875

Function

Time Limit: 7000/3500 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)
#### 问题描述
> The shorter, the simpler. With this problem, you should be convinced of this truth.
>
> You are given an array A of N postive integers, and M queries in the form (l,r). A function F(l,r) (1≤l≤r≤N) is defined as:
> F(l,r)={AlF(l,r−1) modArl=r;l You job is to calculate F(l,r), for each query (l,r).
>
#### 输入
> There are multiple test cases.
>
> The first line of input contains a integer T, indicating number of test cases, and T test cases follow.
>
> For each test case, the first line contains an integer N(1≤N≤100000).
> The second line contains N space-separated positive integers: A1,…,AN (0≤Ai≤109).
> The third line contains an integer M denoting the number of queries.
> The following M lines each contain two integers l,r (1≤l≤r≤N), representing a query.
>
#### 输出
> For each query(l,r), output F(l,r) on one line.
>
####样例输入
> 1
> 3
> 2 3 3
> 1
> 1 3

样例输出

题意

题解

代码

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=1e5+10;

int arr[maxn],ans[maxn];

struct Query{

    int l,r,id;

    Query(int l,int r,int id):l(l),r(r),id(id){}

    bool operator < (const Query& tmp) const {

        return l<tmp.l;

    }

};

struct Node{

    int id,v;

    Node(int id,int v):id(id),v(v){}

    bool operator < (const Node& tmp)const {

        return v<tmp.v;

    }

};

void init(){

    clr(ans,-1);

}

int n,m;

int main() {

    int tc,kase=0;

    scanf("%d",&tc);

    while(tc--){

        scf("%d",&n);

        init();

        for(int i=1;i<=n;i++) scf("%d",&arr[i]);

        scf("%d",&m);

        vector<Query> que;

        rep(i,0,m){

            int l,r;

            scf("%d%d",&l,&r);

            que.pb(Query(l,r,i));

        }

        sort(all(que));

        priority_queue<Node> pq;

        int p=0;

        for(int i=1;i<=n;i++){

            while(!pq.empty()&&pq.top().v>=arr[i]){

                Node nd=pq.top(); pq.pop();

                if(que[nd.id].r<i) continue;

                pq.push(Node(nd.id,nd.v%arr[i]));

                ans[que[nd.id].id]=nd.v%arr[i];

            }

            while(p<que.sz()&&que[p].l==i){

                pq.push(Node(p,arr[i]));

                ans[que[p].id]=arr[i];

                p++;

            }

        }

        rep(i,0,m){

            prf("%d\n",ans[i]);

        }

    }

    return 0;

}

//end-----------------------------------------------------------------------

/*

3

3

2 3 3

1

2 2

*/