链接：https://ac.nowcoder.com/acm/contest/3005/H
来源：牛客网
大致题意：让我们针对每一个数，求这个数左区间和右区间颜色相同（也就是数字相同）得对数；
比如：左边3个“3'得颜色，右边2个‘3’得颜色，就有2*3=6对；
数据范围为5e5；所以可接受得复杂度为nlogn；
那么我们可以考虑线段树；
如何维护呢？
我们用两个vis去标记左边和右边各种颜色的个数；代码中visa标记的是右区间，visb标记的是左区间；
然后从左往右遍历一遍：
在某一次操作中，我们对第K个数求值；那么我们需要先把右区间颜色k的减1；
这个时候假如左区间有这个K数，我们就需要将这个数包含的对数求出来，然后update，
这里有个细节，假如k-1==k,那么需要减掉的对数要减1；
因为k-1并没有在上次的操作中计算；
然后，我们就求K-1这个位置的颜色在右区间的个数，然后将这个数update；
在跑一遍线段树求出第K个数的query（l,r,1）即可；
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+;
int visa[maxn];
int visb[maxn];
ll ans[maxn];
struct node
{
int val,l,r;
}a[maxn];
struct haa
{
int l;int r;
ll sum;
}tree[maxn<<];
void build(int l,int r,int root)
{
tree[root].l=l;tree[root].r=r;
tree[root].sum=;
if(l==r) return;
int mid=l+r>>;
build(l,mid,root<<);
build(mid+,r,root<<|);
}
void up(int root)
{
tree[root].sum=tree[root<<].sum+tree[root<<|].sum;
}
void update(int pos,int val,int root)
{
int L=tree[root].l;
int R=tree[root].r;
if(L==R){
tree[root].sum+=val;
return;
}
int mid=L+R>>;
if(pos<=mid) update(pos,val,root<<);
else update(pos,val,root<<|);
up(root);
}
ll query(int l,int r,int root)
{
int L=tree[root].l;
int R=tree[root].r;
if(l<=L&&r>=R){
return tree[root].sum;
}
ll ans=;
int mid=L+R>>;
if(l<=mid) ans+=query(l,r,root<<);
if(r>mid) ans+=query(l,r,root<<|);
return ans;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%d%d",&a[i].val,&a[i].l,&a[i].r);
visa[a[i].val]++;
}
build(,maxn,);
ans[]=;
visa[a[].val]--; //右区间--
visb[a[].val]++; //左区间++；
for(int i=;i<=n;i++){
visa[a[i].val]--; //右区间--；
if(visb[a[i].val]){ //如果左区间包含这个数的话；
//我们就需要减掉与这个数相关的对数；
//但是左区间包含i-1这一项；而这一项在上次操作中没有出现；
//所以当两者相等的时候，tmp--;
int tmp=visb[a[i].val];
if(a[i-].val==a[i].val) tmp--;
update(a[i].val,-tmp,);
}
int tmp=visa[a[i-].val];
update(a[i-].val,tmp,);
ans[i]=query(a[i].l,a[i].r,);
visb[a[i].val]++;
}
for(int i=;i<=n;i++)
printf("%lld ",ans[i]);
printf("\n");
return ;
}