http://www.lydsy.com/JudgeOnline/problem.php?id=3110
整体二分+区间修改树状数组维护
#include<cstdio>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
typedef long long ll;
const int N=50011,inf=(1<<30);
int n,m,minn,maxx;
int ans[N];
ll tmp[N];
namespace BIT{ll tr1[N],tr2[N];inline void add(ll *a,int p,ll v){for(;p<=n;a[p]+=v,p+=p&-p);}inline ll query(ll *a,int p){ll ret=0;for(;p;ret+=a[p],p-=p&-p);return ret;}inline void _add(int l,int r,ll v){add(tr1,l,v);add(tr1,r+1,-v);add(tr2,l,1ll*(l-1)*v);add(tr2,r+1,-1ll*r*v);}inline ll _query(ll l,ll r){ll ans1=1ll*(l-1)*query(tr1,l-1)-1ll*query(tr2,l-1);ll ans2=1ll*r*query(tr1,r)-1ll*query(tr2,r);return ans2-ans1;}
}
using namespace BIT;
namespace divide{struct question{int a,b,c,k,pos;}p[N],t[N];inline void solve(int l,int r,int head,int tail){if(head>tail)return;if(l==r){FOR(i,head,tail)if(p[i].k==2)ans[p[i].pos]=l;return ;}int mid=(l+r)>>1;FOR(i,head,tail){if(p[i].k==1&&p[i].c>mid)_add(p[i].a,p[i].b,1ll);if(p[i].k==2)tmp[i]=_query(p[i].a,p[i].b);} int top=head,d;FOR(i,head,tail){if(p[i].k==1&&p[i].c>mid)t[top++]=p[i],_add(p[i].a,p[i].b,-1ll);if(p[i].k==2)if(p[i].c<=tmp[i])t[top++]=p[i];}d=top;FOR(i,head,tail){if(p[i].k==1&&p[i].c<=mid)t[top++]=p[i];if(p[i].k==2)if(p[i].c>tmp[i])p[i].c-=tmp[i],t[top++]=p[i]; }FOR(i,head,tail)p[i]=t[i];solve(mid+1,r,head,d-1);solve(l,mid,d,tail);}
}
using namespace divide;
int main(){scanf("%d%d",&n,&m);minn=inf,maxx=-inf;FOR(i,1,m){scanf("%d%d%d%d",&p[i].k,&p[i].a,&p[i].b,&p[i].c);if(p[i].k==2)p[i].pos=++ans[0];if(p[i].k==1)minn=min(minn,p[i].c),maxx=max(maxx,p[i].c);}solve(minn,maxx,1,m);FOR(i,1,ans[0])printf("%d\n",ans[i]);return 0;
}
补一份树套树
树状数组套主席树
#include<cstdio>
#include<algorithm>
#define lson l,mid
#define rson (mid+1),r
using namespace std;
const int maxn=1e5,N=3000000;
int n,m,tot;
int root[maxn],ra[maxn],rb[maxn];
int a[maxn],b[maxn];
struct Query{char type;int l,r,k;
}q[maxn];
struct Chainman_Tree{int ls,rs,sum;
}tr[N];
namespace BIT_with_Chainman_Tree{inline void insert(int &rt,int p,int v,int l=1,int r=b[0]){tr[++tot]=tr[rt];tr[rt=tot].sum+=v;if(l==r)return;int mid=(l+r)>>1;p<=mid?insert(tr[rt].ls,p,v,lson):insert(tr[rt].rs,p,v,rson);}inline int ask(int k,int l=1,int r=b[0]){if(l==r)return l;register int sum=0;for(register int i=1;i<=ra[0];++i)sum-=tr[tr[ra[i]].ls].sum;for(register int i=1;i<=rb[0];++i)sum+=tr[tr[rb[i]].ls].sum;int mid=(l+r)>>1;if(k<=sum){for(register int i=1;i<=ra[0];++i)ra[i]=tr[ra[i]].ls;for(register int i=1;i<=rb[0];++i)rb[i]=tr[rb[i]].ls;return ask(k,lson);}for(register int i=1;i<=ra[0];++i)ra[i]=tr[ra[i]].rs; for(register int i=1;i<=rb[0];++i)rb[i]=tr[rb[i]].rs;return ask(k-sum,rson);}inline int query(int l,int r,int k){ra[0]=rb[0]=0;for(register int i=l-1;i;i-=i&-i)ra[++ra[0]]=root[i];for(register int i=r;i;i-=i&-i)rb[++rb[0]]=root[i];return ask(k);}inline void modify(int pos,int val,int v){for(;pos<=n;pos+=pos&-pos)insert(root[pos],val,v);}
}
using namespace BIT_with_Chainman_Tree;
inline void disc_init(){sort(b+1,b+b[0]+1);b[0]=unique(b+1,b+b[0]+1)-b-1;for(register int i=1;i<=n;++i){a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;modify(i,a[i],1); }
}
char s[6];
int main(){scanf("%d%d",&n,&m);for(register int i=1;i<=n;++i){scanf("%d",a+i);b[++b[0]]=a[i];}for(register int i=1;i<=m;++i){scanf("%s",s);q[i].type=s[0];if(q[i].type=='C'){scanf("%d%d",&q[i].l,&q[i].k);b[++b[0]]=q[i].k;}elsescanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);}disc_init();for(register int i=1;i<=m;++i){if(q[i].type=='C'){q[i].k=lower_bound(b+1,b+b[0]+1,q[i].k)-b;modify(q[i].l,a[q[i].l],-1);a[q[i].l]=q[i].k;modify(q[i].l,a[q[i].l],1);}elseprintf("%d\n",b[query(q[i].l,q[i].r,q[i].k)]);} return 0;
}
