代码其实有很多卡常空间……只是我懒得卡常……
可以考虑枚举某个不被包含的颜色，并枚举该颜色的一个点，然后在其下找同颜色的前驱后继并统计即可。
set + 主席树被卡常……
在 JZOJ 不加 pragma 过不去，在 BZOJ 反而能过。
以及小奇的糖果是真的过不去了……
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125/*#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")*/
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x,1);
}
const int N = 1e5;
int T,n,k,flag;
struct note
{
int x,y;
inline bool operator<(const note &o) const
{
return y < o.y;
}
};
int ind[N * 2 + 5],len;
set<int> d;
vector<int> s[N * 2 + 5];
vector<note> vec[N + 5];
struct node
{
int sum;
int ls,rs;
} seg[(N << 5) + 10];
int rt[N * 2 + 5],seg_tot;
void insert(int x,int k,int &p,int tl,int tr)
{
int &tot = seg_tot;
seg[++tot] = seg[p],seg[p = tot].sum += k;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
int mid = tl + tr >> 1;
int ret = 0;
l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
return ret;
}
int ans;
int main()
{
scanf("%d",&T);
for(;T;--T)
{
scanf("%d%d",&n,&k),seg_tot = ans = flag = 0;
for(register int c = 1;c <= k;++c)
vec[c].clear();
int x,y,z;
for(register int i = 1;i <= n;++i)
scanf("%d%d%d",&x,&y,&z),ind[2 * i - 1] = x,ind[2 * i] = y,vec[z].push_back((note){x,y});
sort(ind + 1,ind + 2 * n + 1),len = unique(ind + 1,ind + 2 * n + 1) - ind - 1;
for(register int i = 1;i <= len;++i)
s[i].clear();
for(register int c = 1;c <= k;++c)
{
if(vec[c].empty())
{
flag |= 1;
break;
}
sort(vec[c].begin(),vec[c].end());
for(register vector<note>::iterator it = vec[c].begin();it != vec[c].end();++it)
it->x = lower_bound(ind + 1,ind + len + 1,it->x) - ind,
it->y = lower_bound(ind + 1,ind + len + 1,it->y) - ind,
s[it->y].push_back(it->x);
}
if(flag)
{
printf("%d\n",n);
continue;
}
for(register int i = 1;i <= len;++i)
{
rt[i] = rt[i - 1];
for(register vector<int>::iterator it = s[i].begin();it != s[i].end();++it)
insert(*it,1,rt[i],1,len);
}
for(register int c = 1;c <= k;++c)
{
d.clear(),d.insert(0),d.insert(len + 1);
for(register vector<note>::iterator it = vec[c].begin();it != vec[c].end();++it)
ans = max(ans,
query(*--d.upper_bound(it->x) + 1,*d.lower_bound(it->x) - 1,rt[it->y - 1],1,len)
),d.insert(it->x);
for(register set<int>::iterator it = ++d.begin(),pre = d.begin();it != d.end();++it,++pre)
ans = max(ans,query(*pre + 1,*it - 1,rt[len],1,len));
reverse(vec[c].begin(),vec[c].end());
d.clear(),d.insert(0),d.insert(len + 1);
for(register vector<note>::iterator it = vec[c].begin();it != vec[c].end();++it)
ans = max(ans,
query(*--d.upper_bound(it->x) + 1,*d.lower_bound(it->x) - 1,rt[len],1,len) - query(*--d.upper_bound(it->x) + 1,*d.lower_bound(it->x) - 1,rt[it->y],1,len)
),d.insert(it->x);
}
printf("%d\n",ans);
}
}