zoj 3633 – Alice’s present(暴力?set)

L – Alice’s present

Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Submit Status

Description

As a doll master, Alice owns a wide range of dolls, and each of them has a number tip on it’s back, the tip can be treated as a positive integer. (the number can be repeated). One day, Alice hears that her best friend Marisa’s birthday is coming , so she decides to sent Marisa some dolls for present. Alice puts her dolls in a row and marks them from 1 to n. Each time Alice chooses an interval from i to jin the sequence ( include i and j ) , and then checks the number tips on dolls in the interval from right to left. If any number appears more than once , Alice will treat this interval as unsuitable. Otherwise, this interval will be treated as suitable.

This work is so boring and it will waste Alice a lot of time. So Alice asks you for help .

Input

There are multiple test cases. For each test case:

The first line contains an integer n ( 3≤ n ≤ 500,000) ,indicate the number of dolls which Alice owns.

The second line contains n positive integers , decribe the number tips on dolls. All of them are less than 2^31-1. The third line contains an interger m ( 1 ≤ m ≤ 50,000 ),indicate how many intervals Alice will query. Then followed by m lines, each line contains two integeruv ( 1≤ uv≤ n ),indicate the left endpoint and right endpoint of the interval. Process to the end of input.

Output

For each test case:

For each query, If this interval is suitable , print one line “OK”. Otherwise, print one line ,the integer which appears more than once first.

Print an blank line after each case.

Sample Input

Sample Output

Hint

Alice will check each interval from right to left, don’t make mistakes.

 

噗。。

想了半天都没想明白。。。

一看市县5s。。要不就暴力来一发?

虽然1.6s通过的。。。但总觉得哪里不对。。

正解应该是线段树之类的吧?

sad

北京之前一定把基础线段树弄回了。。

至少。。。

抄几遍模板。。。

 

View Code

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz