【ZOJ】3279 Ants

 1 #include<cstdio>
 2 #define MAXN 100010
 3 int tree[MAXN<<2];
 4 inline void PushUp(int rt)
 5 {
 6     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
 7 }
 8 void Build(int L,int R,int rt)
 9 {
10     if(L==R)
11         scanf("%d",&tree[rt]);
12     else
13     {
14         int mid=(L+R)>>1;
15         Build(L,mid,rt<<1);
16         Build(mid+1,R,rt<<1|1);
17         PushUp(rt);
18     }
19 }
20 void Update(int x,int val,int L,int R,int rt)
21 {
22     if(L==R)
23         tree[rt]=val;
24     else
25     {
26         int mid=(L+R)>>1;
27         if(mid>=x)
28             Update(x,val,L,mid,rt<<1);
29         else
30             Update(x,val,mid+1,R,rt<<1|1);
31         PushUp(rt);
32     }
33 }
34 int Query(int x,int L,int R,int rt)
35 {
36     if(L==R)
37         return L;
38     int mid=(L+R)>>1;
39     if(x<=tree[rt<<1])
40         return Query(x,L,mid,rt<<1);
41     else
42     {
43         x-=tree[rt<<1];
44         return Query(x,mid+1,R,rt<<1|1);
45     }
46 }
47 int main()
48 {
49     int n,q,x,y;
50     char ch;
51     while(~scanf("%d",&n))
52     {
53         Build(1,n,1);
54         scanf("%d",&q);
55         while(q--)
56         {
57             scanf(" %c%d",&ch,&x);
58             if(ch=='p')
59             {
60                 scanf("%d",&y);
61                 Update(x,y,1,n,1);
62             }
63             else
64                 printf("%d\n",Query(x,1,n,1));
65         }
66     }
67     return 0;
68 }
新博客：www.zhixiangli.com