forestkeeper 2010-01-08 10:32 鍙戣〃璇勮
]]>forestkeeper 2010-01-07 22:39 鍙戣〃璇勮
]]>棰樻剰鏄錛岃殏铓佹湁n涓瓑綰э紙level錛夛紝姣忎釜絳夌駭鍒濆閮芥湁涓瀹氶噺鐨勮殏铓侊紝闅忓悗鏈変竴緋誨垪鎿嶄綔錛宲 a b鎿嶄綔琛ㄧず鎶妉evel a鐨勮殏铓佷釜鏁拌漿鎹㈡垚b錛宷 x 琛ㄧず璇㈤棶鍦ㄦ墍鏈夎殏铓侀噷鎺掑悕絎瑇鐨勮殏铓佸湪鍝釜絳夌駭銆?br>
棣栧厛涓鍏辨湁鐨勮殏铓佹暟涓烘墍鏈塴evel铓傝殎鏁伴噺鎬誨拰錛屼笉鑳戒負(fù)姣忎釜铓傝殎閮藉紑涓涓猧nt鏁扮粍鍘誨瓨瀹冪殑level錛堝鏋滄暟鎹噺寰堝皬鍒欒繖縐嶆柟娉曞彲浠ユ槸o錛坣錛夌殑錛夈傚瀛樼潃姣忎釜灞傜殑铓傝殎鍙互鐢ㄦ眰鍜屼笌x姣旇緝鏉ョ‘瀹氬畠澶勪簬鍝釜level銆傜敱浜巒鐨勬暟閲忕駭錛屾晠甯屾湜鑳介噰鐢╨og n綰х殑鏂規(guī)硶鏉ュ鐞嗭紝鎭板ソ鐢辯嚎孌墊爲(wèi)瀹炵幇鐨勫瓙孌靛拰錛屽叾鏃犺鏄洿鏂幫紙update錛夎繕鏄煡璇紙query錛夐兘鏄痩og n綰х殑錛屽悓鏃跺湪鏌ヨ鏃跺彲鍐嶅姞涓浜屽垎錛屽嵆sort錛?錛宯錛夊紑濮嬶紝浜庢槸鏌ヨ鐨勫鏉傚害涓簂ogn*logn錛屾渶緇?80ms AC銆傞檮浠ｇ爜錛屼唬鐮佷腑鏈敤綰挎鏍?wèi)锛岃屾槸浣跨敤浜?jiǎn)鏍?wèi)鐘舵暟緇勫悓鏍鋒槸logn鐨勬煡鎵懼強(qiáng)鏇存柊澶嶆潅搴︼紝絀洪棿澶嶆潅搴﹀強(qiáng)緙栫▼澶嶆潅搴︽瘮綰挎鏍?wèi)浣庛?br>
#include <cstring> #include<cstdio>const int MAXN = 100000; 
inline int lowbit(int x) 
{ 
return (x & (x ^ (x - 1))); 
} template<class elemType> class Sum{ public: elemType a[MAXN], c[MAXN], ret; int n; 
void init(int i) { memset(a, 0, sizeof(a)); memset(c, 0, sizeof(c)); n = i; 
} void update(int i, elemType v) { v -= a[i]; a[i] += v; for (i++; i <= n; i += lowbit(i)) { c[i - 1] += v; } } elemType query(int i) { for (ret = 0; i; i ^= lowbit(i)) { ret += c[i-1]; } return ret; } };Sum<int>sum; int Sort(int l,int r,int x){ if(l>=r-1) return l; int pos = (l+r)/2; if (pos==1) return pos; int p1 = sum.query(pos); int p2 = sum.query(pos-1); if(x>p1&&x<=p2) return pos; int ans; if(x>p2) ans = Sort(pos,r,x); else ans = Sort(l,pos,x); return ans;}int main(){ int n; while(scanf("%d",&n)!=EOF) { sum.init(n); for (int i =0; i<n; i++) { int a; scanf("%d",&a); sum.update(i,a); } int m; scanf("%d",&m); for (int i =0; i<m; i++) { char c[20]; scanf("%s",c); if (c[0]=='p') { int a,b; scanf("%d%d",&a,&b); sum.update(a-1,b); } else { int x; scanf("%d",&x); int ans = Sort(1,n+1,x); printf("%d\n",ans); } } }}forestkeeper 2010-01-03 11:07 鍙戣〃璇勮
]]>