這個(gè)題我是用線段樹來做的，結(jié)果居然是超時(shí)。。。后來foreverlin同學(xué)告訴我他用樹狀數(shù)組過的，但我記得樹狀數(shù)組能解決的問題，線段樹一定能解決，而且線段樹的復(fù)雜度是logL級(jí)別，為什么我會(huì)超時(shí)呢？還請(qǐng)各位大牛指點(diǎn)。。。
我的代碼如下：
#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;
}
順便發(fā)幾句牢騷，為啥我做浙大的題總是不順呢（當(dāng)然其實(shí)我也是第二次做浙大的比賽）。。。浙大好像總喜歡出極限數(shù)據(jù)，即使算法對(duì)了，也不讓我們快速地通過，總是要優(yōu)化到最佳才行。這樣做好處是比賽的時(shí)候?qū)嵙?huì)更過硬一些吧，畢竟可以說 我們連浙大那么BT的數(shù)據(jù)都過了，算法肯定是最好的了。。。下次提前做好心理準(zhǔn)備吧。。。
下午花了一個(gè)小時(shí) 終于弄懂了樹狀數(shù)組，總算把這題過了，感覺樹狀數(shù)組實(shí)現(xiàn)起來比線段樹容易得多，效率也高得多，非常實(shí)用。
#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;//剛好為最后一個(gè)查找點(diǎn)
}
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;
}