[SPOJ GSS2]Can You Answer These Queries II

这道题非常的有意思，它查询区间和，但是还不计重复。说实话，看到不计重复这种诡异的条件，往可持久化想了，然后完全就没了思路。Orz 网上各种题解。这题有一个比较仁慈的地方：没有修改操作！所以可以离线。

按照右端点排序询问。我们令s[i]为不重复的sum[i..x]，其中x在最外层循环中从1~n。x每前进一位，把s[last[x]+1]到s[x]全部加上a[x]，其中last[x]是x上一次出现的位置。现在，当x等于某一个询问的右端点r的时候，我们的询问[l, r]，相当于询问所有历史中（包括现在）出现的最大的s[k] (k <= r)。听到历史这个词，很容易想到可持久化数据结构，或者说二维数据结构（比如套一个时间维）。但是实际上，这题要求的历史，是从一开始的历史，而不是从某个时间点开始的，因此，还是可以直接使用线段树的。

线段树节点[L, R]记录四个东西：

max:     现在的s[L..R]中最大的一个
tag:     现在还有多少数没有下传给孩子
evermax: 历史到现在的s[L..R]中最大的一个
evertag: 从上一次清除tag到现在最大的tag

然后clear过程就是一个非常纠结的事情。

son.evertag = max(son.evertag, son.tag + p.evertag);
son.evermax = max(son.evermax, son.max + p.evertag);
son.tag += p.tag;
son.max += p.tag;
p.tag = p.evertag = 0;

后面三句很好理解就不说了。第一句是因为tag是一个累加变量，而距离上一次clear我们还有p.evertag没有下传给孩子，所以说孩子还有son.tag+p.evertag这么多没有给孩子的孩子- -|| 而第二句的话就同理了，参照第三句和第四句的关系以及第一句的意义。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <cstdio>
#include <algorithm>

const int MAXN = 100001;
struct Node
{
  int max, tag, evermax, evertag;
} s[MAXN*4];
struct Question
{
  int l, r, index;
  Question() { }
  Question(const int a, const int b, const int i): l(a), r(b), index(i) { }
} q[MAXN];
inline bool operator<(const Question& lhs, const Question& rhs) { return lhs.r < rhs.r; }
int n, m, _st, _ed, _x, a[MAXN], _[MAXN*2], ans[MAXN];
int* const last = _+MAXN+1;
inline void clear(const int p, const int lef, const int rig)
{
  if (lef == rig) return;
  const int lc = p*2, rc = p*2+1;
  s[lc].evertag = std::max(s[lc].evertag, s[lc].tag + s[p].evertag);
  s[lc].evermax = std::max(s[lc].evermax, s[lc].max + s[p].evertag);
  s[lc].tag += s[p].tag;
  s[lc].max += s[p].tag;

  s[rc].evertag = std::max(s[rc].evertag, s[rc].tag + s[p].evertag);
  s[rc].evermax = std::max(s[rc].evermax, s[rc].max + s[p].evertag);
  s[rc].tag += s[p].tag;
  s[rc].max += s[p].tag;

  s[p].tag = s[p].evertag = 0;
}
inline void update(const int p, const int lef, const int rig)
{
  s[p].max = std::max(s[p*2].max, s[p*2+1].max);
  s[p].evermax = std::max(s[p*2].evermax, s[p*2+1].evermax);
}
void _modify(const int p, const int lef, const int rig)
{
  if (_st <= lef && rig <= _ed)
  {
    s[p].tag += _x;
    s[p].max += _x;
    s[p].evertag = std::max(s[p].evertag, s[p].tag);
    s[p].evermax = std::max(s[p].evermax, s[p].max);
    clear(p, lef, rig);
    return;
  }
  clear(p, lef, rig);
  const int mid = (lef+rig)/2;
  if (_st <= mid) _modify(p*2, lef, mid);
  if (mid+1 <= _ed) _modify(p*2+1, mid+1, rig);
  clear(p*2, lef, mid);
  clear(p*2+1, mid+1, rig);
  update(p, lef, rig);
}
int _query(const int p, const int lef, const int rig)
{
  clear(p, lef, rig);
  if (_st <= lef && rig <= _ed) return s[p].evermax;
  const int mid = (lef+rig)/2;
  int res = 0;
  if (_st <= mid) res = _query(p*2, lef, mid);
  if (mid+1 <= _ed) res = std::max(res, _query(p*2+1, mid+1, rig));
  return res;
}
inline void Modify(const int lef, const int rig, const int delta)
{
  _st = lef, _ed = rig, _x = delta;
  _modify(1, 1, n);
}
inline int Query(const int lef, const int rig)
{
  _st = lef, _ed = rig;
  return _query(1, 1, n);
}
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", a+i);
  scanf("%d", &m);
  for (int i = 0; i < m; q[i].index = i, ++i)
    scanf("%d%d", &q[i].l, &q[i].r);
  std::sort(q, q+m);
  for (int i = 1, j = 0; i <= n; ++i)
  {
    Modify(last[a[i]]+1, i, a[i]);
    last[a[i]] = i;
    for (; j < m && q[j].r == i; ++j)
      ans[q[j].index] = Query(q[j].l, q[j].r);
  }
  for (int i = 0; i < m; ++i)
    printf("%d\n", ans[i]);
}

Comments