首页 > 代码库 > 离线+线段树 HDU4228
离线+线段树 HDU4228
题目大意：给一个数组a，他的顺序是严格的单调增，然后有如下三个操作
①加入一个val到a数组里面去，加入的位置就是a[i-1]<val<a[i+1]
②删除一个a[i]=val的值
③查询所有下标i%5=3的值
思路：线段树+离线
首先因为线段树中不支持添加、删除操作的，所以只能离线把所有的val离散化以后放到区间里面去。然后关键就是线段树是怎么建立的。
我们知道，每个%5都会有0,1,2,3,4这5个值，然后我们可以通过线段树来维护这5个值。我们首先用sum[5]表示能被5整除的5种求余后不同类型的数的val，然后再用cnt记录当前这个区间里面还存在的数值。接下来我们定义父亲区间，左子区间和右子区间，然后我们发现左子区间的区间范围和父亲区间的是一样的，然后右子区间的范围要发生改变，他的位置改变到如下位置：(i+cnt)%5，其中i表示右子区间的第几个区间，然后cnt表示左子区间的有效的个数。然后我们就这样去维护就好啦。
//看看会不会爆int!数组会不会少了一维！//取物问题一定要小心先手胜利的条件#include <bits/stdc++.h>using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se secondconst int maxn = 1e5 + 5;struct point{ LL sum[5]; int cnt; void init(){ this -> cnt = 0; memset(sum, 0, sizeof(sum)); }}tree[maxn << 2];LL a[maxn];int q;pair<char, LL> ch[maxn];void buildtree(int o, int l, int r){ if (l == r){ tree[o].init(); return ; } int mid = (l + r) / 2; if (l <= mid) buildtree(o << 1, l, mid); if (r > mid) buildtree(o << 1 | 1, mid + 1, r); tree[o].init();}inline void push_up(int o){ tree[o].cnt = tree[o << 1].cnt + tree[o << 1 | 1].cnt;}void display(int o, int l, int r){ printf("o = %d l = %d r = %d\n", o, l, r); for (int i = 0; i < 5; i++) printf("%d ", tree[o].sum[i]); printf("\n");}void update(int o, int l, int r, int pos, bool flag){ if (l == r && l == pos){ if (flag) {tree[o].sum[1] += a[pos]; tree[o].cnt = 1;} else {tree[o].sum[1] -= a[pos]; tree[o].cnt = 0;} return ; } int mid = (l + r) / 2; if (pos <= mid) update(o << 1, l, mid, pos, flag); if (pos > mid) update(o << 1 | 1, mid + 1, r, pos, flag); memset(tree[o].sum, 0, sizeof(tree[o].sum)); for (int i = 0; i < 5; i++){ int j = (i + tree[o << 1].cnt) % 5; tree[o].sum[i] += tree[o << 1].sum[i]; tree[o].sum[j] += tree[o << 1 | 1].sum[i]; } ///display(o, l, r); push_up(o); return ;}int main(){ while (scanf("%d", &q) == 1 && q){ int n = 0; for (int i = 1; i <= q; i++){ char s[4]; LL tmp = -1; scanf("%s", s); if (s[0] == ‘d‘ || s[0] == ‘a‘) scanf("%I64d", &tmp); ch[i] = mk(s[0], tmp); if (s[0] == ‘a‘) a[++n] = tmp; } sort(a + 1, a + 1 + n);///有待商榷 buildtree(1, 1, n); for (int i = 1; i <= q; i++){ pair<char, LL> p = ch[i]; if (p.first == ‘s‘){ printf("%I64d\n", tree[1].sum[3]); continue; } else { int pos = lower_bound(a + 1, a + 1 + n, p.second) - a; update(1, 1, n, pos, p.first == ‘a‘); } } } return 0;}
离线+线段树 HDU4228
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。