Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* unsolved */
- #include <iostream>
- #include <vector>
- #include <map>
- #include <cmath>
- #include <fstream>
- using namespace std;
- #define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
- #define READ(f) freopen(f, "r", stdin)
- #define Max 100010
- vector <int> segment_tree;
- int data[Max];
- size_t arrLength;
- void initSegmentTree() {
- int length = 2 * pow(2.0, floor(log((double) arrLength ) / log(2.0)) + 1 );
- segment_tree.clear();
- segment_tree.resize(length, 0);
- }
- void buildHelper( int node, int begin, int end ) {
- if (begin == end) {
- segment_tree[node] = begin;
- return;
- }
- int leftIndx = 2 * node, rightIndx = 2 * node + 1;
- buildHelper( leftIndx, begin, (begin + end) / 2);
- buildHelper(rightIndx, (begin + end) / 2 + 1, end);
- int lContent = segment_tree[leftIndx], rContent = segment_tree[rightIndx];
- segment_tree[node] = ( data[lContent] >= data[rContent] ) ? lContent : rContent;
- }
- void buildSegmentTree() {
- buildHelper(1, 0, arrLength - 1);
- }
- int queryHelper( int node, int begin, int end, int i, int j) {
- if (i > end || j < begin) return -1;
- if (begin >= i && end <= j) return segment_tree[node];
- int pos1 = queryHelper(2 * node, begin, (begin + end) / 2, i, j);
- int pos2 = queryHelper(2 * node + 1, (begin + end) / 2 + 1, end, i, j);
- if(pos1 == -1) return pos2;
- if(pos2 == -1) return pos1;
- return (data[pos1] >= data[pos2]) ? pos1 : pos2;
- }
- int query(int lower, int upper) {
- return queryHelper(1, 0, arrLength - 1, lower, upper);
- }
- int main() {
- READ("in.txt");
- int n, q, begin, end, result;
- while(cin >> n && n) {
- cin >> q;
- arrLength = n;
- map <int , int> track;
- rep(i, n) {
- cin >> data[i];
- track[data[i]] += 1;
- }
- rep(i, n) data[i] = track[data[i]];
- initSegmentTree();
- buildSegmentTree();
- rep(i, q) {
- cin >> begin >> end;
- begin--, end--;
- if(begin == end) {
- cout << 1 << "\n";
- continue;
- }
- if(data[begin] == data[end]) {
- cout << end - begin + 1 << "\n";
- continue;
- }
- if(begin > 0 || end < arrLength - 1) {
- if(begin > 0 && end < arrLength - 1) {
- int subq1 = 1, subq2 = 1;
- if(data[begin - 1] == data[begin]) {
- for(int i = begin + 1; data[begin] == data[i] && i <= end; i++) subq1++;
- }
- if(data[end + 1] == data[end]) {
- for(int i = end - 1; data[end] == data[i] && i >= begin; i--) subq2++;
- }
- if((end - begin + 1) - (subq1 + subq2) > 0) {
- int temp = max(subq1, data[query(begin + subq1, end - subq2)]);
- result = max(temp, subq2);
- } else result = (subq1, subq2);
- } else if(begin > 0 && end == arrLength - 1) {
- if(data[begin - 1] == data[begin]) {
- int subq = 1;
- for(int i = begin + 1; data[begin] == data[i] && i <= end; i++) subq++;
- result = max(data[query(begin + subq, end)], subq);
- } else result = data[query(begin, end)];
- } else {
- if(data[end + 1] == data[end]) {
- int subq = 1;
- for(int i = end - 1; data[end] == data[i] && i >= begin; i--) subq++;
- result = max(data[query(begin, end - subq)], subq);
- } else result = data[query(begin, end)];
- }
- } else result = data[query(begin, end)];
- cout << result << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement