[BZOJ 4241] 历史研究
程序员文章站
2022-05-27 18:56:43
...
BZOJ传送门
题目描述
IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。
日记中记录了连续天发生的时间,大约每天发生一件。
事件有种类之分。第天发生的事件的种类用一个整数表示,越大,事件的规模就越大。
JOI教授决定用如下的方法分析这些日记:
-
选择日记中连续的一些天作为分析的时间段
-
事件种类的重要度为*(这段时间内重要度为的事件数)
-
计算出所有事件种类的重要度,输出其中的最大值
现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。
输入输出格式
输入格式
第一行两个空格分隔的整数和,表示日记一共记录了天,询问有次。
接下来一行个空格分隔的整数,表示第天发生的事件的种类
接下来行,第行有两个空格分隔整数和,表示第次询问的区间为。
输出格式
输出行,第行一个整数,表示第次询问的最大重要度
输入输出样例
输入样例#1:
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
输出样例#1:
9
8
8
16
16
解题分析
如果用普通莫队在删除时无法维护次大值, 需要一个, 就GG了。
所以去学了新姿势: 回滚莫队。
还是分块, 把左端点在一块的询问按右端点从小到大排序。
如果左右端点都在一块先处理掉。
然后我们只维护左端点在当前左端点所在块最右端, 且右端点单调递增的答案, 每次动态插入左边块内的元素统计答案后再撤销。
总复杂度还是的。
代码如下:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <vector>
#include <tr1/unordered_map>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 100500
#define ll long long
template <class T>
IN void in(T &x)
{
x = 0; R char c = gc;
for (; !isdigit(c); c = gc);
for (; isdigit(c); c = gc)
x = (x << 1) + (x << 3) + c - 48;
}
template <class T> IN T max(T a, T b) {return a > b ? a : b;}
std::tr1::unordered_map <int, int> mp;
int n, m, sqr, qcnt, arr, bcnt;
ll ans[MX];
int blk[MX], val[MX], cnt[MX], id[MX];
struct Query {int l, r, id;};
IN bool operator < (const Query &x, const Query &y) {return x.r < y.r;}
std::vector <Query> que[500];
int main(void)
{
int foo, bar, cur, siz;
R ll rem, mx;
in(n), in(m); sqr = std::sqrt(n); bcnt = n / sqr;
for (R int i = 1; i <= n; ++i)
{
in(foo), blk[i] = i / sqr;
if (!mp[foo]) mp[foo] = ++arr, val[arr] = foo;
id[i] = mp[foo];
}
for (R int i = 1; i <= m; ++i)
{
in(foo), in(bar);
if (blk[foo] == blk[bar])
{
mx = 0;
for (R int j = foo; j <= bar; ++j)
{
++cnt[id[j]];
mx = max(1ll * cnt[id[j]] * val[id[j]], mx);
}
ans[i] = mx; mx = 0;
for (R int j = foo; j <= bar; ++j) --cnt[id[j]];
}
else que[foo / sqr].push_back({foo, bar, i});
}
std::sort(que + 1, que + 1 + qcnt);
for (R int i = 0; i <= bcnt; ++i)
{
std::sort(que[i].begin(), que[i].end());
std::memset(cnt, mx = 0, sizeof(cnt));
cur = (i + 1) * sqr - 1, siz = que[i].size();
for (R int j = 0; j < siz; ++j)
{
W (cur < que[i][j].r)
{
++cur;
++cnt[id[cur]];
mx = max(mx, 1ll * cnt[id[cur]] * val[id[cur]]);
}
rem = mx;
for (R int k = (i + 1) * sqr - 1; k >= que[i][j].l; --k)
{
++cnt[id[k]];
mx = max(mx, 1ll * cnt[id[k]] * val[id[k]]);
}
ans[que[i][j].id] = mx;
for (R int k = (i + 1) * sqr - 1; k >= que[i][j].l; --k) --cnt[id[k]];
mx = rem;
}
}
for (R int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}
推荐阅读
-
BZOJ1008
-
BZOJ1008: [HNOI2008]越狱(快速幂)
-
BZOJ1927: [Sdoi2010]星际竞速(最小费用最大流 最小路径覆盖)
-
BZOJ4650: [Noi2016]优秀的拆分(hash 调和级数)
-
BZOJ4598: [Sdoi2016]模式字符串(点分治 hash)
-
BZOJ1925: [Sdoi2010]地精部落(dp)
-
BZOJ4602: [Sdoi2016]齿轮(并查集 启发式合并)
-
BZOJ5462: [APIO2018] 新家(K-D Tree)
-
BZOJ4513: [Sdoi2016]储能表(数位dp)
-
BZOJ2946 [Poi2000]公共串(后缀自动机)