文字解释见http://hi.baidu.com/lewutian/blog/item/d0e058ea85b780d8d539c9bf.html
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 111111
#define MAXM 104444
#define INF 100000000
#define PI acos(-1.0)
#define eps 1e-12
#define L(X) X<<1
#define R(X) X<<1|1
using namespace std;
struct PP
{
int left, right, num;
}p[MAXN];
struct node
{
int left, right, mid;
int mx;
}tree[4 * MAXN];
int v[MAXN], h[MAXN];
int n, m, len;
void get()
{
len = 1;
p[1].left = 1;
p[1].num = 1;
h[1] = 1;
for(int i = 2; i <= n; i++)
{
if(v[i] == v[i - 1])
p[len].num++;
else
{
p[len++].right = i - 1;
p[len].left = i;
p[len].num = 1;
}
h[i] = len;
}
p[len].right = n;
}
void up(int C)
{
tree[C].mx = max(tree[L(C)].mx, tree[R(C)].mx);
}
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) >> 1;
if(s == e){tree[C].mx = p[s].num; return;}
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
up(C);
}
int query(int s, int e, int C)
{
if(tree[C].left >= s && tree[C].right <= e) return tree[C].mx;
int ret = 0;
if(tree[C].mid >= s) {int t = query(s, e, L(C)); ret = max(ret, t);}
if(tree[C].mid < e) {int t = query(s, e, R(C)); ret = max(ret, t);}
return ret;
}
int in()
{
int flag = 1;
char ch;
int a = 0;
while((ch = getchar()) == ' ' || ch == '\n');
if(ch == '-') flag = -1;
else
a += ch - '0';
while((ch = getchar()) != ' ' && ch != '\n')
{
a *= 10;
a += ch - '0';
}
return flag * a;
}
void out(int a)
{
if(a < 0) {putchar('-'); a = -a;}
if(a >= 10)out(a / 10);
putchar(a % 10 + '0');
}
int main()
{
while(scanf("%d", &n) != EOF && n)
{
scanf("%d", &m);
for(int i = 1; i <= n; i++) v[i] = in();
get();
make_tree(1, len, 1);
for(int i = 1; i <= m; i++)
{
int x, y;
x= in();
y = in();
int u = h[x];
int v = h[y];
if(u == v) out(y - x + 1);
else if(u == v - 1) out(max(p[u].right - x + 1, y - p[v].left + 1));
else
{
int ans = max(p[u].right - x + 1, y - p[v].left + 1);
int t = query(u + 1, v - 1, 1);
ans = max(ans, t);
out(ans);
}
putchar('\n');
}
}
return 0;
}
分享到:
相关推荐
广工《算法和高级数据结构教程课程设计》 Frequent Values(poj 3368) C语言实现
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1740501
poj 2763 程序 线段树 LCA 2000MS AC
线段树、树状数组算法入门 加 poj解题报告 pdf文档
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1705139
1.Frequent Values(poj 3368) 2.郁闷的出纳员(伸展树)
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 2785 4 Values whose Sum is 0 测试数据 解题报告: http://blog.csdn.net/qq7366020/article/details/8623208
POJ3468,线段树处理,注意longlongint
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...