频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 4339 Query 线段树 多校联合赛(四) 第九题
2012-08-05 11:17:00           
收藏   我要投稿
比赛的时候一顿wa啊!好伤
先将两个数组对位比较,相等为1,否则为零,把这个01数组挂在线段树的末节点上,然后就是向上更新啦
线段树,线段有两个属性,ml存放该线段左边最大连续长度,mr存放该线段右边最大连续长度,在向上更新的时候是a[i].mr=a[i*2+1].mr;    a[i].ml=a[i*2].ml;  这个好理解吧,但如果左孩子是全连续(这条线段的长度等于左连续长度等于右连续长度),a[i].ml=a[i*2].ml(其实这个值就是这条线段的长度)+a[i*2+1].ml;  右孩子是全连续的情况同理
insert比较好弄,就是往那个末节点改成1或0,然后同理向上更新
query的时候,如果查询x,就找到以x为右节点的线段,因为值查询x右边的连续个数,找到那条线段之后,向上加右边线段的ml(左连续值),当右边线段不是全连续的时候,再向上就不加值了,因为左连续已经断了
程序中的query全写成querry了,好囧
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<string.h> 
using namespace std; 
#define N 1000005 
struct node{ 
    int l,r,ml,mr; 
}a[N*3]; 
char ca[N],cb[N]; 
int sum,num[N],x,sign; 
void build(int i,int left,int right){ 
    a[i].l=left; 
    a[i].r=right; 
    if(a[i].l==a[i].r) { 
        if(num[a[i].l]==1) 
            a[i].ml=a[i].mr=1; 
        else 
            a[i].ml=a[i].mr=0; 
        return ; 
    } 
    int mid=(a[i].l+a[i].r)>>1; 
    build(i*2,left,mid); 
    build(i*2+1,mid+1,right); 
    if(a[i*2+1].r-a[i*2+1].l+1==a[i*2+1].ml) 
        a[i].mr=a[i*2].mr+a[i*2+1].ml; 
    else 
        a[i].mr=a[i*2+1].mr; 
    if(a[i*2].r-a[i*2].l+1==a[i*2].ml) 
        a[i].ml=a[i*2].ml+a[i*2+1].ml; 
    else 
        a[i].ml=a[i*2].ml; 

void insert(int i,int x,int y){ 
    if(a[i].l==a[i].r&&a[i].l==x){ 
        a[i].ml=a[i].mr=y; 
        return ; 
    } 
    int mid=(a[i].l+a[i].r)>>1; 
    if(x<=mid) insert(i*2,x,y); 
    else insert(i*2+1,x,y); 
    if(a[i*2+1].r-a[i*2+1].l+1==a[i*2+1].ml) 
        a[i].mr=a[i*2].mr+a[i*2+1].ml; 
    else 
        a[i].mr=a[i*2+1].mr; 
    if(a[i*2].r-a[i*2].l+1==a[i*2].ml) 
        a[i].ml=a[i*2].ml+a[i*2+1].ml; 
    else 
        a[i].ml=a[i*2].ml; 

void querry(int i,int x){ 
    if(a[i].r==x){ 
        sum=1; 
        return ; 
    } 
    int mid=(a[i].l+a[i].r)>>1; 
    if(x<=mid) querry(i*2,x); 
    else querry(i*2+1,x); 
    if(a[i*2].mr!=0&&a[i*2+1].ml!=0&&sign==0&&x<a[i*2+1].l)//如果要查询的点到了右边线段,就不能在加该线段的右面线段了,以为不是一个树枝上的 
        sum+=a[i*2+1].ml; 
    if((a[i*2+1].r-a[i*2+1].l+1)!=a[i*2+1].ml&&x<=a[i*2].r) 
        sign=1; 

int main(){ 
//   freopen("in.txt","r",stdin); 
    int t,pp=1; 
    scanf("%d",&t); 
    while(t--){ 
        printf("Case %d:\n",pp++); 
        scanf("%s%s",ca,cb); 
        int lena=strlen(ca); 
        int lenb=strlen(cb); 
        int len=lena>lenb? lena:lenb; 
        for(int i=0;i<len;i++){ 
            if(ca[i]==cb[i]) 
                num[i]=1; 
            else 
                num[i]=0; 
        } 
        build(1,0,len-1); 
        int q,y,z; 
        char te[2]; 
        scanf("%d",&q); 
        while(q--){ 
            scanf("%d",&z); 
            if(z==2){ 
                scanf("%d",&x); 
                if(num[x]==0){ 
                    printf("0\n"); 
                    continue; 
                } www.2cto.com
                sum=0,sign=0; 
                querry(1,x); 
 
                printf("%d\n",sum); 
            }else{ 
                scanf("%d%d%s",&x,&y,te); 
                if(x==1){ 
                    ca[y]=te[0]; 
                    if(ca[y]==cb[y]) num[y]=1; 
                    else num[y]=0; 
                } www.2cto.com
                else{ 
                    cb[y]=te[0]; 
                    if(ca[y]==cb[y]) num[y]=1; 
                    else num[y]=0; 
                } 
                insert(1,y,num[y]); 
            } 
        } 
    } 
    return 0; 

作者:youngyangyang04
点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 第九
上一篇:Zoj 3524 Crazy Shopping (DP_完全背包)
下一篇:hdu 4336 Card Collector 容斥原理 多校联合赛(四) 第六题
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站