题意：给定一组数组，a[i]表示数字i拥有数量a[i],同时给定q次查询，每次查询给定一个数字k，表示删掉全部数字第k大的数字，求删去后所有数字的中位数。
线段树
#include <bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define pi acos(-1.0)
#define PII pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define chy cout<<"chy";
using namespace std;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N = 1E6+10;
struct node{
int l,r;
int sum;
}tr[N<<2];
int n,m,A[N];
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{
tr[u]={l,r,0};
if(l==r)
{
tr[u].sum=A[l];
return ;
}
int mid = l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void modi(int u,int p)
{
if(tr[u].l==tr[u].r)
{
A[tr[u].l]--;
tr[u].sum--;
return ;
}
if(tr[u<<1].sum>=p) modi(u<<1,p);
else modi(u<<1|1,p-tr[u<<1].sum);
pushup(u);
}
double query(int u,int p)
{
if(tr[u].l==tr[u].r)
return tr[u].l;
if(tr[u<<1].sum>=p) return query(u<<1,p);
else return query(u<<1|1,p-tr[u<<1].sum);
}
int main()
{
n=read();
int cur=0;
for(int i=1;i<=n;i++)
A[i] = read(),cur+=A[i];
build(1,1,n);
int q=read();
for(int i=1;i<=q;i++)
{
int p=read();
modi(1,cur-p+1);
cur--;
if(cur&1)
printf("%.1lf
",query(1,cur+1>>1));
else
printf("%.1lf
",(query(1,cur>>1)+query(1,cur/2+1))/2);
}
return 0;
}
分块
#include <bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define pi acos(-1.0)
#define PII pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
using namespace std;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N = 1e6+100,KN = 3E5+5;
int len[N],A[N],bel[N],st[KN],ed[KN];
int n,m;
void del(int k)
{
ll c=0,p=1;
while(c+len[p]<k)
c+=len[p++];
k-=c,c=0;
for(int i=st[p];i<=ed[p];i++)
{
if(c+A[i]>=k&&A[i]!=0)
{
A[i]--,len[p]--;
return ;
}
c+=A[i];
}
}
double find(int k)
{
ll c=0,p=1;
while(c+len[p]<k)
c+=len[p++];
k-=c,c=0;
for(int i=st[p];i<=ed[p];i++)
{
if(c+A[i]>=k&&A[i]!=0)
return i;
c+=A[i];
}
}
int main()
{
n = read();
int t = sqrt(n),cur=0;
for(int i=1;i<=t;i++)
{
st[i] = (i-1)*t+1;
ed[i] = i*t;
}
if(ed[t]<n) t++,st[t]=ed[t-1]+1,ed[t]=n;
for(int i=1;i<=t;i++)
for(int j=st[i];j<=ed[i];j++)
bel[j]=i;
for(int i=1;i<=n;i++)
{
A[i] = read();
len[ bel[i] ]+=A[i];
cur+=A[i];
}
int q = read();
for(int i=1;i<=q;i++)
{
int k = read(),pos=cur-k+1;
cur--;
del(pos);
if(cur&1)
{
int pos1=cur+1>>1;
printf("%.1lf
",(find(pos1)));
}
else
{
int pos1=cur>>1,pos2=pos1+1;
printf("%.1lf
",(find(pos1)+find(pos2))/2);
}
}
return 0;
}