Znzryb's Blog
0%

Posted on Edited on

思路讲解

AC代码

AC
https://vjudge.net/solution/58198800

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
// Problem: A/B
// Contest: Virtual Judge - HDU
// URL: https://vjudge.net/problem/HDU-1576
// Memory Limit: 32 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3,mod=9973;

ll N,B,T,A[MAXN];

void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){	// x，y都是反的
		x=1,y=0;
	}else{
		exgcd(b,a%b,y,x);
		y-=a/b*x;	// 实际是y=x1-a/b*y1	但实际上因为我们在上面反了一下，所以这里也要反一下
	}
}
// (ax-1)%m=0
inline void solve(){
	// 其实就是要求B的逆元
	cin>>N>>B;
	ll x_,y_;
	exgcd(B,mod,x_,y_);	// x_就是B的逆元
	// (A/B)%mod = (A/B)%mod *(bk)%mod=(Ak)%mod
	ll ans=(N*x_)%mod;
	if(ans<0) ans+=mod;
	cout<< ans <<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://vjudge.net/solution/58198800
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

【牛客寒假集训营第四场讲题】 【精准空降到 2:13:15】 https://www.bilibili.com/video/BV1TxN8eKEQY/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=7995

这个题解可以理解为该视频讲解的笔记

其实异或很简单，不就是相同的相消嘛，所以说对数值有贡献的就只有1是吧，那么把1消掉嘛，剩下的1就是我们要求的值了

道理是比较简单的，就是如果A[i]的这位是0，我们就想知道B[i～r]这位有多少个1，反之，如果A[i]的这位是1，B[i~r]这位有多少个0，统计好以后使用权值进行计算

然后知道了这个道道，但怎么样在O（1）的时间内实现这个查询那？需要用到后缀和的前缀和

image

代码中的ssumB就是代指这个三角形（整体来看是三角形，分序号来看是梯形），ssumB[i][j]如下图所示(第j位是指数位，第i位是指A[i],B[i])

image

查询就是查中间这个小三角形，于是我们用大梯形-小梯形-矩形就好了

image

我们还是要细化一下，这个矩形是怎么求的？还是前缀和？（也不是不行，但是二维前缀和可能MLE了）

我们可以直接用乘法，用a里1的个数乘以b里0的个数就（都是指在数位1里的情况）可以了。

image

这个长方形计算其实也不容易

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75503543

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
// Problem: Tokitsukaze and XOR-Triangle
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/L
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3,mod=static_cast<ll>(1e9)+7;

ll N,M,T,A[MAXN],B[MAXN],B2[MAXN][32],A2[MAXN][32],sumB[MAXN][32],sumA[MAXN][32];
ll pow2[35];
ll ssumB[MAXN][32];

inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,N){
		cin>>B[i];
	}
	FOR(i,0,N+5){	// init
		FOR(j,0,31){
			sumB[i][j]=0;
			sumA[i][j]=0;
			A2[i][j]=0;
			B2[i][j]=0;
			ssumB[i][j]=0;
			// ssumA[i][j]=0;
		}
	}
	FOR(i,1,N){
		ll x=A[i];
		ll idx=0;
		while(x){
			A2[i][idx++]=x%2;
			x/=2;
		}
	}
	FOR(i,1,N){
		ll x=B[i];
		ll idx=0;
		while(x){
			B2[i][idx++]=x%2;
			x/=2;
		}
	}
	FOR(i,1,N){	// A的后缀和
		FOR(j,0,31){
			sumA[i][j]=(sumA[i-1][j]+A2[i][j])%mod;
		}
	}
	ROF(i,N,1){		// 后缀和
		FOR(j,0,31){
			sumB[i][j]=(sumB[i+1][j]+B2[i][j])%mod;
		}
	}
	
	FOR(i,1,N){
		FOR(j,0,31){
			if(A2[i][j]==1){
				ssumB[i][j]=(ssumB[i-1][j]+(N-i+1-sumB[i][j]))%mod;	// 需要计算0的数量(用总数量-1的数量)
			}else{
				ssumB[i][j]=(ssumB[i-1][j]+sumB[i][j])%mod;
			}
		}
	}
	FOR(i,1,M){
		ll l,r;
		cin>>l>>r;
		ll ans=0;
		FOR(j,0,31){
			ll sq=0;
			//  A中0的个数乘以B中1的个数             
			sq=(r-l+1-(sumA[r][j]-sumA[l-1][j]))*sumB[r+1][j]%mod+(sumA[r][j]-sumA[l-1][j])*(N-r-sumB[r+1][j])%mod;
			//     大梯形-小梯形-                     长方形(A是前缀和，B是后缀和)
			ans=(ans+((ssumB[r][j]-ssumB[l-1][j])%mod-sq)*pow2[j])%mod;
		}
		if(ans<0) ans+=mod;
		cout<<ans<<'\n';
	}
	
	// FOR(i,1,N){
		// cerr<<i<<": ";
		// FOR(j,0,31){
			// cerr<<ssumB[i][j]<<' ';
		// }
		// cerr<<'\n';
	// }
	// // cerr<<'\n';
	// FOR(i,1,N){
		// cerr<<i<<": ";
		// FOR(j,0,31){
			// cerr<<sumB[i][j]<<' ';
		// }
		// cerr<<'\n';
	// }
	// // cerr<<'\n';
	// FOR(i,1,N){
		// cerr<<i<<": ";
		// FOR(j,0,31){
			// cerr<<sumA[i][j]<<' ';
		// }
		// cerr<<'\n';
	// }
	// cerr<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,32){
		pow2[i]=(pow2[i-1]*2)%mod;
	}
	while(T--){
		solve();
	}
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

