1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
const int MAXN=(int)2e5+3;
int n,p,q,maxx,cans=0;
int pre[MAXN],ans[MAXN];
PII a[MAXN];
// ===================================================================================================================
// Seg Tree 板子
struct Node{
int val,add,mul=1;
} t[MAXN<<2];
// int a[100003];
void build_t(int root,int l,int r)
{
t[root].mul=1,t[root].add=0;
if(l==r) t[root].val=0; //本题修改的地方,val=0 打标记用
else
{
int m=(l+r)>>1,rx=root<<1;
build_t(rx,l,m);
build_t(rx+1,m+1,r);
t[root].val=(t[rx].val+t[rx+1].val);
}
}
void push_down(int root,int l,int r)
{
int m=(l+r)>>1,rx=root<<1;
t[rx].val=(t[rx].val*t[root].mul+t[root].add*(m-l+1));
t[rx+1].val=(t[rx+1].val*t[root].mul+t[root].add*(r-m));//!!!!!!!!!!!!!!!!!!rx+1
t[rx].mul=(t[rx].mul*t[root].mul);
t[rx+1].mul=(t[rx+1].mul*t[root].mul);
t[rx].add=(t[rx].add*t[root].mul+t[root].add);
t[rx+1].add=(t[rx+1].add*t[root].mul+t[root].add);
t[root].mul=1,t[root].add=0;
}
void up1(int root,int nowl,int nowr,int l,int r,ll k)
{
if(r<nowl || nowr<l) return;
if(l<=nowl && nowr<=r)
{
t[root].val=(t[root].val*k);
t[root].mul=(t[root].mul*k);
t[root].add=(t[root].add*k);
return;
}
push_down(root,nowl,nowr);
int m=(nowl+nowr)>>1,rx=root<<1;
up1(rx,nowl,m,l,r,k);
up1(rx+1,m+1,nowr,l,r,k);
t[root].val=(t[rx].val+t[rx+1].val);
}
void up2(int root,int nowl,int nowr,int l,int r,ll k)
{
if(r<nowl || nowr<l) return;
if(l<=nowl && nowr<=r)
{
t[root].add=(t[root].add+k);
t[root].val=(t[root].val+k*(nowr-nowl+1));
return;
}
push_down(root,nowl,nowr);
int m=(nowl+nowr)>>1,rx=root<<1;
up2(rx,nowl,m,l,r,k);
up2(rx+1,m+1,nowr,l,r,k);
t[root].val=(t[rx].val+t[rx+1].val);
}
ll query(int root,int nowl,int nowr,int l,int r)
{
if(r<nowl || nowr<l) return 0;
if(l<=nowl && nowr<=r) return t[root].val;
push_down(root,nowl,nowr);
int m=(nowl+nowr)>>1,rx=root<<1;
return (query(rx,nowl,m,l,r)+query(rx+1,m+1,nowr,l,r));
}
// End Seg Tree
// ============================================================================================
int que(int l,int r) {
return l>r?0:pre[r]-pre[l-1];
}
bool chk(int m) {
for(int i=m;i<=n;i++) {
int mx=a[i].fi;
if(mx*q*m<=p*que(i-m+1,i)) {
return true;
}
}
return false;
}
int cal(int mx, int sum) {
return mx * q*maxx <= p * sum;
}
inline void work(signed CASE=1,bool FINAL_CASE=false) {
n=read();
for(int i=1;i<=n;i++) {
a[i].fi=read(); a[i].se=i;
}
p=read(); q=read();
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) {
pre[i]=pre[i-1]+a[i].fi;
}
int l=0,r=n;
while(l<r) {
int m=(l+r)>>1;
if(chk(m)) {
maxx=max(maxx,m);
l=m+1;
} else {
r=m;
}
}
build_t(1,1,n);
for (int i = maxx; i <= n; i++) {
if (cal(a[i].fi, que(i - maxx + 1, i))) {
//[i - m + 1 , i ] 这个区间是满足条件的，我们才开始二分
int L = 1, R = i - maxx + 1, pos = INF;
int sum = que(i - maxx + 1 + 1, i);//这里记录下 i 左边 m - 1 个数的和
// for (int j = 1; j <= 50; j++) {
while(L<=R) {
int mid = (L + R) / 2;
if (cal(a[i].fi , sum + a[mid].fi)) {//最大的数是 a[i].val
pos = min(mid, pos);
R = mid-1;
}
else {
L = mid+1;
}
}
up2(1,1,n,pos,i,1);
}
}
for (int i = 1; i <= n; i++) {
if (query(1,1,n,i,i) == 0) {
ans[++cans]=a[i].se;
}
}
sort(ans+1, ans+1+cans);
printf("%lld\n",cans);
for (int i=1;i<=cans;i++) {
printf("%lld%c",ans[i]," \n"[i==cans]);
}
return;
}
|