思路:
-
由于朴素的求前缀是用$T(i)=T(i-1)+1$,为了能够维护修改操作我们就需要在,树状数组上建立主席树,树状数组每一个节点表示的是一颗主席树.
-
这样每次修改缀就是在树状数组上的$\log n$棵主席树上完成即可.
-
求和也是类似的每次都是求$\log n$棵主席树.
-
树状数组在这个过程中扮演的就是类似单点修改,区间查询的工作.
-
我们建树的时候每一次对自己建立即可.这和不带修改的版本是有区别的.
-
由于假如某结点的左儿子或者右儿子在这样建树的过程中没有被创建出来
其就会指向$Tr[0]$由于其是空的因此,在统计的过程中就算因为该点不存在使得我们统计到了$Tr[0]$也不会影响答案.还需要注意的是,我们需要:离线操作,因为离散化的时候我们需要提前开好位置否则的话查询的时候就会因为没有该数字的位置而出现错误.
-
同时每一次修改完成以后还需要注意:及时将$w[x]$修改成$y$.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=1e5+10;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,m;
int w[100010],idx,root[100010];
//int id[N],mx;//记录 节点i 所属的主席树是那一颗
vector<int>nums;
int find(int x)
{
return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
struct node{
int l,r,cnt;
}tr[33554422];//究极卡空间
int insert(int q,int l,int r,int x,int c)
{
int p=idx++;
// id[p]=mx;
tr[p]=tr[q];
if(l==r)
{
tr[p].cnt+=c;
return p;
}
int mid=l+r>>1;
if(x<=mid)tr[p].l=insert(tr[q].l,l,mid,x,c);
else tr[p].r=insert(tr[q].r,mid+1,r,x,c);
tr[p].cnt=tr[tr[p].l].cnt+tr[tr[p].r].cnt;
return p;
}
int lowbit(int x)
{
return x&-x;
}
void add(int pos,int x,int c)
{
for(int i=pos;i<=n;i+=lowbit(i))root[i]=insert(root[i],0,nums.size()-1,x,c);//在第root[i]棵主席树的第x个节点上加一
}
int build(int l,int r)
{
int p=++idx;
if(l==r)return p;
int mid=l+r>>1;
tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
return p;
}
int query(int p,int l,int r,int L,int R)
{//[l,r]为查询区间 [L,R]为整体二分区间
if(L>=l&&R<=r)return tr[p].cnt;
int mid=L+R>>1;
int res=0;
if(l<=mid)res+=query(tr[p].l,l,r,L,mid);//
if(r>mid)res+=query(tr[p].r,l,r,mid+1,R);
return res;
}
int sum(int x,int l,int r)
{
int res=0;
for(int i=x;i;i-=lowbit(i))res+=query(root[i],l,r,0,nums.size()-1);
return res;//得到了 T(x) 在 [l,r]区间数字的数量
}//统计前x棵主席树中 区间(l,r)cnt的数量
int Query(int l,int r,int L,int R,int k)
{
int mid=L+R>>1;
if(L==R)return L;
int cnt=sum(r,L,mid)-sum(l,L,mid);//左区间 数的数量
if(k<=cnt)return Query(l,r,L,mid,k);//左区间数的数量更多
else return Query(l,r,mid+1,R,k-cnt);//右区间数的数量更多
}
struct ans{
char op;
int l,r,k;
int x,y;
}q[100010];
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>w[i];
nums.push_back(w[i]);
}
for(int i=1;i<=m;i++)
{
char op;cin>>op;
if(op=='Q')
{
q[i].op='Q';
cin>>q[i].l>>q[i].r>>q[i].k;
}else
{
q[i].op='C';
cin>>q[i].x>>q[i].y;
nums.push_back(q[i].y);//必须提前开好位置 否则如果主席树没有该点修改就会出错
}
}
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
root[0]=build(0,nums.size()-1);
for(int i=1;i<=n;i++)add(i,find(w[i]),1);
for(int i=1;i<=m;i++)
if(q[i].op=='Q')cout<<nums[Query(q[i].l-1,q[i].r,0,nums.size()-1,q[i].k)]<<endl;
else
{
add(q[i].x,find(w[q[i].x]),-1),add(q[i].x,find(q[i].y),1);
w[q[i].x]=q[i].y;
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
由于每次建树的过程只会插入一个数字,只会修改一条长为$\ log N$的链.
而每次修改某一点同时还需修改树状数组上其余$\log N$棵树的 同样长度的链
因此总体空间复杂度:$(M+N)*\ log ^{2}{N}$需要大概:512MB
时间复杂度 也是类似的$O(M+N)* \ log ^{2}{N}$
Orz