题目链接：https://loj.ac/problem/10115 解题思路 一开始误会了重复种树的意思，以为是线段树染色QAQ，后来知道了重复种树是指该位置可以种无限棵树，用树状数组就能解决。我们用树状数组维护两个数组，一个是左区间的个数，二是右区间的个数。那么询问[l,r]，我们知道，r之前的左区间的个数，代表出现了多少种树，l之前(不包括l)的右区间的个数，代表了有多少种树的区间已经结束了，所以用query2®-query1(l-1)就是答案了。 AC代码
#include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> using namespace std; const int N=5e4+5; int n,m,l,r,K; int sum1[N],sum2[N]; int lowbit(int x) { return x&-x; } void update1(int x) { while(x<=n) { sum1[x]++; x+=lowbit(x); } } void update2(int x) { while(x<=n) { sum2[x]++; x+=lowbit(x); } } int query1(int x) { int res=0; while(x) { res+=sum1[x]; x-=lowbit(x); } return res; } int query2(int x) { int res=0; while(x) { res+=sum2[x]; x-=lowbit(x); } return res; } int main() { scanf("%d%d",&n,&m); while(m--) { scanf("%d%d%d",&K,&l,&r); if(K==1) { update1(l); update2(r); } else { printf("%d\n",query1(r)-query2(l-1)); } } return 0; }