这个是有点问题的，因为前缀和没有根据A在这位的值进行变化

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
159
160
161
162
163
164
165
166
// Problem: Tokitsukaze and XOR-Triangle
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/L
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3,mod=static_cast<ll>(1e9)+7;

ll N,M,T,A[MAXN],B[MAXN],B2[MAXN][32],A2[MAXN][32],sumB[MAXN][32],sumA[MAXN][32];
ll pow2[35];
ll ssumB[MAXN][32],ssumA[MAXN][32];
ll alr[32],blr[32];

inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,N){
		cin>>B[i];
	}
	FOR(i,0,N+5){	// init
		FOR(j,0,31){
			sumB[i][j]=0;
			sumA[i][j]=0;
			A2[i][j]=0;
			B2[i][j]=0;
			ssumB[i][j]=0;
			ssumA[i][j]=0;
		}
	}
	FOR(i,1,N){
		ll x=A[i];
		ll idx=0;
		while(x){
			A2[i][idx++]=x%2;
			x/=2;
		}
	}
	FOR(i,1,N){
		ll x=B[i];
		ll idx=0;
		while(x){
			B2[i][idx++]=x%2;
			x/=2;
		}
	}
	ROF(i,N,1){
		FOR(j,0,31){
			sumB[i][j]=(sumB[i+1][j]+B2[i][j])%mod;
		}
	}
	FOR(i,1,N){
		FOR(j,0,31){
			sumA[i][j]=(sumA[i-1][j]+A2[i][j])%mod;
		}
	}
	
	FOR(i,1,N){
		FOR(j,0,31){
			ssumA[i][j]=(ssumA[i-1][j]+sumA[i][j])%mod;
		}
	}
	ROF(i,N,1){
		FOR(j,0,31){
			ssumB[i][j]=(ssumB[i+1][j]+sumB[i][j])%mod;
		}
	}
	FOR(i,1,M){
		ll l,r;
		cin>>l>>r;
		FOR(j,0,31){
			alr[j]=(ssumA[r][j]-ssumA[l-1][j])%mod;
			alr[j]=(alr[j]-sumA[l-1][j]*(r+l-1))%mod;
		}
		FOR(j,0,31){
			blr[j]=(ssumB[l][j]-ssumB[r+1][j])%mod;
			blr[j]=(blr[j]-sumB[r+1][j]*(r+l-1))%mod;
		}
		ull ans=0;
		FOR(j,0,31){
			ans=(ans+(max(alr[j],blr[j])-min(alr[j],blr[j]))*pow2[j])%mod;
			//cerr<<max(alr[j],blr[j])-min(alr[j],blr[j])<<'\n';
		}
		// FOR(j,0,31){
			// cerr<<alr[j]<<' ';
		// }
		// cerr<<'\n';
		// FOR(j,0,31){
			// cerr<<blr[j]<<' ';
		// }
		// cerr<<'\n';
		ans%=mod;
		if(ans<0) ans+=mod;
		cout<<ans<<'\n';
	}
	
	FOR(i,1,N){
		cerr<<i<<": ";
		FOR(j,0,31){
			cerr<<ssumB[i][j]<<' ';
		}
		cerr<<'\n';
	}
	// cerr<<'\n';
	FOR(i,1,N){
		cerr<<i<<": ";
		FOR(j,0,31){
			cerr<<ssumA[i][j]<<' ';
		}
		cerr<<'\n';
	}
	FOR(i,1,N){
		cerr<<i<<": ";
		FOR(j,0,31){
			cerr<<sumB[i][j]<<' ';
		}
		cerr<<'\n';
	}
	// cerr<<'\n';
	FOR(i,1,N){
		cerr<<i<<": ";
		FOR(j,0,31){
			cerr<<sumA[i][j]<<' ';
		}
		cerr<<'\n';
	}
	cerr<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,32){
		pow2[i]=(pow2[i-1]*2)%mod;
	}
	while(T--){
		solve();
	}
	return 0;
}
/*

*/

