HDU 3333 Turing Tree 树状数组 离线查询
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU 3333 Turing Tree 树状数组 离线查询，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2695字，纯文字阅读大概需要4分钟。
内容图文
题意： 给你一个数列，然后有n个查询，问你给定区间中不同数字的和是多少。
思路还是比较难想的，起码对于蒟蒻我来说。
将区间按照先右端点，后左端点从小到大排序之后，对于每个查询，我只要维护每个数字出现的最后一次就可以了（这个结论稍微想一下就可以证明是正确的）。
然后就是简单的点更新，区间求和问题了～
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stack>
#include <sstream>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int> pii;
const int INF = INT_MAX / 3;
const double eps = 1e-8;
const LL LINF = 1e17;
const double DINF = 1e60;
const int maxn = 3e4 + 10;
struct Seg {
int l,r,id;
LL ans;
Seg(int l,int r,int id): l(l),r(r),id(id) {}
};
int n,val[maxn],last[maxn],m;
VI num;
vector<Seg> query;
LL C[maxn];
bool ext[maxn];
bool cmp(const Seg &a,const Seg &b) {
if(a.r == b.r) return a.l < b.l;
return a.r < b.r;
}
bool cmp1(const Seg &a,const Seg &b) {
return a.id < b.id;
}
inline int lowbit(int x) {
return x & (-x);
}
void addv(int pos,LL v) {
while(pos <= n) {
C[pos] += v; pos += lowbit(pos);
}
}
LL ask_(int pos) {
LL ret = 0;
while(pos > 0) {
ret += C[pos]; pos -= lowbit(pos);
}
return ret;
}
LL ask(int l,int r) {
return ask_(r) - ask_(l - 1);
}
int getID(int Val) {
return lower_bound(num.begin(),num.end(),Val) - num.begin() + 1;
}
void solve() {
memset(C,0,sizeof(C));
memset(last,-1,sizeof(last));
int npos = 1;
for(int i = 0;i < m;i++) {
Seg &now = query[i];
while(npos <= now.r) {
int nowval = getID(val[npos]);
if(last[nowval] != -1) addv(last[nowval],-val[npos]);
last[nowval] = npos;
addv(npos,val[npos]);
npos++;
}
now.ans = ask(now.l,now.r);
}
}
int main() {
int T; scanf("%d",&T);
while(T--) {
query.clear();
num.clear();
int tmp; scanf("%d",&n);
for(int i = 1;i <= n;i++) {
scanf("%d",&val[i]); num.PB(val[i]);
}
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
scanf("%d",&m);
for(int i = 0;i < m;i++) {
int l,r; scanf("%d%d",&l,&r);
query.PB(Seg(l,r,i));
}
sort(query.begin(),query.end(),cmp);
solve();
sort(query.begin(),query.end(),cmp1);
for(int i = 0;i < m;i++) cout << query[i].ans << endl;
}
return 0;
}
原文：http://www.cnblogs.com/rolight/p/3925437.html
内容总结
以上是互联网集市为您收集整理的HDU 3333 Turing Tree 树状数组 离线查询全部内容，希望文章能够帮你解决HDU 3333 Turing Tree 树状数组 离线查询所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。