**HINT 1:** Xuất phát từ bruteforce (chạy $2$ vòng for sinh hết các dãy liên tiếp) rồi tối ưu.<br>
**HINH 2:** <br>
- Từ hint 1, ta nhận thấy với $1$ dãy $i->j$ thỏa mãn thì $i+1,i+2,...->j$ cũng thỏa mãn. Do đó xét $i,$ ta được $j$ là phần tử đầu tiên khiến dãy không thỏa mãn thì khi $i+1,...$ ta chỉ cần xét tiếp $j$ từ chỗ trước.<br>
- Từ đó ta có ý tưởng $2$ con trỏ luôn tăng thay vì vòng for để linh hoạt hơn.<br>
+ **Vậy có cách nào để xác định nhanh $1$ dãy không thỏa mãn trong $1$ phép tính thay vì phải duyệt hết từ $1->m?$<br>
#**HƯỚNG DẪN:**<br>
- Thiết lập $2$ con trỏ $l,r.$ là dãy cần xét từ $l-> r$ và $r$ là vị trí cần xét dãy liệu có thỏa mãn không$?$<br>
- Nếu dãy thỏa mãn thì ta tăng $r$ lên để xét phần tử tiếp theo(nhằm tìm đoạn liên tiếp dài nhất<br>
- Nếu dãy không thỏa mãn thì ta giữ nguyên $r$(con trỏ đang cần xét xem dãy có thỏa mãn không) và tăng $l$ lên để xét mốc mới.<br>
+ Cách xét nhanh dãy thỏa mãn hay không: Mỗi lần cập nhật $1$ phần tử $r$ mới, thì tức là các phần tử trước không thay đổi đã được kiểm chứng thỏa mãn điều kiện $B_i$ do đó ta chỉ cần lưu $1$ mảng đếm số lượng xuất hiện các giá trị rồi so sánh số lượng xuất hiện phần tử đang xét với $B_i$<br>
##**CODE MẪU:**
```cpp
#include<iostream>
using namespace std;
int n,m,l,r,a[100005],dem[100005],ans,x,mx[100005];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>x,mx[i]=x;
r=0;
dem[a[0]]=1;
while(r<n)
{
if(dem[a[r]]>mx[a[r]])
{
ans=max(ans,r-l);
dem[a[l]]--;
l++;
}
else
{
r++;
dem[a[r]]++;
}
}
ans=max(ans,r-l);
cout<<ans;
}
```
sharinganvanhoadong
Created at
0 likes