hdu 4288 线段树+离线处理

xiaoxiao2021-04-18  58

hdu 4288

题意 给你类似一个升序的set结构 add就是加入一个数 del就是删除一个数 sum就是把所有%5=3的位置的数求和

这题我们怎么入手呢?以前做过一道类似的树状数组开55个的题 这个题其实大同小异 就是对sum数组表示%5的值我们开个sum[5]

那么你既然是升序的 我每次add 左边的数一定等于sum[i] 主要是右边的数如何确定 我们知道i = x + cnt(cnt为左子树的点个数)

那么x = i - cnt 于是每次up操作我们爸爸的sum等于 左子树的sum + 右子树 (i - cnt%5 + 5) %5 

所以up就是这样

由于数值很大 所以我们要离散化

这是我的代码

#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <queue> #include <stack> #include <queue> #include <iostream> #include <sstream> #include <set> using namespace std; #define dbg(x) ; //cout<<#x<<" = "<< (x)<< endl const int MAX_N = 1e5+6; long long sum[MAX_N<<2][5]; long long a[MAX_N],b[MAX_N],num[MAX_N<<2]; int q[MAX_N]; char ch[10]; void up(int rt){ num[rt] = num[rt<<1]+num[rt<<1|1]; for(int i = 0;i<5;++i){ sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][((i-num[rt<<1]%5+5)%5)]; } } void update(int rt,int l,int r,int x,int key){ if(l==r){ sum[rt][1] = x? 0:b[key]; num[rt] = !x; return ; } int mid = (l+r)>>1; if(key<=mid) update(rt<<1,l,mid,x,key); else update(rt<<1|1,mid+1,r,x,key); up(rt); } int init(int m){ int top = 0; for(int i = 1;i<=m;i++){ scanf("%s",ch); if(ch[0]=='a'){ q[i] = 0; scanf("%lld",&a[i]); b[++top] = a[i]; } else if(ch[0]=='d'){ q[i] = 1; scanf("%lld",&a[i]); } else { q[i] = 2; } } sort(b+1,b+1+top); memset(num,0,sizeof(num)); memset(sum,0,sizeof(sum)); return top; } int main(){ int key,n,m; while(~scanf("%d",&m)){ n = init(m); for(int i = 1;i<=m;++i){ if(q[i]==0){ int xb = lower_bound(b+1,b+1+n,a[i])-b; update(1,1,n,0,xb); } else if(q[i]==1){ int xb = lower_bound(b+1,b+1+n,a[i])-b; update(1,1,n,1,xb); } else printf("%lld\n",sum[1][3]); } } return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-4820336.html

最新回复(0)