二分+RMQ/双端队列/尺取法 HDOJ 5289 Assignment

题目传送门

 /*

     题意：问有几个区间最大值-最小值 < k

     解法1：枚举左端点，二分右端点，用RMQ(或树状数组)求区间最值，O(nlog(n))复杂度

     解法2：用单调队列维护最值，O(n)复杂度，用法

     解法3：尺取法，用mutiset维护最值

 */

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int MAXN = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 int a[MAXN];

 int mn[MAXN][], mx[MAXN][];     //最多能保存524288的长度

 int RMQ(int l, int r)   {

     int k = ;  while (<<(k+) <= r - l + ) k++;      //令k为满足1<<k <= r-l+1的最大整数

     int MAX = max (mx[l][k], mx[r-(<<k)+][k]);        //意思是区间最左边1<<k长度的最大值和最右边1<<k长度的最大值

     int MIN = min (mn[l][k], mn[r-(<<k)+][k]);        //可能有重叠的地方

     return MAX - MIN;

 }

 int main(void)  {       //HDOJ 5289 Assignment

     freopen ("B.in", "r", stdin);

     int t;  scanf ("%d", &t);

     while (t--) {

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

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

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

             mn[i][] = mx[i][] = a[i];

         }

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

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

                 mn[i][j] = min (mn[i][j-], mn[i+(<<(j-))][j-]);     //mn[i][j]意思是从i开始，长度1<<j的区间的最小值

                 mx[i][j] = max (mx[i][j-], mx[i+(<<(j-))][j-]);

             }

         }

         ll ans = ;

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

             int l = i, r = n;

             while (l +  < r)   {       //二分使得l, r最远

                 int mid = (l + r) >> ;

                 if (RMQ (i, mid) < k)   l = mid;

                 else    r = mid;

             }

             if (RMQ (i, r) < k) {       //此时[l, r](l+1==r) 其中一个一定满足条件

                 ans += (r - i + );

             }

             else    {

                 ans += (l - i + );

             }

         }

         printf ("%I64d\n", ans);

     }

     return ;

 }

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int MAXN = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 int a[MAXN], n;

 struct BIT  {

     int mn[MAXN], mx[MAXN];

     void init(void) {

         memset (mn, INF, sizeof (mn));

         memset (mx, , sizeof (mx));

     }

     void add_min(int i, int x)  {

         while (i <= n)    {

             mn[i] = min (mn[i], x); i += i & (-i);

         }

     }

     int query_min(int i)    {

         int res = INF;

         while (i > )   {

             res = min (res, mn[i]); i -= i & (-i);

         }

         return res;

     }

     void add_max(int i, int x)  {

         while (i <= n)    {

             mx[i] = max (mx[i], x); i += i & (-i);

         }

     }

     int query_max(int i)    {

         int res = ;

         while (i > )   {

             res = max (res, mx[i]); i -= i & (-i);

         }

         return res;

     }

 }bit;

 int main(void)  {

     //freopen ("B.in", "r", stdin);

     int t;  scanf ("%d", &t);

     while (t--) {

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

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

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

         }

         ll ans = ; bit.init ();

         for (int i=n; i>=; --i)    {       //树状数组的特点，倒过来插入，求[i, n]区间

             bit.add_min (i, a[i]);

             bit.add_max (i, a[i]);

             int l = i, r = n;

             while (l <= r)  {

                 int mid = (l + r) >> ;

                 int MAX = bit.query_max (mid);

                 int MIN = bit.query_min (mid);

                 if (MAX - MIN >= k) r = mid - ;

                 else    l = mid + ;

             }

             ans += l - i;

         }

         printf ("%I64d\n", ans);

     }

     return ;

 }

树状数组

 /*

     维护递增和递减的队列，当队首满足条件时，添加个数，再在从后添加元素，否则pop_front

 */

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <queue>

 using namespace std;

 typedef long long ll;

 const int MAXN = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 struct Node {

     int v, p;

 };

 int a[MAXN];

 int main(void)  {

     //freopen ("B.in", "r", stdin);

     int t;  scanf ("%d", &t);

     while (t--) {

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

         for (int i=; i<=n; ++i)    scanf ("%d", &a[i]);

         deque<Node> Q1, Q2; ll ans = ; int head = ;

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

             Node now = (Node){a[i], i};

             while (!Q1.empty ())    {       //递减  队首max

                 Node tmp = Q1.back ();

                 if (now.v > tmp.v)  Q1.pop_back ();

                 else    break;

             }

             Q1.push_back (now);

             while (!Q2.empty ())    {       //递增  队首min

                 Node tmp = Q2.back ();

                 if (now.v < tmp.v)  Q2.pop_back ();

                 else    break;

             }

             Q2.push_back (now);

             if (i == ) ans++;

             else    {

                 while (true)    {

                     Node big = Q1.front ();

                     Node small = Q2.front ();

                     if (big.v - small.v < k)    break;

                     else    {

                         if (small.p < big.p)    {

                             head = small.p + ; Q2.pop_front ();

                         }

                         else    {

                             head = big.p + ;   Q1.pop_front ();

                         }

                     }

                 }

                 ans += i - head + ;

             }

         }

         printf ("%I64d\n", ans);

     }

     return ;

 }

单调队列

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <set>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int MAXN = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 multiset<int> S;

 int a[MAXN];

 int main(void)  {

     //freopen ("B.in", "r", stdin);

     int t;  scanf ("%d", &t);

     while (t--) {

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

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

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

         }

         S.clear (); S.insert (a[]);

         int l = , r = ;   ll ans = ;

         int mn, mx;

         while (true)   {

             if (S.size ())  {

                 mn = *S.begin ();

                 mx = *S.rbegin ();

                 if (abs (a[r] - mn) < k && abs (a[r] - mx) < k) {

                     ans += S.size ();   S.insert (a[r++]);

                     if (r > n) break;

                 }

                 else    {

                     if (S.size ())  S.erase (S.find (a[l]));

                     l++;

                 }

             }

             else    {

                 l = r;  S.insert (a[r++]);

                 if (r > n) break;

             }

         }

         printf ("%I64d\n", ans + n);

     }

     return ;

 }

尺取法(multiset)

巴特西

二分+RMQ/双端队列/尺取法 HDOJ 5289 Assignment

最新文章

热门文章