第一次用英语，见谅。
为什么用英语？
``` Dev 里懒得换输入法。 ```Link
Description
F has \(n\) beads arranged in a sequence, each of which has a color, and a total of \(m\) colors, numbered \(1, 2, 3, \cdots,m\).
She wants to take out a sequence of beads, and for each color \(i\), requires that the number of beads taken out be between \([L_i, R_i]\).
Find how many schemes for taking out beads there are.
Train of Thought
For a data range of \(2 \times 10^5\), we can just use time complexity \(O(n)\) with a constant methods for solving.
Obviously, we need to select a legal interval, which requires the use of the pointer. And as you see, two-pointer.
\(L_i\) means when left pointer is \(i\), all data minimum, \(R_i\) means when right pointer is \(i\), all data maximum.
The answer is the number of all legal numbers between \(L\) and \(R\) (include \(L\) and \(R\)).
See code for details.
Code
//For a data range of 2e5, we can just use time complexity O(n) with a big constant methods for solving.
//Obviously, we need to select a legal interval, which requires the use of the pointer. And as you see, two-pointer.
//L[i] means when left pointer is i, all data minimum, R[i] means when right pointer is i, all data maximum.
//The answer is the number of all legal numbers between L and R(include L and R).
#include <bits/stdc++.h>
#define maxn 200005
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
int n, m, c[maxn], ll[maxn], rr[maxn];
int t[maxn];
int L[maxn], R[maxn];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> c[i];
memset(t, 0, sizeof(t));
for (int i = 1; i <= m; i++) cin >> ll[i] >> rr[i];
ll[0] = rr[0] = INF; //init
int l = 1, r = 1, cnt = 0;
for (int i = 1; i <= m; i++) //remember how many "0" there is
if (ll[i] == 0) cnt++;
t[c[1]] = 1; //init
// if (t[c[1]] >= ll[c[1]] && ll[c[1]]) cnt++; //if ll[c[1]] == 1
if (ll[c[1]] == 1) cnt++;
bool flag = 0;
memset(L, 0x3f, sizeof(L)); //memset L MAX
while (r <= n + 1 && l <= n) {
if (cnt == m) L[l] = min(L[l], r);
//if the number of "allow" = M, that means all of M are OK. choose a smaller value
if (flag) L[l] = 0; //some of "M" are not allow, we can't choose it
if ((cnt == m && l < r) || flag || r == n + 1) {
//if all "M" are OK and l is smaller than r OR some of "M" aren't allow OR r is the max value
t[c[l]]--; //coler l's number get less
if (t[c[l]] == ll[c[l]] - 1) cnt--; //color r isn't allow
if (t[c[l]] == rr[c[l]] && flag) { //color r is allow
cnt++;
flag = 0;
}
l++; //get new value
} else {
r++;
t[c[r]]++;
if (t[c[r]] == rr[c[r]] + 1) { //color r's number bigger than max value color r can be
cnt--;
flag = 1; //color r isn't allow
} else if (t[c[r]] == ll[c[r]]) cnt++; //color r's number is allow
}
}
memset(t, 0, sizeof(t));
l = 1, r = 1, cnt = 0, flag = 0;
for (int i = 1; i <= m; i++)
if (ll[i] == 0) cnt++;
t[c[1]]++;
if (t[c[1]] >= ll[c[1]] && ll[c[1]]) cnt++;
while (l <= n && r <= n + 1) { //similarly, it is easy to prove. no prove again
if (flag) R[l] = 0;
if (cnt == m - 1 && t[c[r]] - 1 == rr[c[r]]) R[l] = max(R[l], r - 1);
if (r == n + 1 && cnt == m) R[l] = max(R[l], r - 1);
if ((t[c[r]] - 1 == rr[c[r]] && cnt == m - 1 && l < r) || flag || r == n + 1) {
t[c[l]]--;
if (t[c[l]] == rr[c[l]] && flag) {
flag = 0;
cnt++;
}
if (t[c[l]] == ll[c[l]] - 1) cnt--;
l++;
} else {
r++;
t[c[r]]++;
if (t[c[r]] == ll[c[r]]) cnt++;
if (t[c[r]] == rr[c[r]] + 1) {
cnt--;
flag = 1;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (L[i] <= R[i] && L[i] && R[i]) //it's allow when L less than or equal to R and L and R aren't 0
ans += R[i] - L[i] + 1;
cout << ans << '\n';
return 0;
}
End.
标签：10,means,int,data,ll,联训,maxn,2023,pointer From： https://www.cnblogs.com/cloud-evecyx/p/18016304