题解【bzoj1251 序列终结者】

Description

维护三个操作：区间加，区间翻转，区间求最大值。(n leq 50000)

Solution

fhqtreap大法好！

模板题（我是不会告诉你这篇题解是用来存个代码的

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const int N = 50050; 
int n, m; 
struct node {
  int d, rnd, Mx, add, rev, siz; 
  node *ch[2]; 
  inline void upd() {
    int sizz = 1, MX = d; 
    if(ch[0]) sizz += ch[0]->siz, MX = max(MX, ch[0]->Mx); 
    if(ch[1]) sizz += ch[1]->siz, MX = max(MX, ch[1]->Mx); 
    siz = sizz; Mx = MX; 
  }
  inline void push() {
    if(add) {
      if(ch[0]) { ch[0]->d += add, ch[0]->Mx += add, ch[0]->add += add; }
      if(ch[1]) { ch[1]->d += add, ch[1]->Mx += add, ch[1]->add += add; }
      upd(); add = 0; 
    } if(rev) {
      swap(ch[0], ch[1]); 
      if(ch[0]) ch[0]->rev ^= 1;
      if(ch[1]) ch[1]->rev ^= 1; 
      rev = 0; 
    }
  }
}pool[N], *cur = pool, *root;
inline int siz(node *p) { if(p) return p->siz; return 0; }
inline node *newnode(int d) { 
  node *ret = cur++; 
  ret->siz = 1, ret->d = ret->Mx = d, 
  ret->add = ret->rev = 0; ret->rnd = rand(); 
  ret->ch[0] = ret->ch[1] = 0; 
  return ret; 
}
inline node *merge(node *p, node *q) {
  if(!p) return q; if(!q) return p; 
  if(p->rnd  < q->rnd) { p->push(); p->ch[1] = merge(p->ch[1], q); p->upd(); return p; }
  if(p->rnd >= q->rnd) { q->push(); q->ch[0] = merge(p, q->ch[0]); q->upd(); return q; } 
}
inline void split(node *r, int k, node *&p, node *&q) {
  if(!r) { p = q = NULL; return ; } r->push(); 
  if(siz(r->ch[0]) < k) p = r, split(r->ch[1], k - siz(r->ch[0]) - 1, r->ch[1], q);
  else q = r, split(r->ch[0], k, p, r->ch[0]); r->upd();  
}
int main() {
  srand((unsigned long long)new char);
  scanf("%d %d", &n, &m); root = newnode(0); 
  for(int i = 2; i <= n; i++) root = merge(root, newnode(0)); 
  for(int i = 1; i <= m; i++) {
    int op, l, r, x; node *p, *q, *s; 
    scanf("%d %d %d", &op, &l, &r); 
    split(root, l - 1, p, q); 
    split(q, r - l + 1, q, s);
    if(op == 1) scanf("%d", &x), q->add += x, q->d += x, q->Mx += x; 
    if(op == 2) q->rev ^= 1; 
    if(op == 3) printf("%d
", q->Mx); 
    root = merge(p, merge(q, s)); 
  }
  return 0; 
}