# The Fourth Dimension Space

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

#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;
}

#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 阅读(1748) 评论(7)  编辑 收藏 引用

@diwayou

@wxq