題目：

題目描述

給出序列?a1，a2，…，an（0≤ai≤109），有關序列的兩種操作。

1.?ai（1≤i≤n）變成?x（0≤x≤109）。

2.?求?al，al+1，…，ar（1≤l≤r≤n）第?k（1≤k≤r-l+1）小。

輸入格式

第一行包含兩個數?n（1≤n≤2×104）和?m（1≤m≤2×104），表示序列長度和操作次數。

接下來一行?n?個數，以空格隔開，表示?a1，a2，…，an?。

接下來m行，每行為以下兩種格式之一：

• 0?i?x?，??表示?ai＝x。
• 1?l?r?k?，求?al，al+1，…，ar?的第?k?小。

輸出格式

對于每次詢問，輸出單獨的一行表示答案。

樣例數據 1

輸入　 [復制]

?

5 3?
1 2 3 4 5?
1 1 5 3?
0 3 5?
1 1 5 3

輸出

3?
4

題解：

? 待修改的權值線段樹的模板題

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std;int getint() {int i=0,f=1;char c;for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar();for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';return i*f; }const int N=2e4+5,M=2e6+5; struct node {int op,x,y,k; }q[N]; struct tree {int lc,rc,size; }tr[M]; int n,m,len,tot,a[N],b[N<<1],bit[N],pos[N];void dic_init() {sort(b+1,b+len+1);len=unique(b+1,b+len+1)-b-1;for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+len+1,a[i])-b;for(int i=1;i<=m;i++)if(!q[i].op)q[i].y=lower_bound(b+1,b+len+1,q[i].y)-b; }void Insert(int &k,int l,int r,int x) {if(!k)k=++tot;tr[k].size++;if(l==r)return;int mid=l+r>>1;if(x<=mid)Insert(tr[k].lc,l,mid,x);else Insert(tr[k].rc,mid+1,r,x); }void Add(int x) {for(int i=x;i<=n;i+=i&(-i))Insert(bit[i],1,len,a[x]); }void Delete(int k,int l,int r,int x) {tr[k].size--;if(l==r)return;int mid=l+r>>1;if(x<=mid)Delete(tr[k].lc,l,mid,x);else Delete(tr[k].rc,mid+1,r,x); }void Rec(int x) {for(int i=x;i<=n;i+=i&(-i))Delete(bit[i],1,len,a[x]); }void pre(int x,int y) {for(int i=x;i>0;i-=i&(-i))pos[i]=bit[i];for(int i=y;i>0;i-=i&(-i))pos[i]=bit[i]; }int calc(int x,int y) {int res=0;for(int i=x;i>0;i-=i&(-i))res+=tr[tr[pos[i]].lc].size;for(int i=y;i>0;i-=i&(-i))res-=tr[tr[pos[i]].lc].size;return res; }void trans(int x,int y,int f) {for(int i=x;i>0;i-=i&(-i))if(!f)pos[i]=tr[pos[i]].lc;else pos[i]=tr[pos[i]].rc;for(int i=y;i>0;i-=i&(-i))if(!f)pos[i]=tr[pos[i]].lc;else pos[i]=tr[pos[i]].rc; }int query(int rt1,int rt2,int l,int r,int k) {if(l==r)return l;int delta=calc(rt1,rt2);int mid=l+r>>1;if(delta>=k){trans(rt1,rt2,0);return query(rt1,rt2,l,mid,k);}else {trans(rt1,rt2,1);return query(rt1,rt2,mid+1,r,k-delta);} }int main() {//freopen("a.in","r",stdin);n=getint(),m=getint();for(int i=1;i<=n;i++)a[i]=getint(),b[++len]=a[i];for(int i=1;i<=m;i++){q[i].op=getint();q[i].x=getint();q[i].y=getint();if(!q[i].op)b[++len]=q[i].y;else q[i].k=getint();} dic_init();for(int i=1;i<=n;i++)Add(i);for(int i=1;i<=m;i++)if(!q[i].op){Rec(q[i].x);a[q[i].x]=q[i].y;Add(q[i].x);}else{pre(q[i].y,q[i].x-1);cout<<b[query(q[i].y,q[i].x-1,1,len,q[i].k)]<<'\n';}return 0; }

?

轉載于:https://www.cnblogs.com/AseanA/p/7201294.html

總結

以上是生活随笔為你收集整理的刷题总结——序列操作（权值线段树套树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。