给出一组序列,问某个区间内序列的和,跟普通求和不同的是,要求值相同的元素只能算一次。
首先看数据范围,就知道要离散化,不然没法标记某个数是否出现过。
然后要对要查询的区间进行排序,按右端点进行排序。
然后按顺序遍历点,如果该点的值以前出现过,就删掉以前的那个,然后插入该点,记录下这个值的位置。刚才已经对询问区间排序了,那么所有右端点在该点的区间都可以进行查询了。
那么为什么要这么干呢。观察一个区间,我们可以发现,如果出现重复的,尽量删除左边的,保留右边的,那么右端点相同的区间都可以进行查询。
下面是树状数组版本的,不得不说树状数组求区间和实在是比较方便
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 66666
#define MAXM 104444
#define INF 100000000
#define eps 1e-7
#define L(X) X<<1
#define R(X) X<<1|1
using namespace std;
struct interval
{
int l, r, id;
bool operator <(const interval &a)const
{
return r < a.r;
}
}p[MAXM];
int x[MAXN], a[MAXN], h[MAXN], n;
long long tx[MAXN], ans[MAXM];
int bin(int v, int bound)
{
int low = 0, high = bound - 1;
while(low <= high)
{
int mid = (low + high) >> 1;
if(x[mid] == v) return mid;
if(x[mid] < v) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int lowbit(int x)
{
return x & -x;
}
void modify(int x, int v)
{
for(int i = x; i <= n; i += lowbit(i))
tx[i] += v;
}
long long get_sum(int x)
{
long long sum = 0;
for(int i = x; i > 0; i -= lowbit(i))
sum += tx[i];
return sum;
}
int main()
{
int T, m;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
int cnt = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
x[cnt++] = a[i];
}
memset(tx, 0, sizeof(tx));
sort(x, x + cnt);
cnt = unique(x, x + cnt) - x;
scanf("%d", &m);
for(int i = 0; i < m; i++)
{
scanf("%d%d", &p[i].l, &p[i].r);
p[i].id = i;
}
sort(p, p + m);
for(int i = 0; i < cnt; i++)
h[i] = 0;
int j = 0;
for(int i = 1; i <= n; i++)
{
int id = bin(a[i], cnt);
if(h[id]) modify(h[id], -a[i]);
modify(i, a[i]);
h[id] = i;
for(; j < m; j++)
{
if(p[j].r == i) ans[p[j].id] = get_sum(p[j].r) - get_sum(p[j].l - 1);
else break;
}
}
for(int i = 0; i < m; i++)
printf("%I64d\n", ans[i]);
}
return 0;
}
分享到:
相关推荐
Hdu 3333解题报告 题意描述: 给你n个数现在要你求在k个区间上[ai, bi]的不相同的数之和各是多少. N,000; k,000; 显然,这题不能用暴力来做。 这题我们选择用线段数来做。
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241