题意很简单，就是带修改的K大数查询。 查询自不用说，怎么修改？ 由于数字都在1-n范围内，所以他的权值就是他的排名，直接插入，然后建立区间线段树，在线段树内找到修改的范围，然后用主席树区间修改。 因为多打两个else而调了一上午的sb。。。 权值线段树本来也可以，但是数据加强以后被卡了。
#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int maxn=1e6+5; const int M=2e7+5; typedef long long ll; int a[maxn],b[maxn],c[maxn]; int N; bool flag[maxn]; int hash[maxn]; int num[maxn],cnt,op; int n,m,sz,t,ans,root[maxn],ls[M],rs[M]; ll sum[M],lazy[M]; inline void pushdown(int x,int l,int r,int mid) { if (!lazy[x])return; if (!ls[x])ls[x]=++sz; sum[ls[x]]+=(mid-l+1)*lazy[x]; lazy[ls[x]]+=lazy[x]; if (!rs[x])rs[x]=++sz; sum[rs[x]]+=(r-mid)*lazy[x]; lazy[rs[x]]+=lazy[x]; lazy[x]=0; } inline void update(int last,int &x,int l,int r,int a,int b,ll v) { if (!x)x=++sz; int mid=(l+r)>>1; ls[x]=ls[last],rs[x]=rs[last]; if (l>=a&&r<=b) { sum[x]+=v*(r-l+1); lazy[x]+=v; return; }pushdown(x,l,r,mid); if (a<=mid)update(ls[last],ls[x],l,mid,a,b,v); if (mid+1<=b)update(rs[last],rs[x],mid+1,r,a,b,v); sum[x]=sum[ls[x]]+sum[rs[x]]; } inline ll query(int x,int l,int r,int a,int b) { ll ans=0; int mid=(l+r)>>1; if (a<=l&&r<=b)return sum[x]; pushdown(x,l,r,mid); if (a<=mid)ans+=query(ls[x],l,mid,a,b); if (mid+1<=b)ans+=query(rs[x],mid+1,r,a,b); return ans; } inline void v_update(int x,int l,int r,int v,int a,int b) { int mid=(l+r)>>1; update(root[x],root[x],1,n,a,b,1); if (l==r)return; if (v<=mid)v_update(x<<1,l,mid,v,a,b); else v_update(x<<1|1,mid+1,r,v,a,b); } inline int v_query(int x,int l,int r,int a,int b,ll k) { if (!x)return 0; int mid=(l+r)>>1; if (l==r)return l; ll t=query(root[x<<1],1,n,a,b); if (t>=k) return v_query(x<<1,l,mid,a,b,k); else return v_query(x<<1|1,mid+1,r,a,b,k-t); } inline int find(int x) { int l=1,r=N,mid; while (l<=r) { mid=(l+r)>>1; if (x>hash[mid])l=mid+1; else r=mid-1; } return l; } int main() { scanf("%d%d",&n,&m); fo(i,1,m) { scanf("%d%d%d%d",&op,&a[i],&b[i],&c[i]); if (op==1) { flag[i]=true; num[++cnt]=c[i]; } } sort(num+1,num+1+cnt); fo(i,1,cnt) { if (num[i]!=num[i-1])hash[++N]=num[i]; } fo(i,1,m) { if (flag[i]) { t=find(c[i]); v_update(1,1,N,t,a[i],b[i]); } else { ll tot=query(root[1],1,n,a[i],b[i]); ll t=(ll)tot-(ll)c[i]+1; ans=v_query(1,1,N,a[i],b[i],t); printf("%d\n",hash[ans]); } } }