[BZOJ 1901]Dynamic Rankings
转载请注明出处:http://danihao123.is-programmer.com/
终于A了!
做了4个月了,终于A了!
这个题其实不难。只要用树状数组维护主席树即可。不过请注意,此题的实际数据范围远比10000大!
代码:
/************************************************************** Problem: 1901 User: danihao123 Language: C++ Result: Accepted Time:540 ms Memory:32712 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int maxn=120051; const int maxlogn=31; const int maxnode=maxn*20; // ChairTree int sumv[maxnode]; int lc[maxnode],rc[maxnode]; int ct_cnt=0; int build_tree(int L,int R){ int ans=++ct_cnt; if(R>L){ int M=L+(R-L)/2; lc[ans]=build_tree(L,M); rc[ans]=build_tree(M+1,R); } return ans; } int p,v; int update(int o,int L,int R){ int ans=++ct_cnt; sumv[ans]=sumv[o]; lc[ans]=lc[o]; rc[ans]=rc[o]; if(R>L){ int M=L+(R-L)/2; if(p<=M) lc[ans]=update(lc[ans],L,M); else rc[ans]=update(rc[ans],M+1,R); } sumv[ans]+=v; return ans; } int LT_siz,RT_siz; int LT[maxlogn],RT[maxlogn]; int query(int L,int R,int k){ if(L==R) return L; int i; int LT_ans=0,RT_ans=0,the_ans,M=L+(R-L)/2; for(i=1;i<=LT_siz;i++) LT_ans+=sumv[lc[LT[i]]]; for(i=1;i<=RT_siz;i++) RT_ans+=sumv[lc[RT[i]]]; the_ans=RT_ans-LT_ans; if(k<=the_ans){ for(i=1;i<=LT_siz;i++) LT[i]=lc[LT[i]]; for(i=1;i<=RT_siz;i++) RT[i]=lc[RT[i]]; return query(L,M,k); }else{ for(i=1;i<=LT_siz;i++) LT[i]=rc[LT[i]]; for(i=1;i<=RT_siz;i++) RT[i]=rc[RT[i]]; return query(M+1,R,k-the_ans); } } int rt[maxn]; int siz; inline int lowbit(int x){ return x&(-x); } int n; void change(int pos,int value,int delta){ p=value; v=delta; while(pos<=n){ rt[pos]=update(rt[pos],1,siz); pos+=lowbit(pos); } } int get_ans(int l,int r,int k){ int temp=l-1; LT_siz=RT_siz=0; while(temp>0){ LT[++LT_siz]=rt[temp]; temp-=lowbit(temp); } while(r>0){ RT[++RT_siz]=rt[r]; r-=lowbit(r); } return query(1,siz,k); } int pre[maxn]; int A[maxn],A2[maxn]; int real_siz=0; void init_CT(){ register int i,pos; sort(A2+1,A2+1+real_siz); siz=unique(A2+1,A2+1+real_siz)-A2-1; rt[0]=build_tree(1,siz); for(i=1;i<=n;i++) rt[i]=rt[0]; for(i=1;i<=n;i++){ pos=lower_bound(A2+1,A2+1+siz,pre[i])-A2; change(i,pos,1); } } inline int get_lsh(int x){ return lower_bound(A2+1,A2+1+siz,x)-A2; } int Query[maxn][4]; int main(){ int m,u,v,d; char buf[3]; register int i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d",&pre[i]); A2[++real_siz]=pre[i]; } for(i=1;i<=m;i++){ scanf("%s%d%d",buf,&u,&v); Query[i][1]=u; Query[i][2]=v; if(buf[0]=='C'){ Query[i][0]=1; A2[++real_siz]=v; }else{ Query[i][0]=0; scanf("%d",&Query[i][3]); } } init_CT(); for(i=1;i<=m;i++){ if(Query[i][0]){ change(Query[i][1],get_lsh(pre[Query[i][1]]),-1); pre[Query[i][1]]=Query[i][2]; change(Query[i][1],get_lsh(Query[i][2]),1); }else{ printf("%d\n",A2[get_ans(Query[i][1],Query[i][2],Query[i][3])]); } } return 0; }
Jul 05, 2023 08:29:26 PM
Learn the reasons why your refrigerator or air conditioner isn't chilling properly, as well as how to properly fill the gas tank. the causes of a noisy air conditioner or refrigerator The refrigerator and air conditioner leak water due to the refrigerator's failure to refrigerationpedia.com properly freeze ice.causes of ice freezing incorrectly in refrigerators. How can I change the thermostat in my refrigerator and why does it have so much ice in it.