HDU4288 Coder(线段树)

注意添加到集合中的数是升序的,先将数据读入,再离散化。

sum[rt][i]表示此节点的区域位置对5取模为i的数的和,删除一个数则右边的数循环左移一位,添加一个数则右边数循环右移一位,相当于循环左移4位,线段树与树状数组结合,树状数组确定位置。

 le[rt]表示左移的位数,区间更新懒惰标记

#include <iostream>
#include <cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100008;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL; int C[N];//注意初始化n
inline int lowbit(int x){
return x&-x;
}
void add(int x, int val, int n){//将第x个数增加val,从1计数
for(int i=x;i<=n;i+=lowbit(i)){
C[i] += val;
}
}
int getsum(int x){//求1到x的和
int ret = 0;
for(int i=x;i>0;i-=lowbit(i)){
ret+=C[i];
}
return ret;
} LL sum[N<<2][5];
int le[N<<2];
LL a[N], b[N]; void PushDown(int l, int r, int rt){
le[rt] %= 5;
if(le[rt]){
if(l < r){
le[rt<<1] = (le[rt] + le[rt<<1]) % 5;
le[rt<<1|1] = (le[rt] + le[rt<<1 | 1]) % 5;
} int t = le[rt];
while(t--){
LL tp = sum[rt][0];
for(int i = 0; i <= 3; i++){
sum[rt][i] = sum[rt][i + 1];
}
sum[rt][4] = tp;
} le[rt] = 0;
}
} void PushUp(int l, int r, int rt){
if(l < r){
int m = (l + r)>>1;
if(le[rt<<1]){//注意
PushDown(lson);
}
if(le[rt << 1 |1]){
PushDown(rson);
}
for(int i = 0; i < 5; i++){
sum[rt][i] = sum[rt <<1 ][i] + sum[rt<<1|1][i];
}
}
}
void build(int l,int r,int rt){
if(l == r){
for(int i = 0 ; i < 5; i++){
sum[rt][i] = 0;
}
le[rt] = 0;
return ;
}
int m = (l + r)>>1;
build(lson);
build(rson);
PushUp(l, r, rt);
} void update(int x, int rdx, int val, int l, int r, int rt){\
PushDown(l, r, rt);
if(l == r){
if(rdx == -1){
for(int i = 0; i < 5; i++){
sum[rt][i] = 0;
}
}else{
sum[rt][rdx] = val;
}
le[rt] = 0; }else{ int m = (l + r)>>1;
if(x <= m){
update(x, rdx, val, lson);
}else{
update(x, rdx, val, rson);
} }
PushUp(l, r, rt);
} void shift(int p, int a, int b, int l , int r, int rt){
PushDown(l ,r , rt);
if(a <= l && b >= r){
le[rt] += p;
PushDown(l, r, rt);
}else{ int m = (l + r)>>1;
if(a <= m){
shift(p, a, b, lson);
}
if(b > m){
shift(p, a, b, rson);
} }
PushUp(l, r, rt);
} int main(){
int n;
while(~scanf("%d", &n)){
memset(C, 0, sizeof(int) * (n + 2));
char str[10]; int cnt = 0;
for(int i = 1; i <= n; i++){
scanf("%s", str);
LL x;
if(str[0] == 'a'){
scanf("%I64d", &x);
a[i] = x << 1|1;
b[cnt++] = x;
}else if(str[0] == 'd'){
scanf("%I64d", &x);
a[i] = x << 1;
}else{
a[i] = -1;
}
}
sort(b, b + cnt);
cnt = unique(b, b + cnt) - b;
build(1, cnt, 1);
for(int i = 1; i <= n; i++){
if(a[i] == -1){
PushDown(1, cnt, 1);
printf("%I64d\n", sum[1][3]);
}else if(a[i] & 1){
a[i] >>= 1;
int pos= lower_bound(b, b + cnt, a[i]) - b + 1;
int rdx = getsum(pos) + 1;
add(pos, 1, cnt); update(pos, rdx % 5, a[i], 1, cnt, 1);
if(pos + 1 <= cnt){
shift(4, pos + 1, cnt, 1, cnt, 1);
}
}else{
a[i] >>= 1;
int pos= lower_bound(b, b + cnt, a[i]) - b + 1;
add(pos, -1, cnt);
update(pos, -1, 0, 1, cnt, 1);
shift(1, pos +1, cnt, 1, cnt, 1);
}
}
}
return 0;
}

为什么我线段树总是写不好,总是要好长时间的debug……

上一篇:DedeCMS清空删除所有文档后新建文档信息ID从1开始


下一篇:大数据Hadoop集群搭建实践记录