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();
}
}
