TIOJ 1045 A.細菌培養

TIOJ 1045 A.細菌培養

題目概述:

有一個初始值為1的10000*10000格子，給n個矩形，使每個矩形內的所有元素加倍。

求最後所有元素加總。

思路:

從上而下一排一排的計算。

假設我知道這排被(1,20),(4,8),(6,12),(15,17)覆蓋。

我把每個區間存成兩個點，一個點代表開始，另一個點代表結束。

我只要能知道a和b之間(不包含b)被k個區間覆蓋，那我就讓答案加上(b-a)*2k

可以參考下圖。(紅色的為甚麼要+1可以看看下文)

la代表上一個位置在哪

sum代表被覆蓋了幾次

那我又要怎麼快速地知道每一行有哪些區間呢?

我維護一個該行有的區間multiset<P> s;

我存矩形的方式為存到vector<P> v[],nv[]，

v[]代表應該從該行要開始覆蓋的區間

nv[]代表應該從該行要結束覆蓋的區間

假設有個矩形l,u,r,d，注意因為題目給的上下左右是線，不是格子，假設給(0,0)~(2,2)試指涵蓋了(1,1),(1,2),(2,1),(2,2)這四格。

(u+1)~(d)行都需要覆蓋(l+1)~(r)這個區間，

所以從第(u+1)行開始覆蓋，第(d+1)行結束。(注意不是在第d行結束，因為第d行也要覆蓋)

至於為甚麼區間是要在(r+1)結束也是一樣的道理。

接著在每一行都加上v[]裡存的區間，然後扣掉nv[]裡的區間，然後再用上圖的做法求出該行的總和。

對了，記得也要把前後沒有計算到的地方都加上1。

AC code:

//By SCJ

//tioj 1045

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define maxn 10000

typedef pair<int,int> P;

vector<P> v[maxn+5],nv[maxn+5];

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int n;

   while(cin>>n,n!=0)

   {

       int l,u,r,d;

       long long ans=0;

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

       {

           cin>>l>>u>>r>>d;

           v[u+1].push_back({l+1,1});

           v[u+1].push_back({r+1,-1});

           nv[d+1].push_back({l+1,1});

           nv[d+1].push_back({r+1,-1});

       }

       multiset<P> s;

       for(int i=1;i<=maxn;++i)

       {

           for(P j:nv[i]) s.erase(s.find(j));

           for(P j:v[i]) s.insert(j);

           int la=1,sum=0;

           for(P j:s)

           {

               ans+=(1LL<<sum)*(j.first-la);

               sum+=j.second;

               la=j.first;

           }

           if(s.size()) ans+=( maxn - ((--s.end())->first) )+1;

           else ans+=maxn;

       }

       cout<<ans<<endl;

       for(int i=0;i<=maxn;++i) v[i].clear(),nv[i].clear();

   }

}