hdu 4288 线段树（离散化的离线算法）-白红宇的个人博客

hdu 4288 线段树（离散化的离线算法）

发布日期：2022-03-30 18:18:25 浏览次数：65 分类：博客文章

本文共 1366 字，大约阅读时间需要 4 分钟。

输入描述：

输入第一行有一个n 表示接下来有n个命令

接下来的每一行包括一个修改命令包括一个字符串命令和一个整数或者一个求和命令：

　　（其意思为： add x 将x插入的数组中，del x 从数组中删除，保持数组有序，保证不插入重复的不删除不存在的

　　　 sum 命令表示输出数组中顺序%5==3 的所有元素之和）

输出描述：输出每一个sum命令的结果

输入样例：

add 1

add 2

add 3

add 4

add 5

sum

add 6

del 3

sum

输出样例：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define MAXN 100005struct Seg{    int lift,right;    int num;    long long sum[5];//存放每一段区间中顺序%5的各个值之和    void init_seg(int l,int r){        lift=l,right=r,num=0,memset(sum,0,sizeof(sum));    }} T[MAXN<<2];char cmd[MAXN];int x[MAXN];int ans[MAXN];void pushup(int i){//向上修改sum值    int t1=(i<<1)+1,t2=t1+1;    for(int j=0; j<5; j++)        T[i].sum[j]=T[t1].sum[j];    for(int j=T[t1].num%5,k=0; k<5; k++,j++)        T[i].sum[j%5]+=T[t2].sum[k];}void build(int i,int l,int r){    T[i].init_seg(l,r);    if(l==r)        return;    build((i<<1)+1,l,((l+r)>>1));    build((i+1)<<1,((l+r)>>1)+1,r);}int key,add_del;//add_del==1 添加一个数 add_del==-1删除一个数void update(int i){    if(T[i].lift==T[i].right){        T[i].num^=1;        T[i].sum[0]= add_del==1 ? key : 0;        return;    }    if(ans[(T[i].lift+T[i].right)>>1] >= key)        update((i<<1)+1);    else        update((i+1)<<1);    T[i].num+=add_del;    pushup(i);}int main(){    int n,top;    char ch[10];    while(~scanf("%d",&n)){        for(int i=top=0; i

转载地址：https://www.cnblogs.com/codeloveme/archive/2012/09/18/2690695.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：hdu 3033 分组背包（反分组背包）

下一篇：Scrapy-Redis分布式爬虫小白问题记录

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章