BZOJ 3658: Jabberwocky (双向链表+BIT)

题意

平面上有n个点，每个点有k种颜色中的一个。你可以选择一条水平的线段获得在其上方或其下方的所有点，请求出你最多能够得到多少点，使得获得的点并不包含所有的颜色。

分析

线段可以向上向下,那么我们只考虑向上,最后y坐标取反再做一遍即可.

由于不包含所有颜色,那么对于两个颜色相同的点(x0,y0),(x1,y1)(x_0,y_0),(x_1,y_1)(x0​,y0​),(x1​,y1​),如果在x∈[a+1,c−1]x\in [a+1,c-1]x∈[a+1,c−1]范围内没有与它们颜色相同的点,那么一定可以选在这个范围里面的所有点.所以我们用树状数组维护在某个范围内的点数(先离散化),用双向链表维护某个点前面和后面跟它颜色相同且最近的点.最初线段在−∞-\infty−∞,然后从下到上移动线段,逐行删点,删的同时统计[pre+1,nxt−1][pre+1,nxt-1][pre+1,nxt−1]内的点数更新答案.

CODE

#include <cctype>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

    char ch; int flg = 1; for(;!isdigit(ch=getchar());)if(ch=='-')flg=-flg;

    for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 100005;

int n, m, ans;

int last[MAXN], pre[MAXN], nxt[MAXN], T[MAXN], X[MAXN];

struct node { int x, y, c, id; }a[MAXN];

inline bool cmpx(const node &i, const node &j) { return i.x < j.x; }

inline bool cmpy(const node &i, const node &j) { return i.y < j.y; }

inline void upd(int x, int val) {

	while(x <= n) T[x] += val, x += x&-x;

}

inline int qsum(int x) {

	int res = 0;

	while(x) res += T[x], x -= x&-x;

	return res;

}

inline void Calc(int l, int r) {

	if(l <= r) ans = max(ans, qsum(r)-qsum(l-1));

}

inline void solve() {

	memset(last, 0, sizeof last);

	memset(T, 0, sizeof T);

	for(int i = 1; i <= n; ++i) {

		upd(X[a[i].id=i]=a[i].x, 1);

		pre[i] = last[a[i].c], nxt[i] = n+1;

		if(pre[i]) nxt[pre[i]] = i;

		Calc(X[pre[i]]+1, X[i]-1);

		last[a[i].c] = i;

	}

	X[n+1] = n+1;

	for(int i = 1; i <= m; ++i) Calc(X[last[i]]+1, X[n+1]-1);

	sort(a + 1, a + n + 1, cmpy);

	for(int i = 1, j = 1; i <= n; i = j) {

		while(j <= n && a[i].y == a[j].y) upd(a[j++].x, -1);

		for(int k = i; k < j; ++k) {

			int o = a[k].id;

			pre[nxt[o]] = pre[o];

			nxt[pre[o]] = nxt[o];

			Calc(X[pre[o]]+1, X[nxt[o]]-1);

		}

	}

}

int main () {

	int T; read(T);

	while(T--) {

		read(n), read(m); ans = 0;

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

			read(a[i].x), read(a[i].y), read(a[i].c);

		sort(a + 1, a + n + 1, cmpx);

		int cur = 1;

		for(int i = 1; i <= n; ++i) {

			a[i].x = cur;

			if(a[i].x != a[i+1].x) ++cur;

		}

		cur = n+1;

		solve();

		for(int i = 1; i <= n; ++i) a[i].y *= -1;

		sort(a + 1, a + n + 1, cmpx);

		solve();

		printf("%d\n", ans);

	}

}