hdu6701 Make Rounddog Happy(分治)
题目链接
大意:让你求满足题意的区间个数
思路:先跑一遍rmq,记录区间最大值下标,预处理每个点最左到左边哪个点,最右到右边哪个点,使得这段区间没有重复。
然后就直接分治,每次分治的区间先求出最大值下标,然后对小的一边for扫一遍求出符合的区间然后更新答案即可。
细节见代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()
using namespace std;
LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 3e5 + 11;
int dp[N + 33][21];
int t, n, k, a[N];
void RMQ() {
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
dp[j][i] = a[dp[j][i - 1]] >= a[dp[j + (1 << (i - 1))][i - 1]] ?
dp[j][i - 1] : dp[j + (1 << (i - 1))][i - 1];
}
}
}
int lg[N + 3];
void init() {
lg[0] = -1;
for (int i = 1; i < N; i++)lg[i] = lg[i >> 1] + 1;
}
int get(int L, int R) {
int k = lg[R - L + 1];
int Mid = (a[dp[L][k]] >= a[dp[R - (1 << k) + 1][k]] ? dp[L][k] : dp[R - (1 << k) + 1][k]); //最大值下标
return Mid;
}
LL ans;
int L[N], R[N], vis[N];
void slove(int l, int r) {
if (l > r)return ;
int K = get(l, r);
if (K - l < r - K) {
// a[k]-(x-i+1)<=k;
// x>=a[k]+i-1-k;
for (int i = l; i <= K; i++) {
int x = a[K] + i - 1 - k;
x = max(x, K);
int tmp = min(r, R[i]);
if (x <= tmp)ans += tmp - x + 1;
}
} else {
// a[k]-(i-x+1)<=k;
// x<=k-a[k]+i+1
for (int i = K; i <= r; i++) {
int x = k - a[K] + i + 1;
x = min(x, K);
int tmp = max(l, L[i]);
if (x >= tmp)ans += x - tmp + 1;
}
}
slove(l, K - 1);
slove(K + 1, r);
}
int main() {
// ios::sync_with_stdio(false);
init();
for (scanf("%d", &t); t; t--) {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
RMQ();
ans = 0;
for (int i = 1; i <= n; i++)vis[i] = 0;
vis[a[1]] = 1; L[1] = 1;
for (int i = 2; i <= n; i++) {
if (vis[a[i]]) {
L[i] = max(L[i - 1], vis[a[i]] + 1);
} else {
L[i] = L[i - 1];
}
vis[a[i]] = i;
}
for (int i = 1; i <= n; i++)vis[i] = 0;
vis[a[n]] = n; R[n] = n;
for (int i = n - 1; i >= 1; i--) {
if (vis[a[i]]) {
R[i] = min(R[i + 1], vis[a[i]] - 1);
} else {
R[i] = R[i + 1];
}
vis[a[i]] = i;
}
// for (int i = 1; i <= n; i++) {
// cout << L[i] << ' ' << R[i] << endl;
// }
slove(1, n);
cout << ans << endl;
}
return 0;
}