3 条题解
-
0
C96 树状数组套权值线段树 P2617 Dynamic Rankings C105 整体二分+树状数组 P2617 Dynamic Rankings
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct trnode{int lc, rc, s;} tr[N*400]; int trlen=0; struct node{bool flag; int l, r, k, p;} q[N]; int a[N], lsh[2*N], ln, root[N], temp[20][2], n, cnt0, cnt1; void change(int &now, int l, int r, int k, int c) { if(now<=0) now=++trlen, tr[now]={-1, -1, 0}; tr[now].s+=c; if(l==r) return ; int mid=(l+r)/2; if(k<=mid) change(tr[now].lc, l, mid, k, c); else change(tr[now].rc, mid+1, r, k, c); } void p_change(int x, int c) { int k=lower_bound(lsh+1, lsh+ln+1, a[x])-lsh; for(int i=x; i<=n; i+=(i&-i)) change(root[i], 1, ln, k, c); } int query(int l, int r, int k) { if(l==r) return lsh[l]; int mid=(l+r)/2, sum=0; for(int i=1; i<=cnt0; i++) sum-=tr[tr[temp[i][0]].lc].s; for(int i=1; i<=cnt1; i++) sum+=tr[tr[temp[i][1]].lc].s; if(k<=sum) { for(int i=1; i<=cnt0; i++) temp[i][0]=tr[temp[i][0]].lc; for(int i=1; i<=cnt1; i++) temp[i][1]=tr[temp[i][1]].lc; return query(l, mid, k); } else { for(int i=1; i<=cnt0; i++) temp[i][0]=tr[temp[i][0]].rc; for(int i=1; i<=cnt1; i++) temp[i][1]=tr[temp[i][1]].rc; return query(mid+1, r, k-sum); } } int p_query(int l, int r, int k) { memset(temp, 0, sizeof(temp)); cnt0=cnt1=0; for(int i=l-1; i; i-=(i&-i)) temp[++cnt0][0]=root[i]; for(int i=r; i; i-=(i&-i)) temp[++cnt1][1]=root[i]; return query(1, ln, k); } int main() { int m; scanf("%d%d", &n, &m); ln=0; for(int i=1; i<=n; i++) scanf("%d", &a[i]), lsh[++ln]=a[i]; for(int i=1; i<=m; i++) { char s[5]; scanf("%s", s); if(s[0]=='Q') { q[i].flag=1; scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k); } else { q[i].flag=0; scanf("%d%d", &q[i].p, &q[i].k); lsh[++ln]=q[i].k; } } sort(lsh+1, lsh+ln+1); ln=unique(lsh+1, lsh+ln+1)-lsh-1; memset(root, 0, sizeof(root)); for(int i=1; i<=n; i++) p_change(i, 1); for(int i=1; i<=m; i++) { if(q[i].flag) printf("%d\n", p_query(q[i].l, q[i].r, q[i].k)); else { p_change(q[i].p, -1); a[q[i].p]=q[i].k; p_change(q[i].p, 1); } } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:04:47
C96 树状数组套权值线段树 P2617 Dynamic Rankings
C105 整体二分+树状数组 P2617 Dynamic Rankings#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct trnode{int lc, rc, s;} tr[N*400]; int trlen=0; struct node{bool flag; int l, r, k, p;} q[N]; int a[N], lsh[2*N], ln, root[N], temp[20][2], n, cnt0, cnt1; void change(int &now, int l, int r, int k, int c) { if(now<=0) now=++trlen, tr[now]={-1, -1, 0}; tr[now].s+=c; if(l==r) return ; int mid=(l+r)/2; if(k<=mid) change(tr[now].lc, l, mid, k, c); else change(tr[now].rc, mid+1, r, k, c); } void p_change(int x, int c) { int k=lower_bound(lsh+1, lsh+ln+1, a[x])-lsh; for(int i=x; i<=n; i+=(i&-i)) change(root[i], 1, ln, k, c); } int query(int l, int r, int k) { if(l==r) return lsh[l]; int mid=(l+r)/2, sum=0; for(int i=1; i<=cnt0; i++) sum-=tr[tr[temp[i][0]].lc].s; for(int i=1; i<=cnt1; i++) sum+=tr[tr[temp[i][1]].lc].s; if(k<=sum) { for(int i=1; i<=cnt0; i++) temp[i][0]=tr[temp[i][0]].lc; for(int i=1; i<=cnt1; i++) temp[i][1]=tr[temp[i][1]].lc; return query(l, mid, k); } else { for(int i=1; i<=cnt0; i++) temp[i][0]=tr[temp[i][0]].rc; for(int i=1; i<=cnt1; i++) temp[i][1]=tr[temp[i][1]].rc; return query(mid+1, r, k-sum); } } int p_query(int l, int r, int k) { memset(temp, 0, sizeof(temp)); cnt0=cnt1=0; for(int i=l-1; i; i-=(i&-i)) temp[++cnt0][0]=root[i]; for(int i=r; i; i-=(i&-i)) temp[++cnt1][1]=root[i]; return query(1, ln, k); } int main() { int m; scanf("%d%d", &n, &m); ln=0; for(int i=1; i<=n; i++) scanf("%d", &a[i]), lsh[++ln]=a[i]; for(int i=1; i<=m; i++) { char s[5]; scanf("%s", s); if(s[0]=='Q') { q[i].flag=1; scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k); } else { q[i].flag=0; scanf("%d%d", &q[i].p, &q[i].k); lsh[++ln]=q[i].k; } } sort(lsh+1, lsh+ln+1); ln=unique(lsh+1, lsh+ln+1)-lsh-1; memset(root, 0, sizeof(root)); for(int i=1; i<=n; i++) p_change(i, 1); for(int i=1; i<=m; i++) { if(q[i].flag) printf("%d\n", p_query(q[i].l, q[i].r, q[i].k)); else { p_change(q[i].p, -1); a[q[i].p]=q[i].k; p_change(q[i].p, 1); } } return 0; }</p> -
-1
整体二分代码：
#include<bits/stdc++.h> using namespace std; const int N=3e5+10; struct node{int x,y,k,id,op;}q[N],q1[N],q2[N]; int a[N],b[N],c[N],ans[N],n,m,cnt; void add(int x,int k){for(;x<=cnt;x+=x&-x)c[x]+=k;} int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;} void solve(int l,int r,int L,int R) { if(L>R)return; if(l==r) { for(int i=L;i<=R;i++)ans[q[i].id]=l; return; } int mid=(l+r)>>1,p1=0,p2=0; for(int i=L;i<=R;i++) { if(q[i].op==0) { if(q[i].y<=mid)add(q[i].x,q[i].k),q1[++p1]=q[i]; else q2[++p2]=q[i]; } else { int sum=get(q[i].y)-get(q[i].x-1); if(sum>=q[i].k)q1[++p1]=q[i]; else q[i].k-=sum,q2[++p2]=q[i]; } } for(int i=1;i<=p1;i++)if(q1[i].op==0)add(q1[i].x,-q1[i].k); for(int i=1;i<=p1;i++)q[L+i-1]=q1[i]; for(int i=1;i<=p2;i++)q[L+p1+i-1]=q2[i]; solve(l,mid,L,L+p1-1);solve(mid+1,r,L+p1,R); } signed main() { cin>>n>>m;cnt=0; for(int i=1;i<=n;i++) { cin>>a[i];b[i]=a[i]; q[++cnt]={i,a[i],1,0,0}; } int cnt1=0; for(int i=1;i<=m;i++) { string s;cin>>s; if(s[0]=='C') { int x,y;cin>>x>>y; q[++cnt]={x,b[x],-1,0,0}; q[++cnt]={x,y,1,0,0}; b[x]=y; } else { int x,y,c;cin>>x>>y>>c; q[++cnt]={x,y,c,++cnt1,1}; } } solve(0,1e9,1,cnt); for(int i=1;i<=cnt1;i++)cout<<ans[i]<<'\n'; return 0; }
- 1
