BZOJ 3658 Jabberwocky

代码其实有很多卡常空间……只是我懒得卡常……

可以考虑枚举某个不被包含的颜色，并枚举该颜色的一个点，然后在其下找同颜色的前驱后继并统计即可。
set + 主席树被卡常……
在 JZOJ 不加 pragma 过不去，在 BZOJ 反而能过。
以及小奇的糖果是真的过不去了……

代码：

/*#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")*/
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
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);
    }
}