当时在赛场上想到了前缀和+前缀和的思路，但是我没想到按位推导的思路，所以就卡住了，在那边疯狂打表找规律，自然看不出来什么~~（数感不行）~~

赛时在草稿纸上画的图

Posted on Edited on

思路讲解

https://www.luogu.com/article/wa8c5zfe 还有一种差分想法，更加简洁，挺好的

10就是在差分数组中有一个-1，01就是差分数组中有一个1，把差分数组加起来，就能得到01数量-10数量的值，然后根据差分的结论，我们就知道差分总值只和首项和末项有关。

首先根据上题，我们需要发现两个结论：
1） 首尾相同的字符串一定是平衡的。
2） 首尾不相同的字符串一定是不平衡的。

这是为什么那？

直接证明这个结论比较难，可以这么想，大家可以想象一个都是0序列，将里面的0变为1（通过这一操作可以生成任何序列）会对10，01数量造成什么变化那？（其实我也不是很会证明，大家就随便看看吧）

image

我们发现，只有在对空情况的操作时，才会产生不平衡这样的问题

而且对空情况的左右两种镜像情况分别为一组，这两组中的任意两对都是互相抵消的（比如10++ && 01++ 就会使数列平衡）

那么其实就完成了，头尾都是0的情况嘛所有操作都使数列保持平衡，头尾都是1的情况对空操作也就抵消了，那么就得到了上述的结论。

有了这个结论以后剩下的就简单了，剩下的就看代码吧，关键地方有注释，然后注意特判只有单个字母的情况。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75411197

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
// Problem: Tokitsukaze and Balance String (hard)
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3,mod=static_cast<ll>(1e9)+7;

ll N,T;
char S[MAXN];//Sd[MAXN];
ull ans=0,pow2[MAXN];

