多校3 Find the answer hdu6609 贪心 权值线段树

题意：Q组样例。每组样例第一行给出n、m，接下来一行n个数(a[i])。对于每一个  i  ,输出需要删除最少的个数，使得 a[i]+  。

如果每次都从大到小删除肯定是会超时的   但是有些是可以永久删除的 

当set里面大于m 的时候    最大的数是肯定要删除的！（ 贪心） 

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
typedef pair<int,int>pii;
//////////////////////////////////
const int N=2e6+10;
int n,m,a[N],sum,sumtemp,cnt,temp;

int main()
{
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        rep(i,1,n)scanf("%d",&a[i]);

        multiset<int>q;
        cnt=sumtemp=sum=temp=0;
        rep(i,1,n)
        {
            temp=0;
            sumtemp=sum;
            auto j=q.end();
            while(sumtemp+a[i]>m)
            {
                --j;
                sumtemp-=*j;
                temp++;
            }
            printf("%d ",cnt+temp);

            q.insert(a[i]);sum+=a[i];
            j=q.end();
            while(sum>m)
            {
                --j;
                sum-=*j;
                q.erase(q.find(*j));
                cnt++;
            }
        }
        printf("
");
    }
    return 0;
}

权值线段树：

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
typedef pair<int,int>pii;
//////////////////////////////////
const int N=2e6+10;

#define lson l,m,pos<<1
#define rson m+1,r,pos<<1|1

ll t[N];
int num[N],n,m,a[N],b[N];

void build(int l,int r,int pos)
{
    t[pos]=0;num[pos]=0;
    if(l==r)return ;
    int m=(l+r)>>1;
    build(lson);build(rson);
}

void upnode(int x,int l,int r,int pos)
{
    if(l==r){ num[pos]++;t[pos]+=b[x];return;};
    int m=(l+r)>>1;
    if(x<=m)upnode(x,lson);
    else upnode(x,rson);
    t[pos]=t[pos<<1]+t[pos<<1|1];
    num[pos]=num[pos<<1]+num[pos<<1|1];
}

int qsum(int x,int l,int r,int pos)
{
    if(t[pos]<=x)return num[pos];
    if(l==r)return min(num[pos],x/b[l]);
    int m=(l+r)>>1;
    if(t[pos<<1]>=x) return qsum(x,lson);
    else return num[pos<<1]+qsum(x-t[pos<<1],rson);
}
int main()
{
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        rep(i,1,n)scanf("%d",&a[i]),b[i]=a[i];

        sort(b+1,b+1+n);

        int nn=unique(b+1,b+1+n)-b-1;
        build(1,nn,1);
        rep(i,1,n)
        {
            if(i==1)printf("0 ");
            else printf("%d ",i-1-qsum(m-a[i],1,nn,1));
            int pos=lower_bound(b+1,b+1+n,a[i])-b;
            upnode(pos,1,nn,1);
        }
        printf("
");
    }
    return 0;
}