题意:无修改询问区间最大子段和,但一个数字如果在一个区间中多次出现,只计一次

神题,我太菜了,根本不会
考虑离线处理,逐个加入序列的每个元素,假设当前处理到第k个元素,令s[j]表示\displaystyle\sum_{i=j}^k a[i],线段树维护s,对于一个询问[l,r],就可以通过处理完第r个元素以后询问[l,r]s的最大值来得到答案

每次修改的区间是[pre[a[i]]+1, i],然后更新pre[a[i]],就可以防止重复计数了

维护每个节点对应区间的当前最大s[i]值,历史最大s[i]值,lazy标记,历史最大lazy标记

关于为什么维护历史最大lazy标记,假设一个节点原有+5标记,并且某个询问的答案就在这个节点对应的区间内,此时pushdown下来一个-6标记,这个标记就会变成-1,然后就GG了

好长时间才懂

vector<pii>q[MAXN];
int a[MAXN], ans[MAXN], n, m, l, r, PRE[MAXN<<1], *pre = PRE + MAXN;
struct Node {
  int val, hval, Add, hAdd;
  Node *ls, *rs;
  inline void pushup() {
    val = max(ls->val, rs->val);
    hval = max(ls->hval, rs->hval);
  }
  inline void add(int v) {
    val += v, Add += v;
    chmax(hAdd, Add), chmax(hval, val);
  }
  inline void pushdown() {
    if (hAdd) chmax(ls->hval, ls->val + hAdd), chmax(ls->hAdd, ls->Add + hAdd), chmax(rs->hAdd, rs->Add + hAdd), chmax(rs->hval, rs->val + hAdd), hAdd = 0;
    if (Add) ls->val += Add, ls->Add += Add, rs->val += Add, rs->Add += Add, Add = 0;
  }
} pool[MAXN << 1], *root, *tail = pool;
inline Node *build(int l, int r) {
  Node *cur = tail++;
  if (l != r) cur->ls = build(l, mid), cur->rs = build(mid + 1, r);
  return cur;
}
inline int query(int ql, int qr, int l = 1, int r = n, Node *cur = root) {
  if (ql <= l && r <= qr) return cur->hval;
  int ret = 0;
  cur->pushdown();
  if (ql <= mid) chmax(ret, query(ql, qr, l, mid, cur->ls));
  if (qr > mid) chmax(ret, query(ql, qr, mid + 1, r, cur->rs));
  return ret;
}
inline void Modify(int ql, int qr, int v, int l = 1, int r = n, Node *cur = root) {
  if (ql <= l && r <= qr) return void(cur->add(v));
  cur->pushdown();
  if (ql <= mid) Modify(ql, qr, v, l, mid, cur->ls);
  if (qr > mid) Modify(ql, qr, v, mid + 1, r, cur->rs);
  cur->pushup();
}
int main() {
#ifdef LOCAL_DEBUG
  // freopen("data.in", "r", stdin), freopen("data.out", "w", stdout);
  Dbg = 1; uint tim1 = clock();
#endif
  in, n;
  lop(i,1,n) in, a[i];
  root = build(1, n);
  in, m;
  lop(i,1,m) {
    in, l, r;
    q[r].pb(mp(l, i));
  }
  lop(i,1,n) {
    Modify(pre[a[i]] + 1, i, a[i]);
    pre[a[i]] = i;
    ergo(q[i]) ans[it->second] = query(it->first, i);
  }
  lop(i,1,m) out, ans[i], '\n';
#ifdef LOCAL_DEBUG
  fprintf(stderr, "\ntime:%.5lfms", (clock() - tim1) / (1.0 * CLOCKS_PER_SEC) * 1000);
#endif
  return 0;
}
分类: 线段树

发表评论

电子邮件地址不会被公开。 必填项已用*标注