网站关键词推广哪家好,咸阳seo推广,网络优化工程师工作内容,一个简单网页的代码正题
题目链接:https://www.luogu.com.cn/problem/P2617 题目大意
给出一个序列#xff0c;要求支持
区间查询第kkk大单点修改 解题思路
区间查询第kkk大需要使用主席树#xff0c;构建权值线段树的前缀和。考虑如何进行单点修改#xff0c;在前缀和上进行单点修改就是进…正题
题目链接:https://www.luogu.com.cn/problem/P2617 题目大意
给出一个序列要求支持
区间查询第kkk大单点修改 解题思路
区间查询第kkk大需要使用主席树构建权值线段树的前缀和。考虑如何进行单点修改在前缀和上进行单点修改就是进行区间修改区间修改主席树显然不可能考虑树套树。
我们可以维护以权值线段树为权值的树状数组这样可以单点修改并且维护动态前缀和。
时间复杂度:O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#define lowbit(x) (x-x)
using namespace std;
const int N1e510,MN*400;
int n,m,a[N],b[N*2],root[N];
int q1[N],q2[N],q3[N],num;
int w[M],ls[M],rs[M],tot;
int cnt1,cnt2,tmp1[N],tmp2[N];
char op[N];
void Updata(int x,int l,int r,int pos,int val){if(!x)xnum;if(lr){w[x]val;return;}int mid(lr)1;if(posmid)Updata(ls[x],l,mid,pos,val);else Updata(rs[x],mid1,r,pos,val);w[x]w[ls[x]]w[rs[x]];
}
void Change(int x,int val){int klower_bound(b1,b1tot,a[x])-b;while(xn){Updata(root[x],1,tot,k,val);xlowbit(x);}return;
}
int Ask(int l,int r,int k){if(lr)return l;int mid(lr)1,sum0;for(int i1;icnt1;i)sum-w[ls[tmp1[i]]];for(int i1;icnt2;i)sumw[ls[tmp2[i]]];if(ksum){for(int i1;icnt1;i)tmp1[i]ls[tmp1[i]];for(int i1;icnt2;i)tmp2[i]ls[tmp2[i]];return Ask(l,mid,k);}else{for(int i1;icnt1;i)tmp1[i]rs[tmp1[i]];for(int i1;icnt2;i)tmp2[i]rs[tmp2[i]];return Ask(mid1,r,k-sum);}
}
int Query(int x,int l,int r){l--;cnt1cnt20;for(int il;i;i-lowbit(i))tmp1[cnt1]root[i];for(int ir;i;i-lowbit(i))tmp2[cnt2]root[i];return Ask(1,tot,x);
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);b[tot]a[i];}for(int i1;im;i){cinop[i];scanf(%d %d,q1[i],q2[i]);if(op[i]Q)scanf(%d,q3[i]);else b[tot]q2[i];}sort(b1,b1tot);totunique(b1,b1tot)-b-1;for(int i1;in;i)Change(i,1);for(int i1;im;i){if(op[i]Q)printf(%d\n,b[Query(q3[i],q1[i],q2[i])]);else{Change(q1[i],-1);a[q1[i]]q2[i];Change(q1[i],1);}}return 0;
}
