CodeForces 484E Sign on Fence - c++编程基础

TOP

CodeForces 484E Sign on Fence

2015-01-26 23:16:31 【大中小】浏览:9909次

Tags：CodeForces 484E Sign Fence

题意：

n（10^5）个模板形成的栅栏 q（10^5）个询问每个询问要求在[u,v]木板区间内摆放一个宽度为w的矩形问矩形最大的高是多少

思路：

对于每个询问可以通过logn的二分来将求解最大h的问题转化为当前h‘情况下的判定问题

为什么可以二分呢因为如果我们将木板排序从大到小的依次放置它们的位置上那么对于某一时刻线段上连续的1就代表了矩形的宽同时这时的h最小为二分到的木板高度h’ 明显h‘和这时矩形的宽满足单调性

得到了h’后只需要快速的找出[u,v]区间连续的1的长度是否超过w就好了这就需要我们提供一种能“追溯到过去任何时刻”的数据结构而且这个数据结构能在log时间内回答上述问题明显可持久化线段树满足要求

那么我们可以nlogn的建树然后二分h 再通过可持久化线段树询问区间内最长的连续的1长度是否超过w 这样对于询问的处理就是m(logn)^2的了

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; typedef long long LL; #define N 100010 #define TS 2000010 #define L(x) (ch[x][0]) #define R(x) (ch[x][1]) int n, q; struct fzc { int h, id; bool operator<(const fzc ff) const { return h > ff.h; } } f[N]; int ch[TS][2], T[TS], fleft[TS], fright[TS], maxsum[TS], tot; int build(int l, int r) { int i = tot++; fleft[i] = fright[i] = maxsum[i] = 0; if (l != r) { int mid = (l + r) >> 1; L(i) = build(l, mid); R(i) = build(mid + 1, r); } return i; } void up(int i, int l, int r) { int mid = (l + r) / 2; fleft[i] = fleft[L(i)]; if (fleft[L(i)] == mid - l + 1) fleft[i] += fleft[R(i)]; fright[i] = fright[R(i)]; if (fright[R(i)] == r - mid) fright[i] += fright[L(i)]; maxsum[i] = max(fright[L(i)] + fleft[R(i)], max(maxsum[L(i)], maxsum[R(i)])); } int insert(int old, int pos, int l, int r) { int i = tot++; L(i) = L(old); R(i) = R(old); if (pos == l && pos == r) { fleft[i] = fright[i] = maxsum[i] = 1; return i; } int mid = (l + r) / 2; if (pos <= mid) L(i) = insert(L(old), pos, l, mid); else R(i) = insert(R(old), pos, mid + 1, r); up(i, l, r); return i; } int toleft, res; void query(int i, int l, int r, int fl, int fr) { if (l == fl && r == fr) { res = max(res, maxsum[i]); toleft += fleft[i]; res = max(res, toleft); if (fleft[i] != fr - fl + 1) toleft = fright[i]; res = max(res, toleft); return; } int mid = (fl + fr) / 2; if (r <= mid) query(L(i), l, r, fl, mid); else if (l > mid) query(R(i), l, r, mid + 1, fr); else { query(L(i), l, mid, fl, mid); query(R(i), mid + 1, r, mid + 1, fr); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &f[i].h); f[i].id = i; } sort(f + 1, f + n + 1); tot = 1; T[0] = build(1, n); for (int i = 1; i <= n; i++) T[i] = insert(T[i - 1], f[i].id, 1, n); scanf("%d", &q); while (q--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); int l = 1, r = n, mid, ans; while (l <= r) { mid = (l + r) / 2; toleft = res = 0; query(T[mid], u, v, 1, n); if (res >= w) { ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", f[ans].h); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：[BZOJ 1103][POI 2007]大都市(DFS..	下一篇：基于内存查看STL常用容器内容