BZOJ1251 序列終結者

---

題目：1. 將\([L,R]\)這個區間內的所有數加上\(V\)。 2. 將\([L,R]\)這個區間翻轉。 3. 求\([L,R]\)這個區間中的最大值。 最開始所有元素都是\(0\)。

存個模板

Code

#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cctype> typedef long long ll; const int N = 100010; const int inf = 0x3f3f3f3f; template<class T> inline void read(T &x) {x = 0; char c = getchar(); T f = 1;while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}while(isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}x *= f; } using namespace std; int n, q, opt, l, r, v, k; class Splay { private :struct Node {int fa, ch[2], sz, rev, tag, mx, v; // rev 翻轉標記，tag 加法標記} T[N];int root;#define lc T[p].ch[0]#define rc T[p].ch[1]#define pa T[p].fainline int LR(int p) {return T[pa].ch[1] == p;}inline void PushUp(int p) {T[p].sz = T[lc].sz + T[rc].sz + 1;T[p].mx = max(T[p].v, max(T[lc].mx, T[rc].mx));}inline void PushDown(int p) {if(T[p].rev) {swap(lc,rc);if(lc) T[lc].rev ^= 1;if(rc) T[rc].rev ^= 1;T[p].rev = 0;}if(T[p].tag) {int &A = T[p].tag;if(lc) T[lc].tag += A, T[lc].mx += A, T[lc].v += A;if(rc) T[rc].tag += A, T[rc].mx += A, T[rc].v += A;A = 0;}}int Build(int l,int r,int f) {if(l > r) return 0;int p = (l + r) >> 1;lc = Build(l,p-1, p); rc = Build(p+1, r, p);T[p].fa = f;T[p].mx = T[p].v = T[p].rev = T[p].tag = 0;PushUp(p);return p;}inline void rotate(int p) {int f = T[p].fa, g = T[f].fa, c = LR(p);if(g) T[g].ch[LR(f)] = p; T[p].fa = g;T[f].ch[c] = T[p].ch[c^1]; T[T[f].ch[c]].fa=f;T[p].ch[c^1] = f; T[f].fa = p;PushUp(f); PushUp(p);}void splay(int p, int ed) {for(;T[p].fa != ed; rotate(p))if(T[pa].fa != ed) rotate(LR(p)==LR(pa)?pa:p);if(ed == 0) root = p;}inline int kth(int k) {int ls = 0, p = root;while(p) {PushDown(p);int tmp = T[lc].sz + ls;if( tmp < k && k <= tmp + 1) return p;if(k <= tmp) p = lc;else ls = tmp+1, p = rc;}return -1;} public:int Init(int n) {T[0].mx = -inf;root = Build(1, n+2, 0);}void Add(int l, int r, int v) {// 操作[l,r]，l-1splay到根，r+1splay到根的rc，r+1的lc就是我們要操作的序列int p = kth(l); splay(p, 0);p = kth(r+2), splay(p, root); T[lc].tag += v; T[lc].mx += v; T[lc].v += v;}void Rev(int l, int r) {int p = kth(l); splay(p, 0);p = kth(r+2), splay(p, root);T[lc].rev ^= 1; //先打標記，pushdown時進行翻轉}void Ask(int l, int r) {int p = kth(l); splay(p, 0);p = kth(r+2); splay(p, root);printf("%d\n", T[lc].mx);} } tree; int main() {read(n), read(q);tree.Init(n);while(q--) {read(opt), read(l), read(r);if(opt == 1) read(v), tree.Add(l, r, v);else if(opt == 2) tree.Rev(l, r);else if(opt == 3) tree.Ask(l, r);} }

轉載于:https://www.cnblogs.com/RRRR-wys/p/10527814.html

總結

以上是生活随笔為你收集整理的BZOJ1251 序列终结者的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。