法一：暴力！
让干什么就干什么，那么久需要可持久化线段树了。
但是空间好紧。怎么破？
不down标记好了！
每个点维护sum和add两个信息，sum是这段真实的和，add是这段整体加了多少，如果这段区间被完全包含，返回sum，否则加上add * 询问落在这段区间的长度再递归回答。
怎么还是MLE？
麻辣鸡指针好像8字节，所以改成数组的就过了。。。
#include#include #include #include #include using namespace std;template Q &read(Q &x) { static char c, f; for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1; for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0'; if(f) x = -x; return x;}template Q read() { static Q x; read(x); return x;}typedef long long LL;const int N = 100000 + 10;struct Node *pis;struct Node { LL sum, add; Node *ch[2]; Node *modify(int l, int r, int L, int R, LL d) { Node *o = new Node(*this); if(L <= l && r <= R) { o->add += d; o->sum += (r - l + 1) * d; return o; } int mid = (l + r) >> 1; if(L <= mid) o->ch[0] = ch[0]->modify(l, mid, L, R, d); if(mid < R) o->ch[1] = ch[1]->modify(mid + 1, r, L, R, d); o->sum = o->ch[0]->sum + o->ch[1]->sum + o->add * (r - l + 1); return o; } LL query(int l, int r, int L, int R) { if(L <= l && r <= R) return sum; int mid = (l + r) >> 1; LL res = (min(R, r) - max(L, l) + 1) * add; if(L <= mid) res += ch[0]->query(l, mid, L, R); if(mid < R) res += ch[1]->query(mid + 1, r, L, R); return res; } void *operator new(size_t) { return pis++; }}pool[1000000 + 10], *root[N];void build(Node *&o, int l, int r) { o = new Node, o->add = 0; if(l == r) return read(o->sum), void(); int mid = (l + r) >> 1; build(o->ch[0], l, mid); build(o->ch[1], mid + 1, r); o->sum = o->ch[0]->sum + o->ch[1]->sum;}int main() {#ifdef DEBUG freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int n, m, cur; char opt[10]; while(scanf("%d%d", &n, &m) == 2) { cur = 0, pis = pool; build(root[cur], 1, n); while(m--) { if(m == 1) { int debug = 1; } scanf("%s", opt); if(opt[0] == 'C') { int l, r; LL d; read(l), read(r), read(d); root[cur + 1] = root[cur]->modify(1, n, l, r, d); cur++; }else if(opt[0] == 'Q') { int l, r; read(l), read(r); printf("%I64d\n", root[cur]->query(1, n, l, r)); }else if(opt[0] == 'H') { int l, r, t; read(l), read(r), read(t); printf("%I64d\n", root[t]->query(1, n, l, r)); }else read(cur); } puts(""); } return 0;}
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 template Q &read(Q &x) {10 static char c, f;11 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1;12 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';13 if(f) x = -x; return x;14 }15 template Q read() {16 static Q x; read(x); return x;17 }18 19 typedef long long LL;20 const int N = 4000000 + 10;21 22 int ch[N][2], tot, root[N];23 LL sum[N], add[N];24 25 int modify(int s, int l, int r, int L, int R, LL d) {26 int x = tot++;27 sum[x] = sum[s];28 add[x] = add[s];29 ch[x][0] = ch[s][0];30 ch[x][1] = ch[s][1];31 32 if(L <= l && r <= R) {33 add[x] += d;34 sum[x] += (r - l + 1) * d;35 }else {36 int mid = (l + r) >> 1;37 if(L <= mid) ch[x][0] = modify(ch[s][0], l, mid, L, R, d);38 if(mid < R) ch[x][1] = modify(ch[s][1], mid + 1, r, L, R, d);39 sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + add[x] * (r - l + 1);40 }41 return x;42 }43 44 LL query(int s, int l, int r, int L, int R) {45 if(L <= l && r <= R) return sum[s];46 int mid = (l + r) >> 1;47 LL res = (min(R, r) - max(L, l) + 1) * add[s];48 if(L <= mid) res += query(ch[s][0], l, mid, L, R);49 if(mid < R) res += query(ch[s][1], mid + 1, r, L, R);50 return res;51 }52 53 void build(int &s, int l, int r) {54 s = tot++, add[s] = 0;55 if(l == r) return read(sum[s]), void();56 int mid = (l + r) >> 1;57 build(ch[s][0], l, mid);58 build(ch[s][1], mid + 1, r);59 sum[s] = sum[ch[s][0]] + sum[ch[s][1]];60 }61 62 int main() {63 #ifdef DEBUG64 freopen("in.txt", "r", stdin);65 freopen("out.txt", "w", stdout);66 #endif67 68 int n, m, cur;69 char opt[10];70 while(scanf("%d%d", &n, &m) == 2) {71 cur = tot = 0;72 build(root[cur], 1, n);73 while(m--) {74 if(m == 1) {75 int debug = 1;76 }77 scanf("%s", opt);78 if(opt[0] == 'C') {79 int l, r; LL d;80 read(l), read(r), read(d);81 root[cur + 1] = modify(root[cur], 1, n, l, r, d);82 cur++;83 }else if(opt[0] == 'Q') {84 int l, r; read(l), read(r);85 printf("%I64d\n", query(root[cur], 1, n, l, r));86 }else if(opt[0] == 'H') {87 int l, r, t; read(l), read(r), read(t);88 printf("%I64d\n", query(root[t], 1, n, l, r));89 }else read(cur);90 }91 // puts("");92 }93 94 return 0;95 }
法二：离线！
主要需要处理H操作。
在第一遍读入数据的时候维护一个pos[]数组，表示当前第i个版本是由pos[i]这个C操作创建的。
然后碰到H就把它挂在pos[t]上就可以，第二遍处理的时候直接回答。
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 template Q &read(Q &x) { 10 static char c, f; 11 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1; 12 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0'; 13 if(f) x = -x; return x; 14 } 15 template Q read() { 16 static Q x; read(x); return x; 17 } 18 19 typedef long long LL; 20 const int N = 100000 + 10; 21 22 int n, m; 23 class SegementTree { 24 private: 25 LL sum[N * 4], tag[N * 4]; 26 27 #define mid ((l + r) >> 1) 28 #define ls s << 1, l, mid 29 #define rs s << 1 | 1, mid + 1, r 30 31 void add_tag(int s, int l, int r, LL d) { 32 tag[s] += d; 33 sum[s] += (r - l + 1) * d; 34 } 35 36 void down(int s, int l, int r) { 37 if(tag[s]) { 38 add_tag(ls, tag[s]); 39 add_tag(rs, tag[s]); 40 tag[s] = 0; 41 } 42 } 43 44 int lft, rgt; 45 LL w; 46 47 void modify(int s, int l, int r) { 48 if(lft <= l && r <= rgt) return add_tag(s, l, r, w); 49 down(s, l, r); 50 if(lft <= mid) modify(ls); 51 if(mid < rgt) modify(rs); 52 sum[s] = sum[s << 1] + sum[s << 1 | 1]; 53 } 54 55 LL query(int s, int l, int r) { 56 if(lft <= l && r <= rgt) return sum[s]; 57 down(s, l, r); 58 if(rgt <= mid) return query(ls); 59 if(mid < lft) return query(rs); 60 return query(ls) + query(rs); 61 } 62 63 public: 64 void build(int s, int l, int r) { 65 tag[s] = 0; 66 if(l == r) return read(sum[s]), void(); 67 build(ls), build(rs); 68 sum[s] = sum[s << 1] + sum[s << 1 | 1]; 69 } 70 #undef mid 71 #undef ls 72 #undef rs 73 74 void Modify(int l, int r, LL w) { 75 lft = l, rgt = r, this->w = w; 76 modify(1, 1, n); 77 } 78 LL Query(int l, int r) { 79 lft = l, rgt = r; 80 return query(1, 1, n); 81 } 82 }seg; 83 84 struct operation { 85 char tp; 86 int l, r; 87 LL d; 88 }opt[N]; 89 90 #include 91 stack stk; 92 93 #include 94 vector G[N]; 95 96 int pos[N]; 97 LL ans[N]; 98 99 int main() {100 #ifdef DEBUG101 freopen("in.txt", "r", stdin);102 freopen("out.txt", "w", stdout);103 #endif104 105 char s[10];106 while(scanf("%d%d", &n, &m) == 2) {107 seg.build(1, 1, n);108 int cur = 0;109 for(int i = 0; i < m; i++) {110 scanf("%s", s);111 opt[i].tp = s[0];112 if(s[0] == 'C') {113 read(opt[i].l), read(opt[i].r), read(opt[i].d);114 pos[++cur] = i;115 }else if(s[0] == 'Q') {116 read(opt[i].l), read(opt[i].r);117 }else if(s[0] == 'H') {118 read(opt[i].l), read(opt[i].r), read(opt[i].d);119 if(!opt[i].d) ans[i] = seg.Query(opt[i].l, opt[i].r);120 else G[pos[opt[i].d]].push_back(i);121 }else cur = read(opt[i].d);122 }123 124 cur = 0;125 for(int i = 0; i < m; i++) {126 if(opt[i].tp == 'C') {127 seg.Modify(opt[i].l, opt[i].r, opt[i].d);128 for(unsigned j = 0; j < G[i].size(); j++) {129 int k = G[i][j];130 ans[k] = seg.Query(opt[k].l, opt[k].r);131 }132 ++cur;133 stk.push(i);134 }else if(opt[i].tp == 'Q') {135 ans[i] = seg.Query(opt[i].l, opt[i].r);136 }else if(opt[i].tp == 'B') {137 while(cur > opt[i].d) {138 int k = stk.top(); stk.pop();139 seg.Modify(opt[k].l, opt[k].r, -opt[k].d);140 cur--;141 }142 }143 }144 145 for(int i = 0; i < m; i++) {146 if(opt[i].tp == 'Q' || opt[i].tp == 'H') {147 printf("%I64d\n", ans[i]);148 }149 }150 }151 152 return 0;153 }