4237: 稻草人

分析：

　　CDQ分治+单调栈。

　　首先按照x排序，每次分治，考虑左边一个点和多少个右边的点可以有贡献。CDQ的过程中，按照y从大到小排序。

　　左右两边的y都是从大到小的，所以对于每个左边点，先把y比它大的加上，然后在这些点中维护一个x递增的栈（每个点在上一个点的右下方，如果一个点的x大于下一个点，那么这个点是没有用的，下一个点y小，x小，在其左下方，能遮住它）。

　　对于左边的点，维护一个x递减的栈。这个栈的意义是上一个点对栈顶的点有限制（上一个点的x大，y大，所以在其左上方）。

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              11 #include
               
                12 #define fi(s) freopen(s,"r",stdin);13 #define fo(s) freopen(s,"w",stdout);14 using namespace std;15 typedef long long LL;16 17 inline int read() {18 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;19 for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;20 }21 22 const int N = 200005;23 24 int n;25 struct Node{26 int x, y;27 Node() {}28 Node(int _x,int _y) { x = _x, y = _y; }29 }A[N], B[N], sk1[N], sk2[N];30 int top1, top2;31 LL Ans;32 33 bool operator < (const Node &A, const Node &B) {34 return A.x < B.x;35 }36 37 int find(int k) {38 int L = 1, R = top2 + 1, res = top2 + 1;39 while (L <= R) {40 int mid = (L + R) >> 1;41 if (sk2[mid].y < k) res = mid, R = mid - 1; // sk中y是递减的42 else L = mid + 1;43 }44 return res;45 }46 47 void CDQ(int l,int r) {48 if (l >= r) return ;49 int mid = (l + r) >> 1;50 CDQ(l, mid); CDQ(mid + 1, r);51 52 top1 = 0, top2 = 0;53 int i = l, j = mid + 1, k;54 for (i=l; i<=mid; ++i) {55 while (top1 && sk1[top1].x < A[i].x) top1--; // x单调递减 56 sk1[++top1] = A[i];57 while (j<=r && A[j].y >= A[i].y) {58 while (top2 && sk2[top2].x > A[j].x) top2 --; // x单调递增59 sk2[++top2] = A[j ++]; 60 }61 if (top1 == 1) Ans += top2;62 else Ans += top2 - find(sk1[top1-1].y) + 1;63 }64 i = l, j = mid + 1, k = l;65 while (i <= mid && j <= r) {66 if (A[i].y > A[j].y) B[k++] = A[i ++];67 else B[k++] = A[j ++];68 }69 while (i <= mid) B[k ++] = A[i ++];70 while (j <= r) B[k ++] = A[j ++];71 for (i=l; i<=r; ++i) A[i] = B[i];72 } 73 74 int main() { 75 n = read();76 for (int i=1; i<=n; ++i) {77 int x = read(), y = read();78 A[i] = Node(x, y);79 }80 sort(A + 1, A + n + 1);81 CDQ(1, n);82 cout << Ans;83 return 0;84 }

转载于:https://www.cnblogs.com/mjtcn/p/9716078.html

你可能感兴趣的文章