当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,