The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

关于浙大月赛B题 快速寻找第k小数...

这个题我是用线段树来做的,结果居然是超时。。。后来foreverlin同学告诉我他用树状数组过的,但我记得树状数组能解决的问题,线段树一定能解决,而且线段树的复杂度是logL级别,为什么我会超时呢?还请各位大牛指点。。。
我的代码如下:

#include<iostream>
#include
<cstdio>
#include
<cstring>
#include
<cmath>
using namespace std;
#define MAX 300001
int a[MAX];


struct node
{
    
    
int left;
    
int right;
    
int level;
    
int cnt;
    node 
*lchild;
    node 
*rchild;
}
dotset[MAX];
int cou;
node 
*Newnode()
{
    
    node 
*p=&dotset[cou];
    cou
++;
    p
->level=0;
    p
->cnt=0;
    p
->left=0;
    p
->right=0;
    p
->lchild=NULL;
    p
->rchild=NULL;
    
return p;
}



void Build(node *&tree,int left,int right)
{
    tree
=Newnode();
    tree
->left=left;
    tree
->right=right;
    
if(left==right)
    
{
        
return;
    }

    
int mid=(left+right)>>1;
    Build(tree
->lchild,left,mid);
    Build(tree
->rchild,mid+1,right);
}

int p=1;
void Insert(node *tree,int k,int num)
{
    tree
->cnt+=num;
    
if(tree->left==tree->right)
    
{
        tree
->level=p;
        p
++;
        
return;
    }

    
int mid=(tree->left+tree->right)>>1;
    
if(k>mid)
        Insert(tree
->rchild,k,num);
    
else
        Insert(tree
->lchild,k,num);
}

void Insert2(node *tree,int k,int num)
{
    tree
->cnt-=a[k];
    tree
->cnt+=num;
    
if(tree->left==tree->right)
    
{
        
return;
    }

    
if(k>(tree->left+tree->right)>>1)
        Insert2(tree
->rchild,k,num);
    
else
        Insert2(tree
->lchild,k,num);
}


int Query(node *tree,int k)
{
    
if(tree->left==tree->right)
        
return tree->level;
    
int t=tree->lchild->cnt;
    
if(k<=t)
        Query(tree
->lchild,k);
    
else 
        Query(tree
->rchild,k-t);
}



int main()
{

    
int n;
    
int q;
    node 
*root;
    
while(scanf("%d",&n)!=EOF)
    
{
        cou
=0;
        Build(root,
1,n);
        p
=1;
        
int i;
        
for(i=1;i<=n;i++)
        
{
            
int t;
            scanf(
"%d",&a[i]);
            Insert(root,i,a[i]);
        }

        scanf(
"%d",&q);
        
for(i=1;i<=q;i++)
        
{
            
int t;
            
char s;
            cin.ignore();
            scanf(
"%c",&s);
            
if(s=='q')
            
{
                scanf(
"%d",&t);
                printf(
"%d\n",Query(root,t));
            }

            
else if(s=='p')
            
{
                
int a1,b1;
                scanf(
"%d%d",&a1,&b1);
                Insert2(root,a1,b1);
                a[a1]
=b1;
            }




        }

        
    }

    
return 0;
}

顺便发几句牢骚,为啥我做浙大的题总是不顺呢(当然其实我也是第二次做浙大的比赛)。。。浙大好像总喜欢出极限数据,即使算法对了,也不让我们快速地通过,总是要优化到最佳才行。这样做好处是比赛的时候实力会更过硬一些吧,毕竟可以说 我们连浙大那么BT的数据都过了,算法肯定是最好的了。。。下次提前做好心理准备吧。。。

下午花了一个小时 终于弄懂了树状数组,总算把这题过了,感觉树状数组实现起来比线段树容易得多,效率也高得多,非常实用。
#include<iostream>
#include
<cmath>
#include
<algorithm>
#include
<cstring>
using namespace std;

int n,q;
int a[100001],c[100001];

int lowbit(int k)
{
    
return k&(k^(k-1));
}


void update(int x,int num)
{
    
while(x<=n)
    
{
        c[x]
+=num;
        x
+=lowbit(x);     
    }
 
}
    
int query(int x)
{
    
int sum=0;
    
while(x>0)
    
{
        sum
+=c[x];
        x
-=lowbit(x);    
    }

    
return sum;      
}


int find(int t)
{

    
int l=1;
    
int r=n;
    
int min;
    
    
while(l<r)
    
{
        
int mid=(l+r)>>1;
        
if(query(mid)>=t&&query(mid-1)<t)
            
return mid;
        
else if(query(mid)>=t)
            r
=mid-1;
        
else 
            l
=mid+1;
    }

    
return r;//刚好为最后一个查找点
}



int main()
{
    
int i,j;
    
int t;
    
char s[2];
    
while(scanf("%d",&n)!=EOF)
    
{

        
for(i=1;i<=n;i++)c[i]=0;
        
for(i=1;i<=n;i++)
        
{

            scanf(
"%d",&a[i]);
            update(i,a[i]);
        }

        scanf(
"%d",&q);
        
while(q--)
        
{
            scanf(
"%s",s);
            
if(s[0]=='q')
            
{

                scanf(
"%d",&t);
                printf(
"%d\n",find(t));
            }

            
else 
            
{
                
int t1,t2;
                scanf(
"%d%d",&t1,&t2);
                update(t1,
-a[t1]);
                a[t1]
=t2;
                update(t1,a[t1]);
            }


        }

        
    }

    
return 0;
}



posted on 2009-12-15 00:36 abilitytao 阅读(1810) 评论(7)  编辑 收藏 引用

评论

# re: 关于浙大月赛B题 快速寻找第k小数... 2009-12-17 11:19 diwayou

我有个问题纳闷,你用了一堆的C++头文件,程序里用的全是C的函数,why  回复  更多评论   

# re: 关于浙大月赛B题 快速寻找第k小数... 2009-12-17 12:40 abilitytao

@diwayou
我用的就是C的 --!  回复  更多评论   

# re: 关于浙大月赛B题 快速寻找第k小数... 2009-12-17 17:00 wxq

你整的太复杂了...没那个必要!  回复  更多评论   

# re: 关于浙大月赛B题 快速寻找第k小数... 2009-12-21 00:26 abilitytao

@wxq
请问有什么更好的方法吗?请指教:-)  回复  更多评论   

# re: 关于浙大月赛B题 快速寻找第k小数... 2009-12-27 23:41 MasterLuo

树状数组与线段树应该都是可以过的。不过可以用树状数组的地方就没必要用线段树了。  回复  更多评论   

# re: 关于浙大月赛B题 快速寻找第k小数... 2011-05-03 17:54 seeyou

呃~~能写点注释么?这样看不明白呀,谢谢啦  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理