HDU 3874 Necklace(树状数组的离线操作)-白红宇

HDU 3874 Necklace(树状数组的离线操作)

阅读量：4512 次

发布时间：2019-06-08

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

题目链接：

【题目大意】

组成项链的珠子有品级之分，价值从1~1000000不等，然而珠子的价值会有重复，例如一个项链有这6个珠子构成 1 1 1 2 3 1，

我们要求给定区间珠子的价值总和，如果区间内有相同价值的珠子，则只计算相同价值珠子中的一个；

用 F（左区间，右区间），来求区间和。

例如 F(1,3)=1, F(2,4)=3, F(2,6)=6.

区间求和问题用树状数组来做比较方便，但是重复数字怎么处理那？在网上学到了离线操作，非常巧妙

离线查询，顾名思义，不再是实时查询，而是根据需要先调整查询的顺序。

简单来讲就是将查询操作按照右区间从小到大排序。

然后从头依次遍历，每次用map储存当前数字的最右区间，如果发现当前map值不为空，就删除节点（删除之前保存的数字最右区间），这样在求和的时候就不会重复计算相同的值了。

具体来看代码吧~

【源代码】

#include 
    
     #include 
     
      #include 
      #include 
       
        #include 
        
         using namespace std;int n;typedef long long ll;const  int maxn = 200010;const  int maxe = 50010;struct node{	int l,r,po;}order[maxn];ll s[maxe];int num[maxe];ll ans[maxn];bool cmp(const node&a,const node&b){	return a.r
         
          0;i-=lowbit(i)) ans+=s[i]; return ans;}int main(){ int T; map
          
           mp; scanf("%d",&T); while(T--){ memset(s,0,sizeof(s)); //储存树状数组要清空 scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); } int cmd; scanf("%d",&cmd); for(int i=1;i<=cmd;i++){ scanf("%d%d",&order[i].l,&order[i].r); order[i].po = i; //记录下表，方便排序后寻找 } sort(order+1,order+cmd+1,cmp); int r=1; //从开始依次遍历 mp.clear(); for(int i=1;i<=cmd;i++){ while(r<=order[i].r){ if(mp[num[r]]) modify(mp[num[r]],-num[r]); //如果出现重复， 删去之前的节点，map中保存了上次出现的节点位置 mp[num[r]]=r; //保存当前节点位置 modify(r,num[r]); //更新树状数组 r++; } ans [order[i].po]=sum(order[i].r)-sum(order[i].l-1); //每次直接求和 } for(int i=1;i<=cmd;i++) printf("%lld\n",ans[i]); } return 0;}

转载于:https://www.cnblogs.com/chaiwenjun000/p/5321175.html

你可能感兴趣的文章