注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【QAQ】【线段树裸题】[Ahoi2009]Seq 维护序列seq  

2014-04-29 21:37:02|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
已经不会写线段树了
标记都忘记了该怎么传QAQ
WA了好久……
感谢GTY神犇的指导
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N = 100000 +100;
 
typedef long long LL;
int n,m,MOD,data[N],ROOT;
int lson[N*2],rson[N*2],Tn,flag[N*2][2];
int tree[N*2];
int max(int a,int b){if(a>b)return a;return b;}
int scan(){
    char cc=' ';int re=0,fh=1;
    while(cc==' '||cc=='\n'||cc=='\r')cc=getchar();
    if(cc=='+'){fh=1;cc=getchar();}
    if(cc=='-'){fh=-1;cc=getchar();}
    while('0'<=cc&&cc<='9'){
        re=re*10+cc-'0';
        cc=getchar();
    }
    return re*fh;
}
void down(int r,int la,int ra){
    if(lson[r]){
        flag[lson[r]][0]=((LL)flag[lson[r]][0]*flag[r][1])%MOD;
        flag[lson[r]][0]=((LL)flag[lson[r]][0]+flag[r][0])%MOD;
        flag[lson[r]][1]=((LL)flag[lson[r]][1]*flag[r][1])%MOD;
         
    }
    if(rson[r]){
        flag[rson[r]][0]=((LL)flag[rson[r]][0]*flag[r][1])%MOD;
        flag[rson[r]][0]=((LL)flag[r][0]+flag[rson[r]][0])%MOD;
        flag[rson[r]][1]=((LL)flag[r][1]*flag[rson[r]][1])%MOD;
    }
    tree[r]=((LL)tree[r]*flag[r][1])%MOD;
    tree[r]=((LL)tree[r]+((LL)flag[r][0]*(ra-la+1))%MOD)%MOD;
    flag[r][0]=0;flag[r][1]=1;
}
int Build(int la,int ra){
    int mid=(la+ra)/2,r=++Tn;
    flag[r][1]=1;
    if(la<ra){
        lson[r]=Build(la,mid);
        rson[r]=Build(mid+1,ra);
        tree[r] = ((LL)tree[lson[r]]+tree[rson[r]])%MOD;
    }else tree[r]=data[la];
    return r;
}
void insert(int ro,int la,int ra,int l,int r,int x,int val){
    int mid=(l+r)/2;down(ro,l,r);
    if(la<=l&&r<=ra){flag[ro][x]=val;down(ro,l,r);return;}
    if(la<=mid)insert(lson[ro],la,ra,l,mid,x,val);
    if(mid+1<=ra)insert(rson[ro],la,ra,mid+1,r,x,val);
    down(lson[ro],l,mid);down(rson[ro],mid+1,r);
    tree[ro]=((LL)tree[lson[ro]]+tree[rson[ro]])%MOD;
}
int ask(int ro,int l,int r,int la,int ra){
    int mid=(l+r)/2;LL re=0;down(ro,l,r);
    if(la<=l&&r<=ra) return tree[ro];
    if(la<=mid) re+=ask(lson[ro],l,mid,la,ra);
    if(mid+1<=ra) re+=ask(rson[ro],mid+1,r,la,ra);
    return (int)(re%MOD);
}
int main(){
    //freopen("input.txt","r",stdin);
    int i,j,a,b,c;
    n=scan();MOD=scan();
    for(i=1;i<=n;i++)
        data[i]=scan();
    ROOT=Build(1,n);
    m=scan();
    flag[0][1]=1;
    for(i=1;i<=m;i++){
        a=scan();
        if(a==1){
            a=scan();b=scan();c=scan();
            insert(ROOT,a,b,1,n,1,c);
        }else if(a==2){
            a=scan();b=scan();c=scan();
            insert(ROOT,a,b,1,n,0,c);
        }else if(a==3){
            a=scan();b=scan();
            printf("%d\n",ask(ROOT,1,n,a,b));
        }
    }
    return 0;
}

  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017