hdu 3333 Turing Tree 线段树 + 离线-白红宇的个人博客

发布日期：2021-09-25 23:57:56 浏览次数：5 分类：技术文章

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

题目给定一个序列，让后查询m个区间，输出区间内数的和，重复的不计算多次。

想了半天也没想出来怎么在线维护这样的线段树，那就考虑一下离线怎么做。如果把区间按右端点排序，那么每次查询 [ l , r ] 的时候，如果都能保证 [ 1 , r ] 内重复数字的下标都在最右边，那这样即可避免重复了，而且还能保证每次查询的准确性。也就是说每次询问，看一下 [ 1 , r ] 是否已经确定，如果还没确定的话就需要遍历到 r ，这样就保证了每次 [ 1 , r ] 区间内没有重复的数字，且下标都只保留最右边。

最好是用树状数组写，线段树在洛谷能被卡掉好几个点，当初想用在线做所以敲了个线段树，~~不想改了~~ 。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=30010,M=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;int a[N],b[N];LL ans[M];struct query{ int l,r; bool operator < (const query &w) const { return r
                
                 =l&&tr[u].r<=r) return tr[u].sum; LL ans=0; if(l<=Mid) ans+=query(L,l,r); if(r>Mid) ans+=query(R,l,r); pushup(u); return ans;}void modify(int u,int l,int r,LL c){ if(tr[u].l>=l&&tr[u].r<=r) { tr[u].sum+=c; return; } if(l<=Mid) modify(L,l,r,c); else modify(R,l,r,c); pushup(u);}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); int t; cin>>t; while(t--) { int tot=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; int m; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+m); build(1,1,n); map
                 
                  mp; int t=1; for(int i=1;i<=m;i++) { int l=q[i].l,r=q[i].r; while(t<=r) { if(!mp.count(a[t])) modify(1,t,t,a[t]); else { modify(1,mp[a[t]],mp[a[t]],-a[t]); modify(1,t,t,a[t]); } mp[a[t]]=t; t++; } ans[q[i].id]=query(1,l,r); } for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); } return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/107034388 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：poj 3764 The xor-longest Path 字典树 + 前缀和

下一篇：P4198 楼房重建线段树 + 单调栈

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章