这个题我是用线段树来做的，结果居然是超时。。。后来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;
}