首先，答案的正方形的長度可以二分搜，所以，我們可以先把問題轉成：有沒有一個長度為X的正方形，可以成功地放進格子裡面。
那，我們也可以輕易地算出：題目的那P個矩形中，每一個矩形會影響到多少 " 左上角放在某個格子的正方形 " ，注意到現在正方形的長度已經被限制成X了。
那，有了這些之後，我們就可以使用掃描線囉~
你需要一顆線段樹，可以支援：
(1) 區間加值
(2) 區間減值
(3) 查詢整體的min。
如果掃到某一個時間，當下整體的min <= B，那就代表可以放。
這樣的複雜度是O(P * log P * log( min(n,m) ))，最後一筆subtask過不了QAQ。
最後一筆有一個很神奇(?)的特性：B = 0。
首先，我們先定義一個一個函數 F(x1,x2)：代表說，在 x 座標是介於 [x1, x2]的區域中，連續 y 座標都是空的最大長度是多少。
可以發現： F(x1,x2) >= F(x1-1, x2) && F(x1,x2) >= F(x1,x2+1)
可以發現，如果固定x1，當x2越大的時候，F(x1,x2)會越來越小
當x2固定時，隨著x1越來越大，F(x1,x2)會越來越大
於是，我們可以使用雙指針來維護x1,x2，如果當下F(x1,x2) >= x2-x1+1，代表我們找到一個邊長為x2-x1+1的三角形，並且可以移動x2的指針。
如果當下F(x1,x2) < x2 - x1 +1，我們就要移動x1的指針的。
所以，我們需要一個資料結構(線段樹)，維護：
(1) 加入一個線段
(2) 刪除一個線段
(3) 查詢當前狀態的F值
可以用類似 " 區間連續最大和 " 的線段樹來解決。
//really hard QAQ #include <bits/stdc++.h> using namespace std; typedef pair<int,int> Pt; typedef pair<int,int> pii; typedef pair<pii,pii> Rec; #define F first #define S second #define MP make_pair #define SZ(x) ((int)(x).size()) int n,m,b; int p; const int N = 400006; Rec rr[N]; Rec rrr[N]; int c[N]; vector<pii> Event[800006]; //MP(+ or - , index(to get y range) ) struct Node { static Node mem[4*200006]; Node *lc,*rc; int mn,tag; Node():lc(NULL),rc(NULL),tag(0),mn(0){} void pull() { mn = min(lc->mn,rc->mn); } } Node::mem[4*200006],*ptr = Node::mem; Node* Build(int L,int R) { Node* node = new(ptr++)Node(); if (L==R) return node; int mid=(L+R)>>1; node->lc = Build(L,mid); node->rc = Build(mid+1,R); return node; } void push(Node* node,int L,int R) { if (L==R) node->tag = 0; if (node->tag == 0)return; node->lc->mn += node->tag; node->rc->mn += node->tag; node->lc->tag += node->tag; node->rc->tag += node->tag; node->tag = 0; return; } void modify(Node* node, int L,int R,int l,int r,int del) { if (l>R || L>r) return; else if (l<=L &&R<=r) { node->mn += del; node->tag += del; return; } push(node,L,R); int mid=(L+R)>>1; modify(node->lc,L,mid,l,r,del); modify(node->rc,mid+1,R,l,r,del); node->pull(); return; } bitset<1000006> vis_x,vis_y,ee; bool can_0(int len) { if (len >= min(n,m)+1) return false; ptr = Node::mem; int nn = n-len+1, mm = m-len+1; int pp=0; vector<int> vx,vy; vis_x = ee; vis_y = ee; for (int i=1;p>=i;i++) { int x1 = rr[i].F.F - len+1; int y1 = rr[i].F.S - len+1; int x2 = rr[i].S.F; int y2 = rr[i].S.S; x1 = max(x1,1); y1 = max(y1,1); if (x1 <= nn && y1 <= mm) { x2 = min(x2,nn); y2 = min(y2,mm); //if (x1 == 1 && y1 == 1 && x2 == nn && y2 == mm) return false; rrr[++pp] = MP( MP(x1,y1) , MP(x2,y2) ); if (!vis_x[x1]) vx.push_back(x1); vis_x[x1] = true; if (x2 + 1 <= nn && !vis_x[x2+1]) vx.push_back(x2+1); vis_x[x2+1] = true; if (!vis_y[y1]) vy.push_back(y1); vis_y[y1] = true; if (1 <= y1-1 && !vis_y[y1-1]) vy.push_back(y1-1); vis_y[y1-1] = true; if (!vis_y[y2]) vy.push_back(y2); vis_y[y2] = true; if (y2+1 <= mm && !vis_y[y2+1]) vy.push_back(y2+1); vis_y[y2+1] = true; } } if (pp == 0) return true; vx.push_back(1); vx.push_back(nn); vy.push_back(1); vy.push_back(mm); sort(vx.begin(),vx.end()); vx.resize(unique(vx.begin(),vx.end()) - vx.begin()); sort(vy.begin(),vy.end()); vy.resize(unique(vy.begin(),vy.end()) - vy.begin()); //y axis --> segment tree for (int i=0;SZ(vx)>=i;i++) { Event[i].clear(); } for (int i=1;pp>=i;i++) { int x1=rrr[i].F.F; int pos = lower_bound(vx.begin(),vx.end(),x1) - vx.begin() + 1; Event[pos].push_back(make_pair(1,i)); rrr[i].F.S = lower_bound(vy.begin(),vy.end(),rrr[i].F.S) - vy.begin() + 1; rrr[i].S.S = lower_bound(vy.begin(),vy.end(),rrr[i].S.S) - vy.begin() + 1; } //cout << "len = " << len << endl; int mmm = SZ(vy); Node* root = Build(1,mmm); for (int i=1;SZ(vx)>=i;i++) { for (pii p:Event[i]) { if (p.F == -1) modify(root,1,mmm,rrr[ p.S ].F.S,rrr[ p.S ].S.S,-c[ p.S ]); else { modify(root,1,mmm,rrr[ p.S ].F.S,rrr[p.S].S.S, c[p.S] ); int x2 = rrr[p.S].S.F; if (x2+1 <= nn) { int _ = x2+1; int pos = lower_bound(vx.begin(),vx.end(),_) - vx.begin() + 1; Event[pos].push_back(make_pair(-1,p.S)); } } } push(root,1,mmm); //cout << "i = " << i << " , len = " << len << " root->mn = " << root->mn << endl; if (root->mn <= b) { return true; } } return false; //return true; } void solve() { for (int i=1;p>=i;i++) { scanf("%d %d %d %d %d",&rr[i].F.F,&rr[i].F.S,&rr[i].S.F,&rr[i].S.S,&c[i]); } int L=0,R=1000006; while (R-L != 1) { int mid=(L+R)>>1; //cout << "mid = " << mid << endl; if (can_0(mid)) L = mid; else R = mid; } printf("%d\n",L); } struct Sagiri { Sagiri *lc,*rc; int Lmax,Rmax,midmax; int cnt; int L,R; Sagiri(){} Sagiri(int _L,int _R):L(_L),R(_R),Lmax(0),Rmax(0),midmax(0),cnt(0){} void pull() { if (cnt) { Lmax = Rmax = midmax = 0; return; } else if (L==R) { Lmax = Rmax = midmax = 1; return; } int mid=(L+R)>>1; Lmax = (lc->Lmax == mid-L+1 ? lc->Lmax + rc->Lmax : lc->Lmax); Rmax = (rc->Rmax == R-mid ? rc->Rmax + lc->Rmax : rc->Rmax); midmax = max( max( lc->midmax , rc->midmax ) , lc->Rmax + rc->Lmax ); } }; Sagiri* Buildd(int L,int R) { Sagiri* sagiri = new Sagiri(L,R); if (L==R) { sagiri->pull(); return sagiri; } int mid=(L+R)>>1; sagiri->lc = Buildd(L,mid); sagiri->rc = Buildd(mid+1,R); sagiri->pull(); return sagiri; } void modifyy(Sagiri* sagiri,int L,int R,int l,int r,int del) { if (l>R || L>r) return; else if (l<=L && R<=r) { sagiri->cnt += del; sagiri->pull(); return; } int mid=(L+R)>>1; modifyy(sagiri->lc,L,mid,l,r,del); modifyy(sagiri->rc,mid+1,R,l,r,del); sagiri->pull(); return; } const int P = 1000006; vector<int> addd[P],subb[P]; int main () { scanf("%d %d %d",&n,&m,&b); scanf("%d",&p); if (p <= 30000) { solve(); return 0; } Sagiri* root = Buildd(1,m); for (int i=1;p>=i;i++) { scanf("%d %d %d %d %d",&rr[i].F.F,&rr[i].F.S,&rr[i].S.F,&rr[i].S.S,&c[i]); addd[ rr[i].F.F ].push_back(i); subb[ rr[i].S.F ].push_back(i); } int ans=0; int L=1; for (int R=1;n>=R;R++) { for (int i:addd[R]) { modifyy(root,1,m,rr[i].F.S,rr[i].S.S,1); } //cout << "L = " << L << " , R = " << R<<" , midmax = " << root->midmax << endl; if (root->midmax >= R-L+1) ans = max(ans,R-L+1); while (root->midmax < R-L+1) { for (int i:subb[L]) { modifyy(root,1,m,rr[i].F.S,rr[i].S.S,-1); } ++L; } } printf("%d\n",ans); }
沒有留言:
張貼留言