题目链接:https://ac.nowcoder.com/acm/contest/3005/H
官方题解一开始没有看懂
还是搜到的一个题解才开始明白(真难想)
直接给链接了 题目讲解https://blog.csdn.net/Q_1849805767/article/details/104275449
树状数组的讲解:https://www.cnblogs.com/xenny/p/9739600.html
(好像集训3里面的G题也可以用树状数组去做明天去试试)
AC代码:
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
int qsum[550000],hsum[550000];
ll ans[550000];
int n;
int L[550000],r[550000],col[550000];
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int k)
{
while(i<=n)
{
ans[i]+=k;
i+=lowbit(i);
}
}
ll getsum(int i)
{
ll res=0;
while(i>0)
{
res+=ans[i];
i-=lowbit(i);
}
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&col[i],&L[i],&r[i]);
hsum[col[i]]++; //因为第一次i=1,可以直接将后面的全部加上
}
for(int i=1;i<=n;i++)
{
hsum[col[i]]--; //后缀颜色要减去自身的一个
update(col[i],-qsum[col[i]]); //减去前缀中与自己匹配的情况
cout<<getsum(r[i])-getsum(L[i]-1)<<" ";
qsum[col[i]]++; //为下一个i做准备,处理完的i放在下一个i+1中就相当于前缀了
update(col[i],hsum[col[i]]); //把后面与当前i相匹配的情况加上,方便后一次使用
}
cout<<endl;
return 0;
}
转载:https://blog.csdn.net/littlegoldgold/article/details/104416750
查看评论