【題目鏈接】

? ? ? ? ? ?點擊打開鏈接

【算法】

? ? ? ? ? 本題也是Splay區間操作的模板題，不過要比BZOJ 3223要稍微復雜一些，做完此題后，我終于對Splay有了更深入的理解，有“撥開云霧見青天”的感覺

??????? ? ? 本題還是有許多細節的，筆者花了5h才通過了此題

【代碼】

? ? ? ? ??

#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 100000 const int INF = 2e9;int i,N,M,d,P,x,y,t; int a[MAXN+10]; string opt;template <typename T> inline void read(T &x) {int f=1; x=0;char c = getchar();for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';x *= f; }template <typename T> inline void write(T x) {if (x < 0) { putchar('-'); x = -x; }if (x > 9) write(x/10);putchar(x%10+'0'); }template <typename T> inline void writeln(T x) {write(x);puts(""); }struct Splay {int root,total;struct Node {int fa,son[2],size,add,Min,val;bool rev; } Tree[MAXN*2+10];inline bool get(int x) {return Tree[Tree[x].fa].son[1] == x;}inline void build(int index,int l,int r) {int mid = (l + r) >> 1;Tree[index].size = 1;Tree[index].add = Tree[index].rev = 0;Tree[index].val = Tree[index].Min = a[mid]; if (l == r) return;if (l < mid) {++total;Tree[index].son[0] = total;Tree[total].fa = index;build(total,l,mid-1);Tree[index].size += Tree[Tree[index].son[0]].size;Tree[index].Min = min(Tree[index].Min,Tree[Tree[index].son[0]].Min);}if (mid < r) {++total;Tree[index].son[1] = total;Tree[total].fa = index;build(total,mid+1,r);Tree[index].size += Tree[Tree[index].son[1]].size;Tree[index].Min = min(Tree[index].Min,Tree[Tree[index].son[1]].Min);}}inline void new_node(int index,int x,int f) {Tree[index].rev = 0;Tree[index].size = 1;Tree[index].val = Tree[index].Min = x;Tree[index].add = 0;Tree[index].fa = f;Tree[index].son[0] = Tree[index].son[1] = 0;}inline int query_pos(int x) {int index = root;while (true) {pushdown(index);if (x > Tree[Tree[index].son[0]].size) {x -= Tree[Tree[index].son[0]].size;if (x == 1) return index;--x;index = Tree[index].son[1];} else index = Tree[index].son[0];} }inline void pushdown(int index) {if (Tree[index].rev) {swap(Tree[index].son[0],Tree[index].son[1]);Tree[Tree[index].son[0]].rev ^= 1;Tree[Tree[index].son[1]].rev ^= 1;Tree[index].rev = 0;}if (Tree[index].add) {Tree[Tree[index].son[0]].val += Tree[index].add;Tree[Tree[index].son[1]].val += Tree[index].add;Tree[Tree[index].son[0]].add += Tree[index].add;Tree[Tree[index].son[1]].add += Tree[index].add;Tree[Tree[index].son[0]].Min += Tree[index].add;Tree[Tree[index].son[1]].Min += Tree[index].add;Tree[index].add = 0;}}inline void update(int index) {Tree[index].size = Tree[Tree[index].son[0]].size + Tree[Tree[index].son[1]].size + 1;Tree[index].Min = Tree[index].val;if (Tree[index].son[0]) Tree[index].Min = min(Tree[index].Min,Tree[Tree[index].son[0]].Min);if (Tree[index].son[1]) Tree[index].Min = min(Tree[index].Min,Tree[Tree[index].son[1]].Min);}inline void splay(int x,int pos) {int f;for (f = Tree[x].fa; (f = Tree[x].fa) != pos; rotate(x)) {if (Tree[f].fa != pos) rotate(get(f) == get(x) ? (f) : (x));}if (!pos) root = x;}inline void rotate(int x) {int f = Tree[x].fa,g = Tree[f].fa,tmpx = get(x),tmpf = get(f);pushdown(f); pushdown(x);if (!f) return;Tree[f].son[tmpx] = Tree[x].son[tmpx^1];if (Tree[x].son[tmpx^1]) Tree[Tree[x].son[tmpx^1]].fa = f;Tree[x].son[tmpx^1] = f;Tree[f].fa = x;Tree[x].fa = g;if (g) Tree[g].son[tmpf] = x;update(f);update(x);}inline void Insert(int p,int val) {int x = query_pos(p),y = query_pos(p+1);splay(x,0); splay(y,root);new_node(++total,val,Tree[root].son[1]);Tree[Tree[root].son[1]].son[0] = total;update(Tree[root].son[1]);update(root); } inline void erase(int p) {int x = query_pos(p-1),y = query_pos(p+1);splay(x,0); splay(y,root);Tree[Tree[root].son[1]].son[0] = 0;update(Tree[root].son[1]);update(root);}inline void add(int l,int r,int v) {int x = query_pos(l-1),y = query_pos(r+1);splay(x,0); splay(y,root);Tree[Tree[Tree[root].son[1]].son[0]].val += v;Tree[Tree[Tree[root].son[1]].son[0]].add += v;Tree[Tree[Tree[root].son[1]].son[0]].Min += v;update(Tree[root].son[1]);update(root);}inline void reverse(int l,int r) {int x = query_pos(l-1),y = query_pos(r+1);splay(x,0); splay(y,root);Tree[Tree[Tree[root].son[1]].son[0]].rev ^= 1;}inline int query_min(int l,int r) {int x = query_pos(l-1),y = query_pos(r+1);splay(x,0); splay(y,root);return Tree[Tree[Tree[root].son[1]].son[0]].Min;}inline void revolve(int l,int r,int t) {int x = query_pos(r-t),y = query_pos(r+1);splay(x,0); splay(y,root);int tmp = Tree[Tree[root].son[1]].son[0];Tree[Tree[root].son[1]].son[0] = 0;update(Tree[root].son[1]);update(root);x = query_pos(l-1); y = query_pos(l);splay(x,0); splay(y,root);Tree[Tree[root].son[1]].son[0] = tmp;Tree[tmp].fa = Tree[root].son[1];update(Tree[root].son[1]);update(root);} } T;int main() {read(N);T.root = T.total = 1;for (i = 2; i <= N + 1; i++) read(a[i]);a[1] = a[N+2] = INF;T.build(1,1,N+2);read(M);while (M--) {cin >> opt;if (opt[0] == 'A') {read(x); read(y); read(d); if (x > y) swap(x,y);T.add(x+1,y+1,d);} else if (opt[0] == 'R' && opt[1] == 'E' && opt[2] == 'V' && opt[3] == 'E'){read(x); read(y);if (x > y) swap(x,y);T.reverse(x+1,y+1); } else if (opt[0] == 'R' && opt[1] == 'E' && opt[2] == 'V' && opt[3] == 'O') {read(x); read(y); read(t);if (x > y) swap(x,y);t = (t % (y - x + 1) + y - x + 1) % (y - x + 1); if (!t) continue;T.revolve(x+1,y+1,t);} else if (opt[0] == 'I') {read(x); read(P);T.Insert(x+1,P);} else if (opt[0] == 'D') {read(x); T.erase(x+1);} else if (opt[0] == 'M') {read(x); read(y);if (x > y) swap(x,y);writeln(T.query_min(x+1,y+1));}}return 0;}

?

轉載于:https://www.cnblogs.com/evenbao/p/9196411.html

總結

以上是生活随笔為你收集整理的【POJ 3580】 SuperMemo的全部內容，希望文章能夠幫你解決所遇到的問題。

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