本文共 629 字，大约阅读时间需要 2 分钟。

【题目】

查询区间和，如果区间元素重复出现则计数一次。

【题解】

按区间的右端点建立树状数组，维护区间[1,R]的每个元素的最右位置。按查询区间的右端点排序，依次处理，每次更新当前值的最右位置即可。

若要查询区间不同元素个数，把

for(;it<=q[i].R;it++){            if(vis[a[it]]) //这个数之前出现过                add(vis[a[it]],-a[it]); //取消标记            vis[a[it]]=it; //记录最大位置            add(it,a[it]); //添加新标记        }

改为如下代码即可

for(;it<=q[i].R;it++){            if(vis[a[it]]) //这个数之前出现过                add(vis[a[it]],-1); //取消标记            vis[a[it]]=it; //记录最大位置            add(it,1); //添加新标记        }

【代码】

#include
   
    using namespace std;const int maxn=5e5+10;typedef long long ll;struct p{    int L,R,num;}q[maxn];int cmp(p a,p b){return a.R
   

转载地址：http://dhfen.baihongyu.com/