inline void solve(){
	cin>>N;
	ans=0;
	ll cnt=0;
	FOR(i, 1, N){
		cin>>S[i];
		if(S[i]=='?') ++cnt;
		// Sd[i]=S[i];
	}
	if(N==1){
		if(S[1]!='?') cout<<1<<'\n';
		else cout<<2<<'\n';
		return;
	}
	if(S[1]=='?' && S[N]=='?'){
		ans+=2*pow2[cnt-2]*(N-2);	// ?为0，0 1，1的情况
		//cerr<<ans<<'\n';
		ans%=mod;
		ans+=4*pow2[cnt-2];	// ?,? 1,0 0,1的情况(两种情况，每种情况有两种位置，所以*4)
		//cerr<<ans<<'\n';
		ans%=mod;
	}else if(S[1]=='?' || S[N]=='?'){
		ans+=pow2[cnt-1]*(N-2);
		ans%=mod;
		ans+=2*pow2[cnt-1];
		ans%=mod;
	}else{
		if(S[1]!=S[N]){
			ans=2*pow2[cnt];
			ans%=mod;
		}else{
			ans=pow2[cnt]*(N-2);
			ans%=mod;
		}
	}
	cout<<ans%mod<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,MAXN-5){
		pow2[i]=(pow2[i-1]*2)%mod;
	}
	while(T--){
		solve();
	}
	return 0;
}
/*
AC

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

如同这个例子一样，已经匹配好的我们就可以不管了，因为是两两匹配的，所以说回文串中心不会改变，不用担心会有什么问题

image

然后最容易想不通的就是长串内部的消除问题

image

1
2
3
4
5
6
7
8
FOR(i,0,25){
	if(cnta[i]>=cntb[i]) cnta[i]-=cntb[i];
	else shortRem+=cntb[i]-cnta[i],cntb[i]-=cnta[i],cnta[i]=0;
}
ll longRem=0;
FOR(i,0,25){
	if(cnta[i]%2==1) ++longRem;
}

abgfhh 和abcdeee的匹配过程（longRem ≥ shortRem 就可以像下图这样将重复元素加入到对称轴两边，进而就可以抵消）

image

当（longRem < shortRem），为什么答案就是shortRem那？

说白了其实就是把这些奇数的都给搞定了，剩下的就都是偶数的，就比较好搞了（）

image

与longRem匹配完剩余是偶数的情况更简单，就不画了。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75405249

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
// Problem: Tokitsukaze and Concatenate‌ Palindrome
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/D
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
char Ao[MAXN],Bo[MAXN],A[MAXN],B[MAXN];
ll cnta[29],cntb[29];

inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,M){
		cin>>B[i];
	}
	FOR(i,0,27){
		cnta[i]=0;
		cntb[i]=0;
	}
	if(N<M){
		FOR(i,1,M){
			swap(A[i],B[i]);
		}
		swap(N,M);
	}
	FOR(i,1,N){
		cnta[A[i]-'a']+=1;
	}
	FOR(i,1,M){
		cntb[B[i]-'a']+=1;
	}
	ll shortRem=0;
	FOR(i,0,25){
		if(cnta[i]>=cntb[i]) cnta[i]-=cntb[i];
		else shortRem+=cntb[i]-cnta[i],cntb[i]-=cnta[i],cnta[i]=0;
	}
	ll longRem=0;
	FOR(i,0,25){
		if(cnta[i]%2==1) ++longRem;
	}
	if(shortRem>longRem){
		cout<<shortRem<<'\n';
	}else{
		// if((N+M)%2!=0) longRem= longRem==0?0:longRem-1;
		cout<<shortRem+(longRem-shortRem)/2<<'\n';
	}
	
	// FOR(i,1,N){
		// cerr<<A[i]<<' ';
	// }
	// cerr<<'\n';
	// FOR(i,1,M){
		// cerr<<B[i]<<' ';
	// }
	// cerr<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

1
2
3
4
5
6
struct cmp{
	bool operator()(const pll &a,const pll &b) const {
		return a.fi>b.fi;
	}
};
multiset<pll,cmp> B;

给multiset的cmp记得加const，否则有可能CE

1
2
3
4
5
6
7
8
9
for(multiset<pll>::iterator it=B.begin();it!=B.end();){
	if(it->first<A[i]){
		break;
	}
	multiset<pll>::iterator next_it=next(it);
	ans[it->second]=i;
	B.erase(it);
	it=next_it;
}

然后erase（）只能传入iterator，不能够传入reverse_iterator

AC代码

https://atcoder.jp/contests/abc382/submissions/62419496

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
// Problem: C - Kaiten Sushi
// Contest: AtCoder - AtCoder Beginner Contest 382
// URL: https://atcoder.jp/contests/abc382/tasks/abc382_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,A[MAXN];
// pll B[MAXN];
struct cmp{
	bool operator()(const pll &a,const pll &b) const {
		return a.fi>b.fi;
	}
};
multiset<pll,cmp> B;
ll ans[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	FOR(i, 1, N){
		cin>>A[i];
	}
	FOR(i, 1, M){
		ll b;
		cin>>b;
		B.insert({b,i});
	}
	FOR(i,1,M){
		ans[i]=-1;
	}
	
	FOR(i,1,N){
		for(multiset<pll>::iterator it=B.begin();it!=B.end();){
			if(it->first<A[i]){
				break;
			}
			multiset<pll>::iterator next_it=next(it);
			ans[it->second]=i;
			B.erase(it);
			it=next_it;
		}
	}
	FOR(i,1,M){
		cout<<ans[i]<<'\n';
	}
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc382/submissions/62419496
*/

心路历程（WA，TLE，MLE……）