2019MultiUniversityTrainingContest31007Findtheanswer——线段树

This way

题意&＃xff1a;

给你n个数&＃xff0c;让你从1到n输出一个数&＃xff0c;这个数是说让你从1到i-1中最少去掉几个数使得1-i的sum<&＃61;m。

题解&＃xff1a;

我们去肯定是去掉最大的那几个&＃xff0c;保留小的。那么我们就可以先离散化求出每个值是在原数组中的第几小。建树按照这个建。维护的值是前缀和&＃xff0c;也就是说新加入一个数&＃xff0c;将i-n的所有位置上都加上a[i]&＃xff0c;这样我们之后直接找<&＃61;m-a[i]的最大位置即可。query返回这个区间有多少个值。
最狗的一点是&＃xff0c;需要在每次输出最后加上空格&＃xff1f;&＃xff1f;这是出题人的问题吧。

#include
using namespace std;
#define ll long long
const int N&＃61;2e5&＃43;5;
ll a[N],b[N],num[N*4],mi[N*4],mx[N*4],flag[N*4];
int fa[N];
int finds(int x)
{return x&＃61;&＃61;fa[x]?x:fa[x]&＃61;finds(fa[x]);
}
void push_down(int root)
{if(!flag)return ;flag[root<<1]&＃43;&＃61;flag[root];flag[root<<1|1]&＃43;&＃61;flag[root];mi[root<<1]&＃43;&＃61;flag[root];mi[root<<1|1]&＃43;&＃61;flag[root];mx[root<<1]&＃43;&＃61;flag[root];mx[root<<1|1]&＃43;&＃61;flag[root];flag[root]&＃61;0;
}
void update(int l,int r,int root,int ql,int qr,int val,int f)
{if(l>&＃61;ql&&r<&＃61;qr){if(!f)num[root]&＃43;&＃43;;elsemi[root]&＃43;&＃61;val,mx[root]&＃43;&＃61;val,flag[root]&＃43;&＃61;val;return ;}push_down(root);int mid&＃61;l&＃43;r>>1;if(mid>&＃61;ql)update(l,mid,root<<1,ql,qr,val,f);if(mid}
int query(int l,int r,int root,int val)
{if(l&＃61;&＃61;r)return mi[root]<&＃61;val?num[root]:0;push_down(root);int mid&＃61;l&＃43;r>>1;if(mx[root]<&＃61;val)return num[root];if(mx[root<<1]<&＃61;val){int ans&＃61;num[root<<1];if(mi[root<<1|1]<&＃61;val)ans&＃43;&＃61;query(mid&＃43;1,r,root<<1|1,val);return ans;}if(mi[root<<1]<&＃61;val)return query(l,mid,root<<1,val);return 0;
}
int main()
{int q;scanf("%d",&q);while(q--){ll n,m;scanf("%lld%lld",&n,&m);for(int i&＃61;0;i<&＃61;n*4;i&＃43;&＃43;)mi[i]&＃61;mx[i]&＃61;num[i]&＃61;flag[i]&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%lld",&a[i]),b[i]&＃61;a[i],fa[i]&＃61;i;sort(b&＃43;1,b&＃43;1&＃43;n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){int x&＃61;lower_bound(b&＃43;1,b&＃43;1&＃43;n,a[i])-b;a[i]&＃61;finds(x);fa[a[i]]&＃61;a[i]&＃43;1;finds(x);}printf("0 ");for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;){update(1,n,1,a[i-1],a[i-1],1,0);update(1,n,1,a[i-1],n,b[a[i-1]],1);int nn&＃61;query(1,n,1,m-b[a[i]]);printf("%d ",i-1-nn);}printf("\n");}return 0;
}