设为首页 加入收藏

TOP

HDU 3333 Turing Tree（树状数组 || 线段树）
2015-11-21 00:55:50 来源: 作者: 【大 中 小】 浏览:1次
Tags：HDU 3333 Turing Tree 线段

题意：给定一个区间，q个查询，对于每次查询回答这个区间内所有不重复的数的和。

思路：可以考虑使用树状数组来做。

先读入所有查询，离线来做，将所有查询按右端点升序排序。

那么我们从给定区间的第一个元素开始遍历这个区间，在此过程中更新每一个元素上一次出现的位置，每次将现在位置加上a[i]并将lastpos位置减去a[i]，

也就是说，我们每一步都是保留与当前位置距离最近的重复元素值，其余置零，那么这样肯定能保证答案正确，

如果遍历到的这个位置恰好是一个询问的右端点，那么我们输出修改后的区间值之和。

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #define eps 1e-6 #define LL long long #define pii (pair
               
                ) //#pragma comment(linker, /STACK:1024000000,1024000000) using namespace std; const int maxn = 30000 + 300; const int maxq = 100000+1000; //const int INF = 0x3f3f3f3f; int n, q; int a[maxn], lastpos[maxn]; LL C[maxn]; map
                
                  Hash; int ha; struct Query { int l, r, id; bool operator < (const Query& A) const { return r < A.r; } } query[maxq]; LL ans[maxq]; int lowbit(int x) { return (x&(-x)); } LL sumv(int x) { LL ret = 0; while(x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } void add(int x, int d) { while(x <= n) { C[x] += d; x += lowbit(x); } } int dis(int x) { if(!Hash.count(x)) return Hash[x] = ++ha; return Hash[x]; } void init() { ha = 0; Hash.clear(); memset(lastpos, 0, sizeof(lastpos)); memset(C, 0, sizeof(C)); } int main() { // freopen(input.txt, r, stdin); int T; cin >> T; while(T--) { init(); cin >> n; for(int i = 1; i <= n; i++) scanf(%d, &a[i]); cin >> q; for(int i = 0; i < q; i++) { int u, v; scanf(%d%d, &u, &v); query[i].l = u; query[i].r = v; query[i].id = i; } sort(query, query+q); int cnt = 0; for(int i = 1; i <= n; i++) { if(!lastpos[dis(a[i])]) add(i, a[i]), lastpos[dis(a[i])] = i; else { add(i, a[i]); add(lastpos[dis(a[i])], -a[i]); lastpos[dis(a[i])] = i; } while(cnt 
                  
                 
?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：hdu1253（胜利大逃亡） 下一篇：HDU 5344 多个数的和异或-思维-（..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: