RE求查错

回复帖子

@AcFirmament 2018-11-02 19:38 回复

其实就是题解的指针板

#include <bits/stdc++.h>
#define db  double 
#define ll  long long
#define MP  make_pair
#define ldb long double
#define PII pair <int, int>
#define ull unsigned long long
using namespace std;
const int mod = 998244353; // change mod there
const int N = 100100;      // change arry size there
const int INF = (int)1e9;  // change INF there
const db eps = 1e-9;       // change eps there
inline void INIT() { std :: ios :: sync_with_stdio(false); }
int n, m, cnt;
struct node {
  int siz, d, sum, lm, rm, ma;
  node *ch[2], *prt;
}pool[N], *root;
inline void update(node *p) {
  int s = p->d, siz = 1; 
  if(p->ch[0]) s += p->ch[0]->sum, siz += p->ch[0]->siz;
  if(p->ch[1]) s += p->ch[1]->sum, siz += p->ch[1]->siz;
  p->sum = s, p->siz = siz;
   int lm = -INF, rm = -INF, ma = -INF;
  if(p->ch[0] && p->ch[1]) {
    lm = max(lm, max(p->ch[0]->lm, p->ch[0]->sum + p->d + p->ch[1]->lm));
    rm = max(rm, max(p->ch[1]->rm, p->ch[1]->sum + p->d + p->ch[0]->rm));
    ma = max(p->ch[0]->rm + p->ch[1]->lm, max(p->ch[0]->ma, p->ch[1]->ma));;
  } else if(p->ch[0]) {
    lm = max(lm, max(p->ch[0]->lm, p->ch[0]->sum + p->d));
    rm = max(rm, p->ch[0]->rm + p->d);
    ma = max(ma, max(p->ch[0]->ma, rm));
  } else if(p->ch[1]) {
    lm = max(lm, p->ch[1]->lm + p->d);
    rm = max(rm, max(p->ch[1]->rm, p->ch[1]->sum + p->d));
    ma = max(ma, max(p->ch[1]->ma, lm));
  } else { lm = rm = max(0, p->d); ma = p->d; }
  p->lm = lm, p->rm = rm, p->ma = ma;
}
inline void rotate(node *p) {
  int k = p->prt->ch[1] == p;
  node *prt = p->prt, *gp = prt->prt, *son = p->ch[!k];
  if(son) son->prt = prt; prt->ch[k] = son;
  if(gp) gp->ch[gp->ch[1] == prt] = p; p->prt = gp;
  p->ch[!k] = prt; prt->prt = p;
  update(prt); update(p); if(prt == root) root = p;
}
inline void splay(node *p, node *tar) {
  while(p->prt != tar) {
    if(p->prt->prt == tar) rotate(p);
    else {
      node *prt = p->prt, *gp = p->prt->prt;
      if(prt->ch[gp->ch[1] == prt] == p) rotate(prt), rotate(p);
      else rotate(p), rotate(p);
    }
  }
}
inline node *find(node *p, int k) {
  // update(p);
  if(p->ch[0]->siz == k - 1) return p;
  else if(p->ch[0]->siz >= k) return find(p->ch[0], k);
  else return find(p->ch[1], k - p->ch[0]->siz - 1);
}
inline void ins(int x, int d) {
  node *p = find(root, x); splay(p, root);
  node *q = find(root, x + 1); splay(q, root->ch[1]);
  node *np = &pool[++cnt]; np->d = np->sum = d; np->siz = 1;
  q->ch[0] = np; np->prt = q;  update(np); update(q), update(p);
}
inline void del(int x) {
  node *p = find(root, x); splay(p, root);
  node *q = find(root, x + 1); splay(q, root->ch[1]);
  q->ch[1]->prt = p; p->ch[1] = q->ch[1]; update(p);
}
inline void upd(int x, int d) {
  node *p = find(root, x + 1); splay(p, root);
  p->d = d; update(p);
}
inline int qry(int l, int r) {
  node *p = find(root, l); splay(p, root);
  node *q = find(root, r + 2); splay(q, root->ch[1]);
  return q->ch[0]->ma;
}
int main() {
  root = &pool[++cnt]; root->siz = 1;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    int t; scanf("%d", &t);
    node *p = &pool[++cnt]; p->d = t, update(p);
    p->prt = root, root->ch[1] = p; rotate(p); 
  }
  node *p = &pool[++cnt]; p->d = 0; update(p);
  p->prt = root, root->ch[1] = p; rotate(p);
  scanf("%d", &m);
  for(int i = 1; i <= m; i++) {
    char op[5]; scanf("%s", op);
    if(op[0] == 'I') {
      int x, y; scanf("%d %d", &x, &y);
      ins(x, y);
    } else if(op[0] == 'D') {
      int x; scanf("%d", &x); del(x);
    } else if(op[0] == 'R') {
      int x, d; scanf("%d %d", &x, &d);
      upd(x, d);
    } else if(op[0] == 'Q') {
      int l, r; scanf("%d %d", &l, &r);
      printf("%d\n", qry(l, r));
    }
  } 
  return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。