[2019杭电多校第十场][hdu6701]Make Rounddog Happy

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6701

题目大意为求满足 $max(a_{l},a_{l+1}\cdot \cdot \cdot a_{r})-(r-l+1)<=k$的区间个数。

先预处理出前缀最大值和后缀最大值和ST表，然后分治。

每次可以得到这次分治区间的区间最大值，然后我们要求出以该最大值为区间最大值时的合法区间数目。

这里我们可以枚举合法区间的左端点(右端点)，然后通过化简上式得到合法的右端点(左端点)，选择枚举左还是右端点由当前区间最大值的位置所决定，因为左端点一定在最大值左边，右端点一定在最大值右边，所以选择数量较小的一边来枚举。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef unsigned long long ull;

 const int maxn = 3e5 + ;

 int a[maxn], pos[maxn], L[maxn], R[maxn], Log[maxn];

 int n, k;

 int dp[maxn][];

 int query(int l, int r) {

     int k = Log[r - l + ];

     if (a[dp[l][k]] > a[dp[r - ( << k) + ][k]])

         return dp[l][k];

     else

         return dp[r - ( << k) + ][k];

 }

 ll dfs(int l, int r) {

     if (l == r)return a[l] -  <= k;

     if (l > r)return ;

     int cnt = query(l, r);

     ll ans = ;

     if (cnt - l < r - cnt) {

         for (int i = l; i <= cnt; i++) {

             int ls = max(cnt, i + a[cnt] - k - );

             int rs = min(r, R[i]);

             if (rs >= ls)

                 ans += rs - ls + ;

         }

     }

     else {

         for (int i = cnt; i <= r; i++) {

             int ls = max(l, L[i]);

             int rs = min(i - (a[cnt] - k) + , cnt);

             if (rs >= ls) ans += rs - ls + ;

         }

     }

     return ans + dfs(l, cnt - ) + dfs(cnt + , r);

 }

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         scanf("%d%d", &n, &k);

         for (int i = ; i <= n; i++)

             scanf("%d", &a[i]);

         Log[] = -;

         for (int i = ; i <= n; i++) Log[i] = Log[i >> ] + ;

         for (int i = ; i <= n; i++)

             dp[i][] = i;

         for (int j = ; ( << j) <= n; j++) {

             for (int i = ; i + ( << j) -  <= n; i++) {

                 if (a[dp[i][j - ]] > a[dp[i + ( << (j - ))][j - ]])

                     dp[i][j] = dp[i][j - ];

                 else

                     dp[i][j] = dp[i + ( << (j - ))][j - ];

             }

         }

         for (int i = ; i <= n; i++)pos[i] = ;

         R[n + ] = n;

         for (int i = n; i >= ; i--) {

             if (pos[a[i]]) {

                 R[i] = pos[a[i]] - ;

                 pos[a[i]] = i;

             }

             else {

                 pos[a[i]] = i;

                 R[i] = n;

             }

             R[i] = min(R[i], R[i + ]);

         }

         for (int i = ; i <= n; i++)pos[i] = ;

         for (int i = ; i <= n; i++) {

             if (pos[a[i]]) {

                 L[i] = pos[a[i]] + ;

                 pos[a[i]] = i;

             }

             else {

                 pos[a[i]] = i;

                 L[i] = ;

             }

             L[i] = max(L[i], L[i - ]);

         }

         printf("%lld\n", dfs(, n));

     }

 }

巴特西

[2019杭电多校第十场][hdu6701]Make Rounddog Happy

最新文章

热门文章