Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 给一发自己写的线段树 700+ms PS: 用cin,cout会超时哦

Posted by marszed at 2017-05-19 21:54:24 on Problem 3368
```话说现在POJ的机器是不是有点卡啊  提交之后经常有7,8份代码在waiting

#include<cstdio>
#include<iomanip>
#include<iostream>
#include<algorithm>
using namespace std;

#define maxn 100010

int n, m;
int input[maxn], start[maxn << 1], End[maxn << 1];

struct Node {
int l, r, lval, rval, mval, mfru;
}cover[maxn << 2];

struct Point {
int val, fru;
};

Point eg;

void pushup(int rt)
{
cover[rt].lval = cover[rt << 1].lval;
cover[rt].rval = cover[rt << 1 | 1].rval;
cover[rt].mfru = max(cover[rt << 1].mfru, cover[rt << 1 | 1].mfru);
cover[rt].mval = cover[rt << 1].mfru > cover[rt << 1 | 1].mfru ? cover[rt << 1].mval : cover[rt << 1 | 1].mval;
if (cover[rt << 1].rval == cover[rt << 1 | 1].lval)
{
int l = max(cover[rt].l, start[cover[rt << 1].rval + 100010]);
int r = min(cover[rt].r, End[cover[rt << 1 | 1].lval + 100010]);
if (r - l + 1 > cover[rt].mfru)
{
cover[rt].mfru = r - l + 1;
cover[rt].mval = cover[rt << 1].rval;
}
}
}

void build(int rt, int l, int r)
{
cover[rt].l = l;
cover[rt].r = r;
if (l == r)
{
cover[rt].mfru = 1;
cover[rt].mval = cover[rt].lval = cover[rt].rval = input[l];
return;
}
int m = (l + r) >> 1;
build(rt << 1, l, m);
build(rt << 1 | 1, m + 1, r);
pushup(rt);
}

Point query(int rt, int qstart, int qend)
{
if (qstart <= cover[rt].l&&cover[rt].r <= qend)
{
eg.val = cover[rt].mval;
eg.fru = cover[rt].mfru;
return eg;
}
int m = (cover[rt].l + cover[rt].r) >> 1;
if (m >= qend)
return query(rt << 1, qstart, qend);
if (m < qstart)
return query(rt << 1 | 1, qstart, qend);
Point p1 = query(rt << 1, qstart, qend), p2 = query(rt << 1 | 1, qstart, qend);
Point tmp = p1.fru > p2.fru ? p1 : p2;
if (cover[rt << 1].rval != cover[rt << 1 | 1].lval)
return tmp;
int l = max(max(qstart, start[cover[rt << 1].rval + 100010]), cover[rt << 1].l);
int r = min(min(qend, End[cover[rt << 1 | 1].lval + 100010]), cover[rt << 1 | 1].r);
if (r - l + 1 <= tmp.fru) return tmp;
tmp.val = cover[rt << 1].rval;
tmp.fru = r - l + 1;
return tmp;
}

int main()
{

ios::sync_with_stdio(false);

while (cin >> n&&n)
{
scanf("%d", &m);
//cin >> m;
memset(start, 0, sizeof(start));
for (int i = 1; i <= n; i++)
{
scanf("%d", &input[i]);
//cin >> input[i];
if (!start[input[i] + 100010]) start[input[i] + 100010] = i;
End[input[i] + 100010] = i;
}
build(1, 1, n);
int l, r;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &l, &r);
//cin >> l >> r;
printf("%d\n", query(1, l, r).fru);
//cout << query(1, l, r).fru << endl;
}
}
return 0;
}

```

Followed by: