这个题目有个显然的做法可能时间复杂度没有那么优秀。
考虑维护区间的最小值。
先把相同颜色的拉出来。
显然,对于两两相同颜色之间的最小权小于等于p,那么在序列中包含这一段的区间都是合法的。
于是我们想到了什么时候这一段区间都是不合法的呢?
即补集转换。
于是我们只需要把两两相同颜色的最小全大于p的两两区间拿出来,按照
$\frac{len(len-1)}{2}$计算负的贡献就可以了。
复杂度大概是可以看的$O(n log_2 n)$
```cpp
// luogu-judger-enable-o2
# include <bits/stdc++.h>
# define inf (0x3f3f3f3f)
# define int long long
using namespace std;
const int N=2e5+10;
struct rec{ int c,w;}t[N];
int tr[N<<2];
int n,k,p,a[51][N],tmp[N];
int read()
{
int x=0,w=0;char c=0;
while (!(c>='0'&&c<='9')) w|=c=='-',c=getchar();
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
void build(int x,int l,int r)
{
if (l==r) { tr[x]=t[l].w; return;}
int mid=(l+r)>>1;
build(2*x,l,mid);
build(2*x+1,mid+1,r);
tr[x]=min(tr[2*x],tr[2*x+1]);
}
int query(int x,int l,int r,int ql,int qr)
{
if (ql<=l&&r<=qr) return tr[x];
int mid=(l+r)>>1;
int ret=inf;
if (ql<=mid) ret=min(ret,query(2*x,l,mid,ql,qr));
if (qr>mid) ret=min(ret,query(2*x+1,mid+1,r,ql,qr));
return ret;
}
signed main()
{
// freopen("P1311.in","r",stdin);
// freopen("P1311.out","w",stdout);
scanf("%lld%lld%lld",&n,&k,&p);
for (int i=1;i<=n;i++) {
t[i].c=read();t[i].w=read();
a[t[i].c][++a[t[i].c][0]]=i;
}
memset(tr,0x3f,sizeof(tr));
build(1,1,n);
int ans=0;
for (int col=0;col<k;col++) {
ans+=a[col][0]*(a[col][0]-1)/2;
for (int i=1;i<a[col][0];i++)
if (query(1,1,n,a[col][i],a[col][i+1])<=p) tmp[i]=1;
else tmp[i]=0;
int l=1;
while (l<a[col][0]) {
int r=l;
while (tmp[r]==0&&r<a[col][0]) r++;
if (l==r) l++;
else ans-=(r-l)*(r-l+1)/2,l=r+1;
}
}
printf("%lld\n",ans);
return 0;
}