理解题意后可以把题目看成一个覆盖线段的问题。
对于点在 \(-m\) 上，看成在 \(m\) 上。
对于 \(l<r\)，不用处理。
对于 \(l>r\)，将问题看成 \((l,m)\) 和 \((-m+1.r)\) 两个区间。
对于正常处理点的问题，Splay 可以在 \(l\) 时加入这个点，\(r+1\) 时删除这个点。
但本题为线段覆盖，所以我们可以把线段的下标看为点的下标，但是一个 \((l,r)\) 的区间只能覆盖 \((r-l)\) 的线段数，所以在 \(r\) 时就删除这个点即可。
剩下的都是 Splay 板子了，离线排序，插入，删除，在一个点时判断是否树中有超过 \(k\) 的节点，如果有，那么搜索第 \(k\) 大的数，否则赋为 \(0\)。
时间复杂度：\(O(n\times \log(n))\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
int n,m,k,cnt,root,nl,nr;
struct node2
{
int name,data;
bool flag;
}ask[4*N];
int cmp2(node2 fi,node2 se)
{
if(fi.name==se.name)return fi.flag<se.flag;
return fi.name<se.name;
}
void clac(int &x,int &y)
{
nl=0;
if(x>y)
{
nl=x;
x=-m+1;
}
}
struct node
{
int fa,ch[2],siz,cnt,val;
}t[4*N];
inline void newnode(int &x,int fa,int val)
{
x=++cnt;
t[x].fa=fa;
t[x].val=val;
t[x].cnt=t[x].siz=1;
}
inline void connect(int x,int fa,int son)
{
t[x].fa=fa;
t[fa].ch[son]=x;
}
inline bool ident(int x,int fa)
{
return t[fa].ch[1]==x;
}
inline void pushup(int x)
{
t[x].siz=t[x].cnt+t[t[x].ch[0]].siz+t[t[x].ch[1]].siz;
}
inline void rotate(int x)
{
int fa=t[x].fa,ff=t[fa].fa,k=ident(x,fa);
connect(t[x].ch[k^1],fa,k);
connect(fa,x,k^1);
connect(x,ff,ident(fa,ff));
pushup(fa),pushup(x);
}
void splay(int x,int topp=0)
{
if(topp==0)root=x;
while(t[x].fa!=topp)
{
int fa=t[x].fa,ff=t[fa].fa;
if(ff!=topp)ident(x,fa)^ident(fa,ff)?rotate(x):rotate(fa);
rotate(x);
}
}
void ins(int val,int &x=root,int fa=0)
{
if(!x)newnode(x,fa,val),splay(x);
else if(t[x].val>val)ins(val,t[x].ch[0],x);
else if(t[x].val<val)ins(val,t[x].ch[1],x);
else t[x].cnt++,splay(x);
}
void erase(int val,int x=root)
{
if(t[x].val==val)
{
splay(x);
if(t[x].cnt>=2)t[x].cnt--;
else if(t[x].ch[1])
{
int p=t[x].ch[1];
while(t[p].ch[0])p=t[p].ch[0];
splay(p,x);
root=p,connect(t[x].ch[0],p,0),t[p].fa=0;
pushup(p);
}
else root=t[x].ch[0],t[t[x].ch[0]].fa=0;
}
else if(t[x].val>val)erase(val,t[x].ch[0]);
else erase(val,t[x].ch[1]);
}
int getrank(int k,int x=root)
{
if(k<=0)
{
splay(x);
return t[x].val;
}
if(k<=t[t[x].ch[0]].siz)return getrank(k,t[x].ch[0]);
int tmp=k-t[t[x].ch[0]].siz-t[x].cnt;
if(tmp<=0)
{
splay(x);
return t[x].val;
}
return getrank(tmp,t[x].ch[1]);
}
signed main()
{
//freopen("a.out","r",stdin);
//freopen("area.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&k);
int cnp=0;
for(int i=1;i<=n;i++)
{
int dat,lc,rc;
scanf("%lld%lld%lld",&dat,&lc,&rc);
if(lc==-m)lc=m;
if(rc==-m)rc=m;
clac(lc,rc);
ask[++cnp]=(node2){lc,dat,0};
ask[++cnp]=(node2){rc,dat,1};
if(nl)ask[++cnp]=(node2){nl,dat,0};
}
sort(ask+1,ask+1+cnp,cmp2);
int bef=1,num=0,ans=0;
for(int i=-m+1;i<=m;i++)
{
for(;bef<=cnp;bef++)
{
if(ask[bef].name!=i)break;
if(ask[bef].flag==1)num--,erase(ask[bef].data*ask[bef].data);
else num++,ins(ask[bef].data*ask[bef].data);
}
if(num>=k)ans+=getrank(num-k+1);
}
printf("%lld",ans);
return 0;
}
/*
10 100 2
24660 98 32
906 -15 -49
26067 -52 -23
15409 -76 -25
22490 41 65
2600 -10 -7
4310 15 75
20389 -100 -3
4421 8 -40
8664 -70 -95
*/