HDU 4288 Coder（12年成都网络赛-离线线段树）

68 阅读 0 评论 45 点赞

我是靠谱客的博主失眠小土豆，最近开发中收集的这篇文章主要介绍HDU 4288 Coder（12年成都网络赛-离线线段树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：Click here~~

题意：

维护一个有序数列{An}，有三种操作：

1、添加一个元素。

2、删除一个元素。

3、求数列中下标%5 = 3的值的和。

解题思路：

看的各种题解，今天终于弄懂了。

由于线段树中不支持添加、删除操作，所以题解写的是用离线做法。

我们来看它是如何解决添加、删除的问题的。

首先将所有出现过的数记录下来，然后排序去重，最后根据去重结果建树，然后每个操作数都会对应线段树中的一个点。

遇到添加、删除操作的时候，只要把那个节点的值改变，然后将它对下标的影响处理好就可以。

那么如何处理这些操作对下标的影响呢？

现在我们考虑一个父区间，假设它的左右子区间已经更新完毕。

显然，左区间中下标%5的情况与父区间中下标%5的情况完全相同；

可是，右区间中却不一定相同，因为右区间中的下标是以 mid 当作 1 开始的。

那么，只要我们知道左区间中有效元素的个数 cnt，我们就能知道右区间中的下标 i 在父区间中对应的下标为 i+cnt。

所以，虽然我们最终要的只是总区间中下标%5 = 3的和。但是在更新时我们需要知道右区间%5的所有情况。

于是我们要在线段树的每个节点开一个 sum[5] 和一个 cnt，分别记录这个节点中下标%5的5种情况的和与有效元素的个数。

而查询时，直接访问总区间的 sum[3] 即可。

如此，题目便可解了。复杂度O(M logN logN)。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100003
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)
typedef __int64 LL;
int num[N],x[N];
//num记录对应操作的数，x记录对应的区间存的数
int add;
struct Tnode
{
int l,r,cnt;
LL sum[5];
}T[N<<2];
void Build(int u,int l,int r)
{
T[u].l = l , T[u].r = r;
if(l == r-1)
{
memset(T[u].sum,0,sizeof(T[u].sum));
T[u].cnt = 0;
return ;
}
int mid = MID(l,r);
Build(L(u),l,mid);
Build(R(u),mid,r);
memset(T[u].sum,0,sizeof(T[u].sum));
T[u].cnt = 0;
}
void Updata(int u,int l,int r)
{
add ? ++T[u].cnt : --T[u].cnt;
if(T[u].l == T[u].r - 1)
{
T[u].sum[1] = add * x[l-1];
return ;
}
int mid = MID(T[u].l,T[u].r);
if(l >= mid)
Updata(R(u),l,r);
else
Updata(L(u),l,r);
for(int i=0;i<5;i++)
{
int j = (i + T[L(u)].cnt) % 5;
T[u].sum[j] = T[L(u)].sum[j] + T[R(u)].sum[i];
}
}
int main()
{
int Q;
char cmd[N],ccmd[4];
while(~scanf("%d",&Q))
{
int top = 0;
for(int i=0;i<Q;i++)
{
scanf("%s",ccmd);
cmd[i] = ccmd[0];
if(cmd[i] != 's')
scanf("%d",&num[top++]);
}
memcpy(x,num,sizeof(int)*top);
sort(x,x+top);
int n = unique(x,x+top) - x;
Build(1,1,n+1);
for(int i=0,j=0;i<Q;i++)
{
if(cmd[i] == 's')
{
printf("%I64dn",T[1].sum[3]);
continue;
}
int k = lower_bound(x,x+n,num[j++]) - x + 1;
add = cmd[i] == 'a' ? 1 : 0;
Updata(1,k,k+1);
}
}
return 0;
}