HDU 4288 Coder(12年成都网络赛-线段树)
题意:
维护一个有序数列{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)。
[cpp]
#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("%I64d\n",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;
}
补充:软件开发 , C++ ,