1 //用树状数组维护前i项最值
 2 
 3 map<int,int> m;//用map可以突破下标过大导致的空间限制
 4 
 5 int lowbit(int x)
 6 {
 7     return x&-x;
 8 }
 9 
10 void upd(int idx,int val)
11 {
12     while(idx<maxn)
13     {
14         m[idx]=max(val,m[idx]);
15         idx+=lowbit(idx);
16     }
17 }
18 
19 int query(int idx)
20 {
21     int ans=0;
22     while(idx>0)
23     {
24         ans=max(ans,m[idx]);
25         idx-=(idx&(-idx));
26     }
27     return ans;
28 }