[BZOJ4548]小奇的糖果

试题描述

有 \(N\) 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。

输入

包含多组测试数据,第一行输入一个正整数 \(T\) 表示测试数据组数。

接下来 \(T\) 组测试数据,对于每组测试数据,第一行输入两个正整数 \(N\)、\(K\),分别表示点数和颜色数。

接下来 \(N\) 行,每行描述一个点,前两个数 \(x, y (|x|, |y| \le 2^{30} - 1)\) 描述点的位置,最后一个数 \(z (1 \le z ≤ k)\) 描述点的颜色。

输出

对于每组数据在一行内输出一个非负整数 \(ans\),表示答案

输入示例

110 31 2 32 1 12 4 23 5 34 4 25 1 26 3 16 7 17 2 39 4 2

输出示例

5

数据规模及约定

对于 \(100\%\) 的数据,\(N \le 100000,K \le 100000,T \le 3\)

题解

此题和是双倍经验关系。

然而我的做法在这里直接 T 飞了，所以再讲一个不那么慢的做法。（虽然也是基本垫底）

如果给出的点没有提到所有颜色，就直接输出 \(n\)。

枚举不能包含的那个颜色 \(c\)，令所有颜色为 \(c\) 的点的集和为 \(S_c\)。将 \(S_c\) 中的点按 \(x\) 坐标排序，然后我们从左到右依次考虑每个点，并以 \(y\) 坐标为关键字维护单调栈，当删除单调栈中的元素时统计一下极大子矩形的答案。询问矩形内部点数可以用主席树一个 \(\log n\) 做。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 100010#define maxnode 2000010#define pii pair 
           
            #define x first#define y second#define mp(x, y) make_pair(x, y)int n, K, nX[maxn], nY[maxn];pii ps[maxn];vector 
            
              col[maxn];bool cmpy(pii a, pii b) { return a.y < b.y; }int ToT, rt[maxn], sumv[maxnode], lc[maxnode], rc[maxnode];void update(int& y, int x, int l, int r, int p) { sumv[y = ++ToT] = sumv[x] + 1; if(l == r) return ; int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x]; if(p <= mid) update(lc[y], lc[x], l, mid, p); else update(rc[y], rc[x], mid + 1, r, p); return ;}int query(int o, int l, int r, int ql, int qr) { if(!o) return 0; if(ql <= l && r <= qr) return sumv[o]; int mid = l + r >> 1, ans = 0; if(ql <= mid) ans += query(lc[o], l, mid, ql, qr); if(qr > mid) ans += query(rc[o], mid + 1, r, ql, qr); return ans;}int Query(int xl, int xr, int yl, int yr) { if(xl > xr || yl > yr) return 0; return query(rt[yr], 1, n, xl, xr) - query(rt[yl-1], 1, n, xl, xr);}int S[maxn], top;void work() { ToT = 0; memset(rt, 0, sizeof(rt)); memset(lc, 0, sizeof(lc)); memset(rc, 0, sizeof(rc)); n = read(); K = read(); rep(c, 1, K) col[c].clear(); rep(i, 1, n) { int x = read(), y = read(), c = read(); nX[i] = x; nY[i] = y; ps[i] = mp(x, y); col[c].push_back(ps[i]); } sort(nX + 1, nX + n + 1); sort(nY + 1, nY + n + 1); rep(i, 1, n) ps[i].x = lower_bound(nX + 1, nX + n + 1, ps[i].x) - nX, ps[i].y = lower_bound(nY + 1, nY + n + 1, ps[i].y) - nY; rep(c, 1, K) { if(!col[c].size()) return (void)printf("%d\n", n); rep(i, 0, (int)col[c].size() - 1) { pii& p = col[c][i]; p.x = lower_bound(nX + 1, nX + n + 1, p.x) - nX; p.y = lower_bound(nY + 1, nY + n + 1, p.y) - nY; } } sort(ps + 1, ps + n + 1, cmpy); int j = 1; rep(i, 1, n) { rt[i] = rt[i-1]; while(j <= n && ps[j].y == i) update(rt[i], rt[i], 1, n, ps[j++].x); } int ans = 0; rep(c, 1, K) { sort(col[c].begin(), col[c].end()); // optimus rep(i, 0, (int)col[c].size() - 1) ans = max(ans, Query(i ? col[c][i-1].x + 1 : 1, col[c][i].x - 1, 1, n)); ans = max(ans, Query(col[c][col[c].size()-1].x + 1, n, 1, n)); // down rep(i, 0, (int)col[c].size() - 1) { pii now = col[c][i]; while(top && col[c][S[top]].y > now.y) { ans = max(ans, Query(top > 1 ? col[c][S[top-1]].x + 1 : 1, now.x - 1, 1, col[c][S[top]].y - 1)); top--; } S[++top] = i; } while(top) { ans = max(ans, Query(top > 1 ? col[c][S[top-1]].x + 1 : 1, n, 1, col[c][S[top]].y - 1)); top--; } // up rep(i, 0, (int)col[c].size() - 1) { pii now = col[c][i]; while(top && col[c][S[top]].y < now.y) { ans = max(ans, Query(top > 1 ? col[c][S[top-1]].x + 1 : 1, now.x - 1, col[c][S[top]].y + 1, n)); top--; } S[++top] = i; } while(top) { ans = max(ans, Query(top > 1 ? col[c][S[top-1]].x + 1 : 1, n, col[c][S[top]].y + 1, n)); top--; } } printf("%d\n", ans); return ;}int main() { int T = read(); while(T--) work(); return 0;}