首页 > 代码库 > POJ3468--A Simple Problem with Integers（Splay Tree）
POJ3468--A Simple Problem with Integers（Splay Tree）
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N = 100010;int sz[N], ch[N][2], pre[N];int a[N];ll sum[N], add[N], key[N];int root, tot;void new_node(int &o, int fa, int k) { o = ++tot; sz[o] = 1; ch[o][0] = ch[o][1] = 0; pre[o] = fa; sum[o] = key[o] = k; add[o] = 0;}void push_up(int o) { sum[o] = sum[ch[o][0]] + sum[ch[o][1]] + key[o]; sz[o] = sz[ch[o][0]] + sz[ch[o][1]] + 1; // +1 !!}void update(int o, int v) { if (!o) return ; add[o] += v; key[o] += v; sum[o] += (ll)sz[o]*v;}void push_down(int o) { if (add[o]) { update(ch[o][1], add[o]); update(ch[o][0], add[o]); add[o] = 0; }}void build(int &o, int l, int r, int fa) { if (l > r) return; int mid = (l+r) >> 1; new_node(o, fa, a[mid]); build(ch[o][0], l, mid-1, o); build(ch[o][1], mid+1, r, o); push_up(o);}void init(int n) { root = tot = 0; sz[0] = ch[0][0] = ch[0][1] = pre[0] = 0; sum[0] = add[0] = key[0] = 0; new_node(root, 0, -1); new_node(ch[root][1], root, -1); build(ch[ch[root][1]][0], 1, n, ch[root][1]); push_up(ch[root][1]); push_up(root);}void rotate(int o, int d) { // 0:left 1:right int fa = pre[o]; push_down(fa); push_down(o); ch[fa][!d] = ch[o][d]; pre[ch[o][d]] = fa; if (pre[fa]) ch[pre[fa]][ch[pre[fa]][1]==fa] = o; pre[o] = pre[fa]; ch[o][d] = fa; pre[fa] = o; push_up(fa);}void splay(int o, int goal) { push_down(o); while (pre[o] != goal) { if (pre[pre[o]] == goal) { rotate(o, ch[pre[o]][0] == o); } else { int fa = pre[o]; int d = (ch[pre[fa]][0] == fa); if (ch[fa][d] == o) { rotate(o, !d); rotate(o, d); } else { rotate(fa, d); rotate(o, d); } } } push_up(o); if (goal == 0) root = o;}int get_kth(int o, int k) { push_down(o); //!! int t = sz[ch[o][0]] + 1; if (t == k) return o; if (t > k) return get_kth(ch[o][0], k); return get_kth(ch[o][1], k-t);}ll query(int l, int r) { splay(get_kth(root, l), 0); splay(get_kth(root, r+2), root); return sum[ ch[ch[root][1]][0] ];}void Add(int l, int r, int v) { splay(get_kth(root, l), 0); splay(get_kth(root, r+2), root); update(ch[ch[root][1]][0], v); push_up(ch[root][1]); push_up(root);}int main() { //freopen("in.txt", "r", stdin); int n, q; while (~scanf("%d%d", &n, &q) && n) { for (int i = 1; i <= n; ++i) scanf("%d", a+i); init(n); char op[2]; int x, y, z; while (q--) { scanf("%s%d%d", op, &x, &y); if (*op == ‘Q‘) { printf("%lld\n", query(x, y)); } else { scanf("%d", &z); Add(x, y, z); } } } return 0;}
POJ3468--A Simple Problem with Integers（Splay Tree）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。