Problem 1862 QueryProblem

Accept: 100    Submit: 249
Time Limit: 2000 mSec    Memory Limit : 32768 KB

There
are N numbers (non-negative integers) in a circle. Now your task is
quite simple, just tell me the largest number between L and R.

The Figure 1 is a sample of five integers in a circle. (marked with their index, but not their exact value.)

Figure 1.

The Figure 2,3 show how we count the number.



Figure 2.



Figure 3.

There are no more than 10 test cases;

For each case, the first line contains only one integer N, indicates the size of the circle.

The following one line contains N non-negative integers where Mi
indicates the i-th integers whose index is i. (1 <= N <= 1000, 1
<= i <= N, 0 <= Mi <= 10^9)

Then one line contains Q indicates the number of querys. (1 <= Q <= 10^5)

Then the next Q lines, each line contains only two integers indicate L and R (1 <= L,R <= N)

For each case, please output “Case #index:” in a single line, here index is the case index starts from one.

For each query just output a single line indicates the largest number between L and R.

Output a blank line after each case.

2
3 8
3
1 1
1 2
2 1
1
9
1
1 1

Case #1:
3
8
8

Case #2:
9

#include <cstdio>

#include <iostream>

#include <cstdlib>

#include <algorithm>

#include <ctime>

#include <cmath>

#include <string>

#include <cstring>

#include <stack>

#include <queue>

#include <list>

#include <vector>

#include <map>

#include <set>

using namespace std;

const int INF=0x3f3f3f3f;

const double eps=1e-;

const double PI=acos(-1.0);

#define maxn 8006

int tre[maxn];

int a[maxn/];

int n;

void build(int num, int le, int ri)

{

    if(le == ri)

    {

        if(le > n)

            tre[num] = a[le-n];//函数中的num指的是线段树上的编号，而当le == ri时，le 或 ri指的是最低层的编号。

        else

            tre[num] = a[le];

        return;

    }

    int mid = (le + ri)/;

    build(num*, le, mid);

    build(num*+, mid+, ri);

    tre[num] = max(tre[num*], tre[num*+]);

}

int query(int num,int le,int ri,int x,int y)

{

    if(x<=le&&y>=ri)

        return tre[num];

    int mid=(le+ri)/;

    int ans=;

    if(x<=mid)

        ans=max(ans,query(num*,le,mid,x,y)); //先查询左边

    if(y>mid)

        ans=max(ans,query(num*+,mid+,ri,x,y)); //再查询右边

    return ans;

}

int main()

{

    int cas = ;

    while(~scanf("%d", &n))

    {

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

            scanf("%d", &a[i]);

        build(, , *n);

        int m;

        scanf("%d", &m);

        int a, b;

        printf("Case #%d:\n", cas++);

        for(int j = ; j < m; j++)

        {

            scanf("%d%d", &a, &b);

            if(b < a)

                b = b + n;

            printf("%d\n", query(, , *n, a, b));

        }

        puts("");

    }

}

#include <cstdio>

#include <iostream>

#include <cstdlib>

#include <algorithm>

#include <ctime>

#include <cmath>

#include <string>

#include <cstring>

#include <stack>

#include <queue>

#include <list>

#include <vector>

#include <map>

#include <set>

#define C 0.57721566490153286060651209

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const double eps=1e-;

const double PI=acos(-1.0);

const int maxn=;

int dp[][];

int a[];

int main()

{

    int n, b;

    int sum=;

    while(~scanf("%d", &n))

    {

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

        {

            scanf("%d", &b);

            a[i]=a[i+n]=b;

        }

        for(int i = ; i <=*n; i++)

        {

             dp[i][i]=a[i];

            for(int j=i+;j<=*n;j++)

            {

                if(a[j]>dp[i][j-])

                    dp[i][j]=a[j];

                else

                    dp[i][j]=dp[i][j-];

            }

        }

        int m;

        scanf("%d", &m);

        int L, R;

        printf("Case #%d:\n",++sum);

        for(int i=;i<=m;i++)

        {

            int q,w;

            scanf("%d%d",&q,&w);

            if(w<q)

                w=w+n;

            printf("%d\n",dp[q][w]);

        }

        puts("");

    }

    return ;

}